[comp.misc] Arbitrary precision square root alg?

g-mccann@gumby.cs.wisc.edu (Lester I. McCann) (02/10/88)

Can anyone point me toward an algorithm for computing square roots to
arbitrary precisions?  Thanks.

Lester McCann
University of Wisconsin CS Dept.
g-mccann@gumby.cs.wisc.edu

russ@hpldola.HP.COM (Russell Johnston) (02/11/88)

RE: Square root to specified precision

The "divide and average" method is not elaborate, but it works.
It does no error checking (assumes x > 0).
Specify desired precions in the while loop.

   sqrt=1
   while abs(x-x/sqrt) > .0000000001
      sqrt(x/y+sqrt)/2
   end

Thomas_E_Zerucha@cup.portal.com (02/12/88)

There is the long-division type method.  You shift two bits (from even
positions) into a working "divisior".  Then the working square root gets a
01 appended (shifted right) into it.  If this value is less than the
working quotient, subtract this remainder from the quotient, and replace
the 01 with a 1, otherwise replace it with a zero.  This sounds complicated
but it is simply the method found in many books converted to binary.  I can
retrieve a more detailed example and post it if you need it.  But you will
need long integers, but you don't need multiplies or divides, just shifts
and subtracts/compares.