perfect power / nth root improvements
arthur at ilvsun3.com
Wed May 14 00:24:47 CEST 2008
Howdy. I'm using GMP to generate and test a variety of numbers to see
if they are prefect powers. 98% of the run time of my program is spent
inside mpz_perfect_power_p, so it seems wise to spend time investigating
the efficiency of this portion of the code.
I read, regarding "Nth root"
Improve mpn_rootrem. The current code is really naive, using full
precision from the first iteration. Also, calling mpn_pow_1 isn't very
clever, as only 1/n of the result bits will be used; truncation after
each multiplication would be better. Avoiding division might also be
And then an exciting tidbit:
Work mostly done, see http://swox.com/gmp/development.html.
But on that page, I don't see anything related to Nth root.
I see root.c and rootrem.c here:
But nothing related here:
Are there any code updates or news regarding Nth root or perfect power
I see this note on the projects page:
mpz_perfect_power_p could be improved in a number of ways, for instance
p-adic arithmetic to find possible roots.
I'm considering investigating modifying this sample code to GMP calls:
Integer root extraction and perfect-power detection via p-adic
although I'm afraid that the overhead of all my mpz_ calls would put it
behind the efficiency of the current internal GMP algorithm.
More information about the gmp-discuss