mpz_root aborts for n-th root when n is very large

Volker Lukas vlukas at
Sun Feb 27 23:53:26 CET 2011


On Sunday 27 February 2011, Marc Glisse wrote:
> > For x >= 2^n, the memory need is suddenly O(n) which isn't
> > unreasonable.
> > 
> > Do you agree?
> Yes.
> > Now, should we do something about this?  Should we check x < 2^n,
> > i.e. log(x) < n?
> It doesn't look like a very expensive check (and it doesn't even
> need to be tight). But then I have no idea how useful it would be.
> Maybe Volker could tell a bit more?
The idea in the software was, as far as I can tell from reading the 
code + comments, to test whether x^y results in an integer. For this y 
is represented as a fraction (as a mpq_t). So mpz_root is called with 
x and the denominator of y and it is tested whether the result is 
exact. So if you had for example 3^2.89278926071 y is 
289278926071/100000000000 and you were calling mpz_root(x, 3, 

More information about the gmp-bugs mailing list