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

Volker Lukas vlukas at
Sun Feb 27 23:27:47 CET 2011


On Sunday 27 February 2011, Torbjorn Granlund wrote:
> Marc Glisse <marc.glisse at> writes:
>   ... the function mpn_rootrem(_internal) indeed calls
> TMP_ALLOC_LIMBS with an argument linear in k.
> OK, computing a high root of 1 will ask for undue of memory.
Ok, thanks for looking into this (and thank you Marc for confirming my 

> I'd claim that computing the nth root of x, x < 2^n is somewhat
> strange, since the result is always 1.
> For x >= 2^n, the memory need is suddenly O(n) which isn't
> unreasonable.
> Do you agree?
> Now, should we do something about this?  Should we check x < 2^n,
> i.e. log(x) < n?
I am inclined to say that it could be helpful if the GMP manual had a 
bit more to say on memory consumption, so that users of this function 
could know whether a certain combination of arguments is 
"pathological" and can avoid calling this function then.

More information about the gmp-bugs mailing list