GNU Info

(gmp.info)Nth Root Algorithm

---

Next: Perfect Square Algorithm Prev: Square Root Algorithm Up: Root Extraction Algorithms

---

Enter node , (file) or (file)node

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.