Replacement mpn/generic/mul.c

bodrato at bodrato at
Sun Dec 20 13:14:36 CET 2009

> 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.



More information about the gmp-devel mailing list