Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!cica!ctrsol!ginosko!uunet!yale!leichter
From: leichter@CS.YALE.EDU (Jerry Leichter)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Message-ID: <68259@yale-celray.yale.UUCP>
Date: 1 Aug 89 15:34:33 GMT
Sender: root@yale.UUCP
Organization: Yale Computer Science Department, New Haven, Connecticut, USA
Lines: 34
X-from: leichter@CS.YALE.EDU (Jerry Leichter (LEICHTER-JERRY@CS.YALE.EDU))

In article <7415@ecsvax.UUCP>, utoddl@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.)
> 
>The wheel I'm inventing is a library of matrix operations for
>3-D graphics for Yet Another Ultimate Space Game.  I've got 
>everything working with longs, but there's this one place where
>I just can't seem to get around doing a square root.  Right now
>I'm converting to a double and back, and that works Ok, but
>I'd rather have no floating point operations.
> 
>So, How does one efficiently go about taking the square root
>of a long?

A lot depends on what the expected range of inputs is.  A classic algorithm,
which is appropriate when you are usually taking square roots of small num-
bers, is to use the observation that the sum of the first n odd numbers is
n^2, so you can extract a square root using just subtraction and counting.

You might combine this with range reduction - divide through by a couple of
large squares up front.  In particular, removing the largest even power of two
is trivial on a binary machine.  Again, whether this is worth while depends a
bit on what you know about the numbers involved.  If they are likely to have
small factors, then range reduction can be easy and very effective.

Without some constraints on the inputs, it's probably hard to beat a carefully
implemented Newton-Raphson algorithm.  Since it sounds as if you are actually
computing Euclidean distances (sqrt(a^2 + b^2)), you can make an excellent
starting guess - actually, abs(a) + abs(b) is probably pretty good.

							-- Jerry