perfect power / nth root improvements

[Paul Zimmermann]

       Arthur,

> Given integers N and R, the algorithm uses Newton iteration in a modular 
> fashion to to calculate an X for which X^R=N mod 2^(2^K) for smallest 
> 2^(2^K) > N^(1/R).  After calculating X, return true if X^R = N.

this modular usage of Newton's iteration is usually called Hensel lifting.
Note that you could also lift up to half the size of N^(1/R), and perform
a classical Newton's iteration for the upper half. In such a way, you would
perform two Newton/Hensel iterations of half-size, which should be faster
(this trick is usually known for exact division, but applies in many other
cases).

> Benefits of p-adic vs. floating point iterations:
> a) the exact number of iterations needed can be calculated precisely
> b) the number of p-adic digits of accuracy exactly doubles with each 
> iteration
> c) no divisions

which iteration do you use? Are you sure there is no MSB (most-significant-bit)
variant without division?

Paul Zimmermann