NTT multiplication.

[Niels Möller]

Aleksey Bader <bader at newmail.ru> writes:

> Let's fix n>m. In that case we usually
> make 3*fft(n+m). 3 - because we need to find u image, v image and recover
> u*v via inverse fft.
> If n/m is big enough then 3*fft(n+m) could be replaced with
> (2*n/m+1)*fft(2m) (I can't say how big should be n/m, maybe 3-4 goes well).
> It could be worth if m << n, i.e. we can consider v as "one large digit"
> that needed to be multiplied by n/m other digits.

How to do unbalanced multiplication is an area where GMP has been
improved recently, but where there is still much room for improvements.

Theoretically, n x m multiplication (n > m) ought to take time O(n log
m log log m), (or O(n log m log^* m) with Furer). When
n is much larger than m, the "one lage digit" method with n/m
multiplications each of size m x m is reasonable and it gets the right
asymptotic complexity, but it's not clear that it's really the best
way to do it.

One useful building block for unbalanced multiplication is unbalanced
toom. Say you have numbers of sizes close to 3n and 2n. View these as
polynomials of degree 2 and 1, respectively, with coefficients of size
n. Evaluate in 4 points each, multiply pointwise, and reconstruct the
product polynomial of degree 3. (Naturally, the same trick works well
for other combinations of low-degree polynomials). The pointwise
products would typically be close to balanced, and depending on size
they will be done by Schoolbok, Karatsuba, FFT, or something in
between.

This trick can be applied either directly, when the ratio of the
operand sizes is close to an appropriate ratio (3/2 for the above
method), or it can be iterated. E.g., in the scenario where n >> m,
one possible strategy is to do a series of n / (1.5 m)
multiplications, each of size 1.5m x m.

To find the optimal strategy for unbalanced multiplication is an open
research problem.

Regards,
/Niels