🚀 go-pugleaf

In article <1992Nov17.143914.19700@mcs.drexel.edu> dmagagno@mcs.drexel.edu (David Magagnosc) writes:
>This reminds me of something I came up with not long after the
>Midatlantic ACM Region Programming Contest last year.  One of the
>problems involved computing square roots by the long division-like
>method (which they claimed we all learned in elementary school).
>I translated it to binary, applied the techniques used for division,
>and came up with a sort of non-restoring square root.

>Now, the convergence is linear (2 bits of input for 1 bit of output
>per iteration), but it uses only elementary operations like shifts
>and adds, so its run time should be comparable to a single division.
>Newton's method, on the other hand, typically uses division on
>every iteration.

>So, the real question is, has someone done something like this before?
>How does it really compare for smallish (under 32 or maybe even 64
>bit) square roots?

I wrote a FP library last year on the ARM(2/3) and tried both the Newton
method and the long division type method.  With a good approximation from
the Newton method I was getting 6,000 or so sqrts per second on an 8MHz
ARM2.  My implementation of the long-division type algorithm got about
30,000 sqrts per second.

QED? :)

>Oh yes, it can also be extended very easily to compute fixed point
>square roots of integers -- as many bits as you like.

Yes - in the fp library, the routine gets 24 bits of output from 24 bits
of input, by assuming that there are another 24 0s tagged onto the input.

>
>D. Magagnosc
>-- 
>496620796F752063616E207265616420746869732C20796F752063616E206265636F6D65206120
>636F6D70757465722070726F6772616D6D657220616E6420676574206120676F6F64206A6F622E

mad@bike
-- 
* Simon Proven -  Secretary, University of Strathclyde Green Group *
* sproven@cs.strath.ac.uk             REAL (tm) peeps ride bike :) *