perfect power / nth root improvements

arthur arthur at
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

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 
Newton-Hensel lifting

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 mailing list