Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!uwvax!tank!mimsy!chris
From: chris@mimsy.umd.edu (Chris Torek)
Newsgroups: comp.graphics
Subject: Re: Integral Square Root
Message-ID: <21562@mimsy.umd.edu>
Date: 31 Dec 89 20:46:52 GMT
References: <9170@cbmvax.commodore.com> <21550@mimsy.umd.edu> <21561@mimsy.umd.edu>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 76

Aw heck. :-)

Here is my version of Rokicki's code, complete with a main() to test it.

/*
 * Integer square root routine, good for up to 32-bit values.
 * Note that the largest square root (that of 0xffffffff) is
 * 0xffff, so the result fits in a regular unsigned and need
 * not be `long'.
 *
 * Original code from Tomas Rokicki (using a well known algorithm).
 * This version by Chris Torek, University of Maryland.
 *
 * This code is in the public domain.
 */
unsigned
root(v)
	register unsigned long v;
{
	register long t = 1L << 30, r = 0, s;

#define STEP(k) \
	s = t + r; \
	r >>= 1; \
	if (s <= v) { \
		v -= s; \
		r |= t; \
	}
	STEP(15); t >>= 2;
	STEP(14); t >>= 2;
	STEP(13); t >>= 2;
	STEP(12); t >>= 2;
	STEP(11); t >>= 2;
	STEP(10); t >>= 2;
	STEP(9); t >>= 2;
	STEP(8); t >>= 2;
	STEP(7); t >>= 2;
	STEP(6); t >>= 2;
	STEP(5); t >>= 2;
	STEP(4); t >>= 2;
	STEP(3); t >>= 2;
	STEP(2); t >>= 2;
	STEP(1); t >>= 2;
	STEP(0);
	return r;
}

#ifdef MAIN
#include <stdio.h>
#include <math.h>

main()
{
	unsigned long l;
	char buf[100];

	for (;;) {
		(void) printf("gimme a number> ");
		if (fgets(buf, sizeof buf, stdin) == NULL)
			break;
		/* should use strtoul here but some do not have it */
		if (sscanf(buf, " 0x%lx", &l) != 1 &&
		    sscanf(buf, " 0%lo", &l) != 1 &&
		    sscanf(buf, "%lu", &l) != 1 &&
		    sscanf(buf, "%lx", &l) != 1)
			(void) printf("that was not a number\n");
		else
			(void) printf("root(%lu) => %u; sqrt(%lu) => %.17g\n",
			    l, root(l), l, sqrt((double)l));
	}
	exit(0);
}
#endif
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@cs.umd.edu	Path:	uunet!mimsy!chris