IsPerfectPower

[Torbjorn Granlund]

James Wanless <james at grok.ltd.uk> writes:

  > I thought the operation you asked for was computation of the nth
  > root of some (large) integer a given that it is known by the caller
  > that the exact result will be an integer.
  >
  > Was this what you mean?
  
  Yes, exactly, [thank you!!!] (this I _can_ say with confidence). But
  note that my method does not require to know or evaluate n in advance
  (I believe).

Huh?  I see the use of nowing if some number x is of the form a^b (for
integers a, b) but I cannot see any use for "please compute the nth
exact root of x for some unknown integer n, and return sensibly only of
there exists such an n"...
  
Our current mpz_root(x,b) is not super-fast.  Its (average and max) time
complexity is \Omega(M(x)), while it should be possible to construct an
algorithm that has average time complexity of \Theta(M(x^{1/b}log b)) or
somesuch.

A faster mpz_root for the exact case would be a nice addition to GMP.

(I will not have time for a longer discussion on this, now.  Others are
of course very welcome to continue.)

-- 
Torbjörn