[ << ] | [ < ] | [ 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*.