Replacement mpn/generic/mul.c
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Sun Dec 20 12:53:21 CET 2009
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/
More information about the gmp-devel
mailing list