perfect power / nth root improvements

[Torbjorn Granlund]

From: Torbjorn Granlund <tg at swox.com>
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.

  On
  http://gmplib.org/projects.html
  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 
  possible.

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 http://swox.com/gmp/development.html.

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:
  http://gmplib.org/devel/mpz/

  But nothing related here:
  http://gmplib.org/devel/mpn/generic/

Indeed.

  Are there any code updates or news regarding Nth root or perfect power 
  improvements?

No, sorry.

-- 
Torbjörn