(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
automatically generated byinfo2html