Node:Square Root Algorithm,
Next:Nth Root Algorithm,
Previous:Root Extraction Algorithms,
Up:Root Extraction Algorithms

#### Square Root

Square roots are taken using the "Karatsuba Square Root" algorithm by Paul
Zimmermann (see References). This is expressed in a divide and conquer
form, but as noted in the paper it can also be viewed as a discrete variant of
Newton's method.

In the Karatsuba multiplication range this is an O(1.5*M(N/2)) algorithm, where M(n) is the time to multiply
two numbers of n limbs. In the FFT multiplication range this grows to
a bound of O(6*M(N/2)). In practice a factor of about 1.5 to
1.8 is found in the Karatsuba and Toom-3 ranges, growing to 2 or 3 in the FFT
range.

The algorithm does all its calculations in integers and the resulting
`mpn_sqrtrem`

is used for both `mpz_sqrt`

and `mpf_sqrt`

.
The extended precision given by `mpf_sqrt_ui`

is obtained by
padding with zero limbs.