Torbjorn Granlund tg at
Wed Mar 16 16:15:26 CET 2011

James Wanless <james at> 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

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.)


More information about the gmp-discuss mailing list