perfect power / nth root improvements

Torbjorn Granlund tg at
Wed May 14 09:29:16 CEST 2008

From: Torbjorn Granlund <tg at>
Date: Wed, 14 May 2008 09:25:01 +0200

  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 

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.

  And then an exciting tidbit:
  Work mostly done, see

Unfortunately, this is wrong.

We had a contribution, but we cannot use it for legal reasons.

  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 

No, sorry.


More information about the gmp-discuss mailing list