perfect power / nth root improvements
Paul Zimmermann
Paul.Zimmermann at loria.fr
Wed May 21 09:57:08 CEST 2008
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
More information about the gmp-devel
mailing list