Reflections on mulmod_bnm1

[Torbjorn Granlund]

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.

mp_size_t
mpn_mulmod_bnm1_next_size (mp_size_t n)
{
  mp_size_t nh;

  if (BELOW_THRESHOLD (n,     MULMOD_BNM1_THRESHOLD))
    return n;
  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.

-- 
Torbjörn