Reflections on mulmod_bnm1

[bodrato at mail.dm.unipi.it]

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/