perfect power / nth root improvements

[arthur]

Torbjorn Granlund wrote:
> The current code is O(M(n)(log n)^2),

> it is possible to do O(M(n)) in
> the worst case, or O(M(n/k)) on average, for computing the kth root of
> an n-bit number.

Is this the method outlined by Bernstein in: Detecting Perfect Powers In 
Essentially Linear Time?


 > >  Work mostly done, see http://swox.com/gmp/development.html.
 > Unfortunately, this is wrong.
 > We had a contribution, but we cannot use it for legal reasons.

Thats disappointing.

In my sadness, I got busy and implemented a padic root routine for 
perfect power testing that runs 20% faster than the current code up to 
inputs around 10^100, then it really improves.

Seconds to check numbers for being a perfect power.

starting   check   how many  seconds  seconds
at         this    perfect   w/ orig  w/ new
            many    powers    code     code
10^0    10,000,000   3395     8.94     7.28
10^10   10,000,000     51    11.11     8.17
10^100  10,000,000      1    43.98    37.23
10^1000    100,000      1    16.04     3.81
10^10000    10,000      1   385.76     7.79

I'm not familiar with the process of making code submissions.  I put the 
code and instructions here: www.ilvsun3.com/files/artroot.tar

It could easily be improved by implementing the root algorithm with GMP 
internal calls instead of calls through the high level interface (and 
better signed "mod" for mod powers-of-2).

I tested it against the current algorithm for the range of integers 
-2^30..2^30 and various large numbers with identical results.  I don't 
know if this is the best nth root algorithm to use as a long-term choice 
for GMP, but it seems to be working quickly and correctly.

/arthur