🚀 go-pugleaf

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?

Yes, and it has ben discussed on the net earlier (I think in
comp.theory or sci.math).

>How does it really compare for smallish (under 32 or maybe even 64
>bit) square roots?

Very well, depending of course of whether you have fast hardware
division. If division is implemented using shifts, the square root is
usually one-and-a-half times as slow as division.

	Torben Mogensen (torbenm@diku.dk)