# Karatsuba vs. Schönhage-Strassen for multiplication of polynomials

I am wondering how to most effectively multiply two polynomials with several $100$'s of coefficients, each coefficient having $1000$-$2000$ decimal digits.

I know Schönhage-Strassen begins to outperform Karatsuba between $10,000$ and $40,000$ digits. My question is, is SS not worth it because there are much less than $10,000$ coefficients, or is it worth it because a polynomial has more than $100,000$ digits total?

-

Here is a trick that I used a few times that allows you to multiply two integer polynomials using a single large integer multiplication. This way, you can avoid the division of your multiplication algorithm between the polynomial level and integer level.

Let $$p(x) = a_0 + a_1x + \cdots + a_mx^m, \quad q(x) = b_0 + b_1x + \cdots + b_nx^n,$$ be your two polynomials and let $$r(x) = p(x)q(x) = c_0 + c_1x + \cdots + c_{m+n}x^{m+n}$$ be the product to be computed.

To compute this product, first evaluate $P = p(2^k)$ and $Q = q(2^k)$ for some large enough $k$ and then compute the integer product $R = PQ$ (using Schönhage-Strassen since $P$ and $Q$ will be quite large). Note that $$R = r(2^k) = c_0 + c_12^k + \cdots + c_{m+n}2^{k(m+n)}.$$

If $k$ was chosen so that $|c_i| < 2^{k-1}$ for $i = 0, 1, \dots, m+n$, then we can recover $r(x)$ from $R$ as follows. Since $c_0 \equiv R \pmod{2^k}$ and $|c_0| < 2^{k-1}$, it follows that $c_0$ is the smallest absolute value number which is congruent to $R$ modulo $2^k$. Thus if $r_0$ is the (nonnegative) remainder of $R$ divided by $2^k$, then $c_0 = r_0$ when $r_0 < 2^{k-1}$ and $c_0 = r_0 - 2^k$ when $r_0 > 2^{k-1}$. Let $$R' = \frac{R-c_0}{2^k} = c_1 + c_2 2^k + \cdots + c_{m+n}2^{k(m+n-1)}$$ and repeat the same process to extract $c_1$ from $R'$, and so on until all the coefficients of $r(x)$ are recovered.

Note that evaluating $P = p(2^k)$, $Q = q(2^k)$ and recovering $r(x)$ from $R$ are very low cost on a binary computer since multiplication and division by powers of $2$ only involves shifting bits left and right. Furthermore, a suitable exponent $k$ can be chosen knowing only $p(x)$ and $q(x)$ — for example, it suffices to pick $k$ in such a way that $$\min(m,n)\max(|a_0|,|a_1|,\dots,|a_m|)\max(|b_0|,|b_1|,\dots,|b_n|) < 2^{k-1}.$$

-
This answer assumes that the coefficients of the polynomials are integers. I thought that was part of the question, but I now see that it wasn't... – François G. Dorais Aug 22 '11 at 21:48

Let's start remembering that there are other algorithms in between Karatsuba and SS: e.g. Toom, that can win in some interval.

I agree with Dorais, the Kronecker's trick (mapping multivariate to univariate polynomial, then polynomials to integers) can be worth trying, in particular if you already have a good library for integer arithmetic (e.g. GMP), and it applies mutatis mutandis also with coefficients in a field or ring Zn.

By the way, the exact threshold between Karatsuba, (Toom,) and SS heavily depend on implementation details (and CPU, caches, memory allocation...), but it is roughly connected to the total size of the result. I mean: it does not depend only on the size of coefficients, but on both coefficients and degree. In some sense, Kronecker's trick shows why.

-

If the bit length of the coefficients and the degree of the polynomial don't differ too much*, it is more efficient to directly run the DFT on the polynomial coefficients. Otherwise, the technique described by François (Kronecker substitution) is faster.

See page 4 of this presentation.

* - they need to be within roughly a factor of 2

-