Reflections on mulmod_bnm1
Torbjorn Granlund
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!
--
Torbjörn
More information about the gmp-devel
mailing list