Integer square root routine needed.

[Joseph D. Shapiro]

In article <7415 at ecsvax.UUCP> utoddl at ecsvax.UUCP (Todd M. Lewis) writes:
>
>This may be the wrong place to post this, but I need C source
>to a reasonably fast integer square root routine.  (Actually
>a clear description of an efficient algorithm would do--I can
>write the code myself.)
>

this routine makes better and better guesses until it gets the same
answer twice.  This takes at most 20 iterations.  You could also limit
the iterations to 10 and get real close.

#include <stdlib.h>

#define print(xxx) printf(#xxx " = %ld\n",xxx);
#define MAXROOT 46340 /* square 46341 and you blow the long range */

long root(long value)
{
	long hi;
	long lo;
	long mid;
	long last;

	lo = 1;
	hi = value;
	if (hi>MAXROOT) hi=MAXROOT;
	mid = value/4;
	if (mid>MAXROOT) mid=MAXROOT;
	last = 0;

	while(mid != last)
	{
		last=mid;
		if (mid * mid > value)
		{
			hi = mid;
		}
		else
		{
			lo = mid;
		}
		mid = (hi+lo)/2L;
	}
	return mid;
}

main(int argc, char **argv)
{
	long value;

	value=atol(argv[1]);
	print(value);
	print(root(value));
	return 0;
}
-- 
__--__--__--__--__--__--__--__--__--__--__--__--__--__--__--__--__--__--__--__
Joe Shapiro					"My other car is a turbo...
ISC-Bunker Ramo     				 ...too."
{decvax,yale,philabs,oliveb}!bunker!shap