Reflections on mulmod_bnm1
tg at gmplib.org
Wed Dec 9 23:09:42 CET 2009
Torbjorn Granlund <tg at gmplib.org> writes:
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.
I rewrote the next function again. Now I am convinced it is close to
optimal; some tune/speed plots helped.
mpn_mulmod_bnm1_next_size (mp_size_t n)
if (BELOW_THRESHOLD (n, MULMOD_BNM1_THRESHOLD))
if (BELOW_THRESHOLD (n, 4 * (MULMOD_BNM1_THRESHOLD - 1) + 1))
return (n + (2-1)) & (-2);
if (BELOW_THRESHOLD (n, 8 * (MULMOD_BNM1_THRESHOLD - 1) + 1))
return (n + (4-1)) & (-4);
nh = (n + 1) >> 1;
if (BELOW_THRESHOLD (nh, MUL_FFT_MODF_THRESHOLD))
return (n + (8-1)) & (-8);
return 2 * mpn_fft_next_size (nh, mpn_fft_best_k (nh, 0));
The tuneup code for MULMOD_BNM1_THRESHOLD is also not better.
More information about the gmp-devel