(gmp.info.gz) Nth Root Algorithm

Info Catalog

(gmp.info.gz) Square Root Algorithm

(gmp.info.gz) Root Extraction Algorithms

(gmp.info.gz) Perfect Square Algorithm

 
 Nth Root
 --------
 
 Integer Nth roots are taken using Newton's method with the following
 iteration, where A is the input and n is the root to be taken.
 
               1         A
      a[i+1] = - * ( --------- + (n-1)*a[i] )
               n     a[i]^(n-1)
 
    The initial approximation a[1] is generated bitwise by successively
 powering a trial root with or without new 1 bits, aiming to be just
 above the true root.  The iteration converges quadratically when
 started from a good approximation.  When n is large more initial bits
 are needed to get good convergence.  The current implementation is not
 particularly well optimized.
 

Info Catalog

(gmp.info.gz) Square Root Algorithm

(gmp.info.gz) Root Extraction Algorithms

(gmp.info.gz) Perfect Square Algorithm