Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.