Replacement mpn/generic/mul.c

[bodrato at mail.dm.unipi.it]

Sorry, the previous e-mail was unfinished...

> moreover I'd add another iterative block at lines 321-323 like
>  if (vn < MP_SIZE_T_MAX/8 && un >= 8*vn) {

..fill here a block similar to ToomXn, but using FFT

> } else

...the final FFT call.

We used the arbitrary condition (un >= 8*vn), then I'd suggest to iterate
mpn_fft_mul (prodp, up, 7*vn, vp, vn);

If we model the cost of FFT with M(a,b)=(a+b)*log(a+b)*log(log(a+b)), we
can compare the two costs M(14*vn,vn) and 2*M(7*vn,vn), and see that the
first is bigger than the second up to a quite big vn.
Above that, one should probably switch to some 2*M(10*vn,vn), and so on.
But, for the moment, I think we can accept a "suboptimal" algorithm for
operands that are both: very big, and very unbalanced.

Best regards,
Marco

-- 
http://bodrato.it/papers/