manpagez: man pages & more
info gmp
Home | html | info | man
[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

15.5.2 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.


This document was generated on March 31, 2014 using texi2html 5.0.

© manpagez.com 2000-2023
Individual documents may contain additional copyright information.