Memory usage for large multiplications

bodrato at bodrato at
Thu Jan 28 22:06:10 CET 2010


> The below patch changes the interface of mpn_mulmod_bnm1, and reduces
> the amount of temporary storage needed for mpn_nussbaumer_mul (used for

The patch has been refined, and some more memory was saved...

Unfortunately I don't have as much memory as Paul has, so that I can't
reproduce exactly his test, some estimates follow.

Let's call rn the length of the result, from the numbers that Paul
reported I guess that 2rn = 999,000,000. And GMP-4.3.2 allocates something
like 2.4rn for the product.
GMP-5.0 used 5rn, thanks to Niels' patch GMP-5.0.0-20100123 uses 4rn

With the last patches we have 3rn for balanced products and 3.5rn for
unbalanced. I expect, for the current code
max mmap bytes   = 2,760,000,000

It still is a 25% more than GMP-4.3.2...

Unfortunately  a temporary space of 2rn is allocated by mul_fft, this
function currently does not accept a scratch parameter, it is difficult to
further reduce memory usage without completely reorganising the code.

Can Paul confirm my estimate?

Best regards,


More information about the gmp-bugs mailing list