Reflections on mulmod_bnm1

Torbjorn Granlund tg at
Wed Dec 9 10:05:11 CET 2009

bodrato at 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!


More information about the gmp-devel mailing list