DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH
 

(gmp.info.gz) Square Root Algorithm

Info Catalog (gmp.info.gz) Root Extraction Algorithms (gmp.info.gz) Root Extraction Algorithms (gmp.info.gz) Nth Root Algorithm
 
 Square Root
 -----------
 
 Square roots are taken using the "Karatsuba Square Root" algorithm by
 Paul Zimmermann ( References).
 
    An input n is split into four parts of k bits each, so with b=2^k we
 have n = a3*b^3 + a2*b^2 + a1*b + a0.  Part a3 must be "normalized" so
 that either the high or second highest bit is set.  In GMP, k is kept
 on a limb boundary and the input is left shifted (by an even number of
 bits) to normalize.
 
    The square root of the high two parts is taken, by recursive
 application of the algorithm (bottoming out in a one-limb Newton's
 method),
 
      s1,r1 = sqrtrem (a3*b + a2)
 
    This is an approximation to the desired root and is extended by a
 division to give s,r,
 
      q,u = divrem (r1*b + a1, 2*s1)
      s = s1*b + q
      r = u*b + a0 - q^2
 
    The normalization requirement on a3 means at this point s is either
 correct or 1 too big.  r is negative in the latter case, so
 
      if r < 0 then
        r = r + 2*s - 1
        s = s - 1
 
    The algorithm 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, or as a variation on the schoolboy method (no longer
 taught) for square roots two digits at a time.
 
    If the remainder r is not required then usually only a few high limbs
 of r and u need to be calculated to determine whether an adjustment to
 s is required.  This optimization is not currently implemented.
 
    In the Karatsuba multiplication range this algorithm is
 O(1.5*M(N/2)), 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.
 
Info Catalog (gmp.info.gz) Root Extraction Algorithms (gmp.info.gz) Root Extraction Algorithms (gmp.info.gz) Nth Root Algorithm
automatically generated byinfo2html