Path: chuka.playstation.co.uk!chuka.playstation.co.uk!scea!greg_labrec@interactive.sony.com
From: Nick Porcino <Nick_Porcino@bc.sympatico.ca>
Newsgroups: scea.yaroze.programming.3d_graphics,scea.yaroze.programming.3d_graphics
Subject: Re: A reply to one of Nick's questions.
Date: Thu, 18 Sep 1997 22:28:42 -0800
Organization: SCEA News Server
Lines: 28
Message-ID: <34221B98.7AD5@bc.sympatico.ca>
References: <01bcbc4f$8c5a55e0$0e9f22cf@SmarttNet.smartt.com> <3414FD7E.2EE5@bc.sympatico.ca> <34150952.6D6A5DF3@micronetics.com> <341CE849.48A2@bc.sympatico.ca> <01bcc1c4$5edb1c60$c793989e@fourny.demon.co.uk>
NNTP-Posting-Host: vcta01m04-63.bctel.ca
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01-C-SYMPA (Macintosh; I; PPC)
Xref: chuka.playstation.co.uk scea.yaroze.programming.3d_graphics:129

Well here you go, Grim, and anyone else. An integer square root. It
works on 32 bit numbers and 16.16 fixed point. I assume it works on
other species of fixed point numbers as well, although I haven't tried
it yet.

This code was the result of a contest we had in the bad old days in
comp.graphics.algorithms (back in the early 80's) to come up with the
world's most efficient square root routine. Unfortunately, I don't know
who wrote it, because back then I was a punk who was just happy to snag
some codez and get back to coding. 

#define STEP(k) s = r + (1L << k * 2); r >>= 1; \
                                if (s <= v) { v -= s; r |= (1L << k *
2); }

u_long Sqrt(u_long n)
{
        u_long r = 0, s, v = n;

        STEP(15);       STEP(14);       STEP(13);       STEP(12);
        STEP(11);               STEP(10);       STEP(9);               
STEP(8);
        STEP(7);                STEP(6);               
STEP(5);                STEP(4);
        STEP(3);                STEP(2);               
STEP(1);                STEP(0);
        return r;
}