GNU Info

(gmp.info)Square Root Algorithm

---

Next: Nth Root Algorithm Prev: Root Extraction Algorithms Up: Root Extraction Algorithms

---

Enter node , (file) or (file)node

Square Root
-----------

   Square roots are taken using the "Karatsuba Square Root" algorithm
by Paul Zimmermann (Note: 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.