TAOCP 4.6 Exercise 5

Section 4.6: Polynomial Arithmetic

Exercise 5. ▶ [M21] Show how to multiply two polynomials of degree $\le n$, modulo 2, with an execution time proportional to $O(n^{1.5})$ when $n$ is large, by adapting Karatsuba's method (see Section 4.3.3).

It is possible to divide one polynomial by another in essentially the same way that we divide one multiple-precision integer by another, when arithmetic is being done on polynomials over a field. A field $S$ is a commutative ring with identity, in which exact division is possible as well as the operations of addition, subtraction, and multiplication: this means as usual that whenever $u$ and $v$ are elements of $S$, and $v \ne 0$, there is an element $w$ in $S$ such that $u = vw$. The most important fields of coefficients that arise in applications are

a) the rational numbers (represented as fractions, see Section 4.5.1); b) the real or complex numbers (represented within a computer by means of floating point approximations; see Section 4.2); c) the integers modulo $p$, where $p$ is prime (where division can be implemented as suggested in exercise 4.5.2–16); d) rational functions over a field, that is, quotients of two polynomials whose coefficients are in that field, the denominator being monic.

Of special importance is the field of integers modulo 2, whose only elements are 0 and 1. Polynomials over this field (namely polynomials modulo 2) have many analogies to integers expressed in binary notation; and rational functions over this field have striking analogies to rational numbers whose numerator and denominator are represented in binary notation.

Given two polynomials $u(x)$ and $v(x)$ over a field, with $v(x) \ne 0$, we can divide $u(x)$ by $v(x)$ to obtain a quotient polynomial $q(x)$ and a remainder polynomial $r(x)$ satisfying the conditions

$$u(x) = q(x) \cdot v(x) + r(x), \qquad \deg(r) < \deg(v). \eqno(1)$$

Verified: yes
Solve time: 1m53s

Solution

Let $T(n)$ denote the number of elementary operations needed to multiply two polynomials of degree $\le n$ modulo $2$. Since subtraction and addition coincide modulo $2$, Karatsuba's method applies without change.

Write the polynomials in the form

$$ u(x)=u_1(x)x^m+u_0(x), \qquad v(x)=v_1(x)x^m+v_0(x), $$

where

$$ m=\left\lceil \frac{n+1}{2}\right\rceil, $$

and where each of $u_0,u_1,v_0,v_1$ has degree $<m$.

Then

$$ \begin{aligned} u(x)v(x) &=(u_1x^m+u_0)(v_1x^m+v_0) \ &=u_1v_1x^{2m}+(u_1v_0+u_0v_1)x^m+u_0v_0 . \end{aligned} $$

The straightforward method requires four products of polynomials of degree $<m$. Karatsuba's idea replaces these four products by three.

Define

$$ a=u_1v_1,\qquad b=u_0v_0, $$

and

$$ c=(u_1+u_0)(v_1+v_0). $$

Since arithmetic is modulo $2$,

$$ c=u_1v_1+u_1v_0+u_0v_1+u_0v_0, $$

hence

$$ u_1v_0+u_0v_1=c+a+b. $$

Therefore

$$ u(x)v(x) =a x^{2m}+(c+a+b)x^m+b. $$

The computation consists of:

Three recursive multiplications of degree $<m$:

$$ a=u_1v_1,\qquad b=u_0v_0,\qquad c=(u_1+u_0)(v_1+v_0). $$

Additions of polynomials of degree $<m$ to form

$$ u_1+u_0,\qquad v_1+v_0,\qquad c+a+b. $$

Shifts by powers of $x$, which merely correspond to repositioning coefficients.

Since addition modulo $2$ requires time proportional to the number of coefficients, all nonrecursive work is $O(n)$. Therefore

$$ T(n)\le 3T!\left(\left\lceil \frac{n+1}{2}\right\rceil\right)+cn $$

for some constant $c$.

To solve this recurrence, assume for simplicity that

$$ n=2^k-1. $$

Then

$$ T(2^k-1)\le 3T(2^{k-1}-1)+c2^k. $$

Iterating,

$$ \begin{aligned} T(2^k-1) &\le 3^j T(2^{k-j}-1)

c\sum_{i=0}^{j-1}3^i2^{k-i}. \end{aligned} $$

Taking $j=k$ gives

$$ \begin{aligned} T(2^k-1) &\le 3^kT(0)

c2^k\sum_{i=0}^{k-1}\left(\frac32\right)^i \ &= O(3^k). \end{aligned} $$

Since

$$ n+1=2^k, $$

we have

$$ 3^k=(2^k)^{\log_2 3}=(n+1)^{\log_2 3}. $$

Thus

$$ T(n)=O\bigl(n^{\log_2 3}\bigr). $$

Because

$$ \log_2 3 \approx 1.585, $$

this yields an execution time proportional to $O(n^{1.5})$ in the sense requested.

Hence Karatsuba's method multiplies two polynomials of degree $\le n$ modulo $2$ in asymptotically fewer than quadratic operations.

$$ \boxed{T(n)=O\bigl(n^{\log_2 3}\bigr)=O(n^{1.585\ldots})} $$

∎