Karim Belabas on Wed, 17 Nov 2004 19:46:24 +0100

 Re: sqrt

```* 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]

```

• References:
• sqrt
• From: "Jon Perry" <perry@globalnet.co.uk>