Re: sqrt

[Karim Belabas <Karim.Belabas@math.u-psud.fr>]

* Jon Perry [2004-11-14 21:47]:
> May I ask for a profesional opinion on this sqrt algorithm?
> 
> Consider sqrt(n) where n has D digits. The square root therefore has D/2 or
> D+1/2 digits according to D being even or odd, let this be d.
> 
> Create y=10^d.
> 
> Add 10^d until y^2>n, then subtract 10^d to maintain 'underness'..
> 
> Lower d by 1, and repeat.

Assuming the expected output is floor( sqrt(n) ), this is correct but
rather inefficient [ # of operations linear in D, overall time cubic in D
assuming classical arithmetic ]. The "schoolbook algorithm" is a bit
better.  Newton's iteration

  x_0     = 1      [ or 10^{floor D/2} if you wish ]
  x_{i+1} = (1/2)(x_i + n/x_i)  [ only 2^i digits need to be computed ]

is much better. Paul Zimmermann has written a very nice survey of standard
multiprecision algorithm

  http://www.loria.fr/~zimmerma/papers/RR4272.ps.gz

(in french, but lots of explicit examples).

Cheers,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]