vincent at vinc17.net
Tue Dec 17 13:12:59 UTC 2013
On 2013-12-17 12:40:25 +0100, Torbjorn Granlund wrote:
> 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.,
> 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.
It seems that what Paul says is ambiguous (can be interpreted
> 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 think that Paul means that currently, due to the bug, it is not
possible to know how much space is needed, because GMP may end up
adding leading 0's.
> I don't think trimming the requirements to a or even b will be doable
> without either:
> 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
So, if I understand correctly, you consider that the current
documentation is incorrect and GMP's current behavior is the
Vincent Lefèvre <vincent at vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
More information about the gmp-bugs