Reflections on mulmod_bnm1
tg at gmplib.org
Wed Dec 9 10:05:11 CET 2009
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!
More information about the gmp-devel