Reflections on mulmod_bnm1

[Torbjorn Granlund]

bodrato at mail.dm.unipi.it writes:

  > Why don't you call mpn_fft_best_k + mpn_fft_next_size?
  
  The value of n can not be changed, if I'm in the middle of recursions I
  need the product mod (B^n+1) with a _given_ n. The only possible choice
  is, using FFT or basecase with that _fixed_ n.
  
Eh, of course.

  > "Works", yes, but with a suboptimal k.  (I.e., too short transform, too
  > large coefficients.  It might be more like Toom...)
  
  But Toom does not give its result mod B^n+1 :-)
  It is not a "suboptimal" k... it is the "best" k one can use, with the
  _given_ n. Maybe one should use basecase if k was reduced too much?
  
Yes, I think one should definitely go to the basecase when "too much"
happens.  It is not immediately evident which exact criteria to use for
too much, though.

Using the the FFT_TABLEs (FFT_TABLE2 is it exists, else FFT_TABLE) does
not give the solution; they can tell us if we're in an ideal situation.
But we know we're not already, if we've decremented k.  But just that we
decremted k does not mean the basecase will be faster, for sure.

I suppose we really need some wondrous new thresholds.  A table indexed
by k (small k, say < 10 should be enough) giving the n where to switch
to FFT, for properly aligned n.

  Oh, no... the coordinator of the project does not like branches, he says
  that _any_branch_is_too_much_ if it is not strictly needed!
  I guess that any FFT implementation will transform its two operands
  independently, without any restriction on their relative sizes.
  
  Beware, future implementors of FFT!
  
Now, this discussion is really branching out!

-- 
Torbjörn