Reflections on mulmod_bnm1

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  It looked like a good idea at the time. But I agree it's a poor
  interface. mullo (at least some of the implementations) had the same
  issue, and in that case we chose an interface that doesn't require extra
  space at rp, and instead the function has to allocate whatever it needs.
  
I think mullo could perhaps allow itself to write all an+bn limbs, but
mulmod_bnm1 could be used in ways were such a thing would be very
surprising.

  > Should we perhaps pass and use tp for the mpn_mul_n result,
  
  It makes sense to me to at add scratch parameter tp. One might want to
  specify that rp and tp may point to the same area; that will save
  storage for all callers that compute rp into a scratch area anyway.
  
Good idea.

I leave this to Marco, or until Marco has expressed his opinion.

I checked in a new mpn_mulmod_bnm1_next_size, as well as a new speed
measruments type so that one can plot the jagged direct mulmod_bnm1 and
the next_size rounded mulmod_bnm1:

./speed -Pbar -s1-2000 mpn_mulmod_bnm1 mpn_mulmod_bnm1_next

A gnuplot of bar shows that things can still be improved, in particular
in the FFT range.  But things are much better than before my change!

  > (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...)
  
  Is it easy to check if a given n works with FFT? Then one can just check
  for this, like
  
        if (BELOW_THRESHOLD (n, MUL_FFT_MODF_THRESHOLD)
            || !valid_fft_size_p(n))
        	mpn_bc_mulmod_bnp1 (xp, ap1, bp1, n);
        else { ... do the fft thing ... }
  
  (then I guess this may also interact with the choice of the fft "k" in
  some interesting way).
  
I doubt this is a problem in practice, but we should keep it in mind.
We'll hit an ASSERT_ALWAYS if there is indeed a problem.

-- 
Torbjörn