Integer Square Root (Was Re: # to the nth power)

[weaver]

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;
}