Integer Square Root (Was Re: # to the nth power)
weaver
weaver
Mon Nov 5 04:35:55 AEST 1990
Here is an integer square root function I wrote. It is derived from
Newton's method, mentioned earlier by Henry Spencer. After trying
to learn algorithms used in hardware for square root, it seems to
me that none would translate to more efficient C than Newton's
method, unless divide or multiply are really slow.
Caveats:
I am not a mathematician.
This has not been exhaustively tested.
Cut here----------------------------------------
#include <stdio.h>
main(argc, argv)
int argc;
char **argv;
{
int n;
argv++;
argc--;
while (argc-- > 0) {
n = atoi(*argv++);
printf("Ans = %d\n", int_sqrt(n));
}
}
int
int_sqrt(n)
int n;
{
/* Integer version of Newton's method applied to square root. */
/* Similar to floating point, but need beware of overflows. */
/* Michael Gordon Weaver 1990/11/04 weaver at weitek.COM */
int i, j, k, d;
int k = 0;
/* range check */
if (n <= 0)
return -1;
/* initial estimate (j) */
i = j = n;
while (i > 0) {
i >>= 2;
j >>= 1;
}
/* iterate */
do {
d = ((j * j) - n) / (2 * j);
printf("Iter %d, guess = %d, est err = %d, remainder = %d\n",
++k, j, d, (j * j) - n);
j = j - d;
} while (d != 0);
/* we want answer < sqrt(n) when inexact */
if ((j * j) == n)
return j;
else
return j - 1;
}
More information about the Comp.lang.c
mailing list