Reflections on mulmod_bnm1
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Wed Dec 9 09:39:19 CET 2009
Ciao,
> 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.
> "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?
> One more warning: in the mul_fft call above it may happen that an < bn.
> I know an advanced algorithm for resolving such a problem if it occurs.
> It needs a few cycles, but since we're about to spend tens of thousands
> of cycles, that's not too much overhead.
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!
Regards,
Marco
--
http://bodrato.it/papers/
More information about the gmp-devel
mailing list