NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/arch/10823

Internet Message Format | 1992-11-17 | 1.7 KB

Path: sparky!uunet!pmafire!mica.inel.gov!ux1!news.byu.edu!hamblin.math.byu.edu!sol.ctr.columbia.edu!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!jvnc.net!netnews.upenn.edu!netnews.noc.drexel.edu!king.mcs.drexel.edu!dmagagno
From: [e-mail] (David Magagnosc)
Newsgroups: comp.arch
Subject: Re: integer distance or sqrt
Message-ID: <[e-mail]>
Date: 17 Nov 92 14:39:14 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Organization: Drexel University
Lines: 24

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?

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

D. Magagnosc
--
496620796F752063616E207265616420746869732C20796F752063616E206265636F6D65206120
636F6D70757465722070726F6772616D6D657220616E6420676574206120676F6F64206A6F622E