Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!sun-barr!newstop!sun!amdcad!weitek!weaver
From: weaver
Newsgroups: comp.lang.c
Subject: Integer Square Root (Was Re: # to the nth power)
Keywords: square root integer
Message-ID: <1990Nov4.173555.25376@weitek.COM>
Date: 4 Nov 90 17:35:55 GMT
References: <9750@helios.TAMU.EDU> <1990Nov1.232830.17131@NCoast.ORG> <2730D2C2.13524@maccs.dcss.mcmaster.ca> <3809@idunno.Princeton.EDU>
Sender: weaver@weitek.COM (mike weaver)
Reply-To: weaver@weitek.UUCP (Michael Weaver)
Organization: WEITEK Corp. Sunnyvale Ca.
Lines: 64



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