Multiplication Algorithms

Multiplication

How do we multiply numbers?

Assume that we the input representation of a number is in decimals. How can we compute the product of two numbers?

1) Grid Method: Split both the factors into units, tens, hundreds etc, multiply all of these parts separately and then add them together.

2) Long Multiplication: Multiply the first number with each digit of the second number and take the sum of the resulting numbers with appropriate shifts. Multiplying each digit is carried by looping for all the digits of the first number, multiplying and using “carries” for previous computations.

3) Karatsuba algorithm:

We can save one of 4 multiplications needed by using the following formulae:

$\displaystyle x=x_{1} 10^{m}+x_{0}$
$\displaystyle y=y_{1} 10^{m}+y_{0}$

$\displaystyle \begin{aligned} x y &=\left(x_{1} 10^{m}+x_{0}\right)\left(y_{1} 10^{m}+y_{0}\right) \\ &=z_{2} 10^{2 m}+z_{1} 10^{m}+z_{0} \end{aligned}$

$\displaystyle \begin{array}{l} z_{2}=x_{1} y_{1} \\ z_{1}=x_{1} y_{0}+x_{0} y_{1} =\left(x_{1}+x_{0}\right)\left(y_{1}+y_{0}\right)-z_{2}-z_{0}\\ z_{0}=x_{0} y_{0}\\ \end{array}$

$\displaystyle T(n)=3 T(\lceil n / 2\rceil)+c n+d \implies T(n)=\Theta\left(n^{\log _{2} 3}\right)$

4) Toom-Cook multiplication:

Toom- ${k}$ : Input : Two non-negative integers ${a}$ and ${b}$ of length at most ${n.}$

Splitting:
Write $\displaystyle \begin{array}{l} a=a^{(0)}+a^{(1)} \cdot 10^{m}+\cdots+a^{(k-1)} \cdot 10^{(k-1) \cdot m} \\ b=b^{(0)}+b^{(1)} \cdot 10^{m}+\cdots+b^{(k-1)} \cdot 10^{(k-1) \cdot m} \end{array}$ ${m:=\lceil n / k\rceil}$ and integers ${a^{(i)}, b^{(i)}}$ of length at most ${m}$
Evaluation
${p(x):=a^{(0)}+a^{(1)} \cdot x+\cdots+a^{(k-1)} \cdot x^{k-1}}$
${q(x):=b^{(0)}+b^{(1)} \cdot x+\cdots+b^{(k-1)} \cdot x^{k-1}}$
Compute ${p(x_i), q(x_i)}$ for ${2k-1}$ distinct points ${x_i}$
Pointwise Multiplication
Compute ${r(x_i) =p(x_i).q(x_i)}$ recursively!
Interpolation
Interpolate ${r(x_i}$ to find the polynomial ${r(x) = p(x)q(x).}$ This can be done by inverting the vandermonde determinant.
Recomposition
$\displaystyle T(n) \leq(2 k-1) \cdot T(\lceil n / k\rceil)+O(n) \implies T(n)= O(n^{\frac{\log (2 k-1)}{\log k}})$

5) FFT Methods:
Interpolation, Evaluation steps are costly. Similar to the Tim-Cook but we evaluate the polynomials at ${\zeta_l^i}$ , where ${\zeta_l}$ is the ${\ell}$ -th principal root of unity. This choice reduces the cost of the interpolation, evaluation. This computation can be happen over any ring with ${\ell}$ -th principal root of unity.

Over complex numbers, over finite fields or over ${\mathbb{Z}/n}$ for ${n}$ of a special forms like Fermat’s number ${n=2^k+1}$ or Mersenne Number ${n=2^k-1.}$

6) Schonhage- Strassen algorithm: FFT over the ring ${\mathbb{Z} /\left(2^{n}+1\right) \mathbb{Z}}$ , and ${l =2^k | n}$ ${2^{n / \ell} \equiv-1 \left(\bmod ~2^{n}+1\right)}$
Allows for negativecyclic convolution (Weighted FFT): Compute ${C(x)=A(x) B(x) \bmod x^{\ell}+1}$