|
|
Re: Root (EXACT Square Root Algorithm)
Posted:
Jul 12, 1999 4:45 PM
|
|
Gareth McCaughan wrote:
>
> Thomas Chrapkiewicz wrote:
>
> > This method for square roots is EXACT for the number of digits that you have
> > the patience to use it to.
> [SNIP]
>
> It might be worth mentioning that this algorithm works especially
> nicely in binary.
>
> If you can do division efficiently, another possibility is to use
> Newton's method (though I think this particular application of it
> goes back to before Newton): start with any half-decent guess at
> the square root and iterate x -> (x+a/x)/2 where a is the thing
> whose square root you want.
AsI recall, I once coded a fast Newton's method square root algorithm
that minimized the number of iterations required by referring to a 256
entry lookup table of guesses, and used the most significant 8 bits as
pointer. There was a little more to it than that, but a good guess can
shorten things considerably.
John Popelish
|
|
