IsPerfectPower
Torbjorn Granlund
tg at gmplib.org
Wed Mar 16 16:15:26 CET 2011
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
More information about the gmp-discuss
mailing list