Bob Fehrenbach <PICLIST@MITVMA.MIT.EDU> wrote:

> We haven't had a "how do you think this works" quiz from Andy Warren
> for a while so I thought I'd toss out this square root routine just
> for fun.  Maybe someone can make it smaller or faster and we could
> all benefit.
>
> A beer to the first one with an explanation but you have to come to
> Milwaukee to collect.

Bob:

Your algorithm is pretty cute... I don't think I've seen it before.

I guess I'm not eligible for the prize, though... For anyone else
who's trying to figure out how it works, here are a couple of clues
that might help (I'll try to be, like, really vague here so as not
to give anything away):

At every iteration, the "1" in P_A:B is shifted right one position
at the same time that N_A:B:C:D is shifted left one position, so the
comparisons go two bits at a time.

Of all the numbers that fit in two bits (0, 1, 2, and 3), the square
root is 0 only for the number 0.  The square root of all the others
is equal to 1 + a fraction.  For the square root of 1, this remainder
is 0.  For the square root of 2, it's approximately 1/2.  For the
square root of 3, it's approximately 3/4, or 1/2 + 1/4.

-Andy

Andrew Warren - fastfwd@ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499