Problems with mpz_set_str and huge strings

[Stefan Krah]

Torbjorn Granlund <tg at gmplib.org> wrote:
> Stefan Krah <stefan-usenet at bytereef.org> writes:
> 
>   I'm having memory corruption problems when using mpz_set_str for some huge
>   strings. Valgrind tracks down the problem to an invalid write in __gmpn_sub_n.
>   
> GMP only supports numbers of 2^31-1 bits or less on a 32-bit computer.
> Your number is greater than that.

Thanks for the explanation. Perhaps it's a good idea to publish the limits
more prominently (if anyone has time to work on the documentation). For
example, the main page currently says:

"There is no practical limit to the precision except the ones implied by the
 available memory in the machine GMP runs on."

This could be replaced by the actual limits. Then, in the manual the limits
could be added as a short subsection of "GMP Basics".


> Of course, GMP should catch oversize operands, print an error message
> and abort.  It does that for most overflows (starting with GMP 4.3) but
> unfortunately not all.  The difficulty is detecting overflow without
> adding overhead.
> 
> I assume you have tried larger and larger conversions until you ran into
> this limitation?  Your operands are just slightly above what GMP can
> handle, which make sens if you gradually increased your operands.

Not systematically. I tried to test my own 32 bit Karatsuba multiplication
with a number theoretic transform as the basecase against GMP. The transform
itself supports convolutions up to 905969664 decimal digits, so to test its
integration into Karatsuba I just used random operands large enough to
trigger the actual Karatsuba recursion.

It's a coincidence that the operands were close to the 32 bit GMP limit.


Stefan Krah