Replacement mpn/generic/mul.c

[bodrato at mail.dm.unipi.it]

> Using FFT(3n,n):
> Take 3n x n pieces, roughly m/(3n) times.
> Each 3n x n piece needs time O(M(4n)).
> Totally O(M(4n) m/(3n))
>
> Using toom63:
> Take 2n x n pieces, roughly m/(2n) times.
> Each 2n x n piece needs time O(8 M(n/3)).
> Totally O(M(n/3) 4m/n)
>
> The function M(n) is superlinear, so:
> M(n/3) 4m/n < M(4n/3) m/n < M(4n) m/(3n)
>
> So it seems toom63 is better.  Am I missing something?

I do not follow your computation, I look at the problem from another point
of view: is there any size vn such that toom63(2vn,vn) is slower than
FFT(2vn,vn)? If there isn't any, then you are probably right, and toom63
is good also for huge operands. Otherwise, it is FFT is better, above some
given threshold.

Regards,
Marco

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