tg at gmplib.org
Tue Dec 17 11:40:25 UTC 2013
Zimmermann Paul <Paul.Zimmermann at inria.fr> writes:
it would make sense that mpn_set_str requires that the space allocated at RP
contains at least:
a = the exact number of limbs needed to store the input number,
or b = the number of limbs needed to store the maximal possible input number
of base BASE with STRSIZE chars, i.e., BASE^STRSIZE-1,
where of course a <= b.
The bug is that in some cases, the required space is even b + 1!
Almost. I think a+1 is the required allocation.
For example on a 64-bit computer with BASE=3 and STRSIZE=1815 limbs,
mpn_set_str might require up to 46 limbs, whereas 3^1815-1 has 45 limbs only.
As a consequence, it is not possible to know how much space needs to be
allocated at RP before calling mpn_set_str.
First you analyse the allocation requirements, then then you say such an
analysis is not possible. :-)
I don't think trimming the requirements to a or even b will be doable
1. slowing down the function (by e.g., split up the culprit mpn_mul call
into one mpn_mul and one mpn_addmul_1, or
2. making a large local allocation for the mpn_mul product.
To me, documenting a+1 as required allocation seem like the best
solution. (We need to read the sources to make sure a+1 is indeed
Please encrypt, key id 0xC8601622
More information about the gmp-bugs