mpz_root aborts for n-th root when n is very large
Volker Lukas
vlukas at gmx.de
Sun Feb 27 23:53:26 CET 2011
Hi,
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,
100000000000).
More information about the gmp-bugs
mailing list