Reflections on mulmod_bnm1

Torbjorn Granlund tg at
Tue Dec 8 20:20:04 CET 2009

First some questions:

When the basecase function mpn_bc_mulmod_bnm1 is invoked, it writes 2rn
limbs to rp.  This is an unexpected interface, it might be far outside
the result area.  Is this intended?  Should we perhaps pass and use tp
for the mpn_mul_n result, then let mpn_add (which should BTW be
mpn_add_n) write to rp?

About the next interface:

Clearly, the current next function is very silly, I wrote it, so please
don't take offence :-).  Even close to the MULMOD_BNM1_THRESHOLD, we
round to a multiple of 16.  Such rounding does not allow for more mulmod_bnm1
calls, it just increases the basecase size.

Perhaps we should do something like this:

Rounding MULMOD_BNM1_THRESHOLD should be be done.

Else, rounding within 2 * MULMOD_BNM1_THRESHOLD should be to the next
multiple of 2.

Else, rounding within 4 * MULMOD_BNM1_THRESHOLD should be to the next
multiple of 4.

Else, rounding within 8 * MULMOD_BNM1_THRESHOLD should be to the next
multiple of 8.

Else if less than MUL_FFT_MODF_THRESHOLD round to the next multiple of 16.

Else round with mpn_fft_next_size.


(There is a potential error in this algorithm, which is also present in
the current next function: The non-FFT rounding might bring an n smaller
than MUL_FFT_MODF_THRESHOLD into the FFT range.  This could then be
insufficiently rounded for FFT...)


More information about the gmp-devel mailing list