perfect power / nth root improvements
arthur at ilvsun3.com
Mon May 19 04:57:15 CEST 2008
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.
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.
More information about the gmp-discuss