Editing Toom–Cook multiplication (section)

==Interpolation matrices for various ''k''==

Here we give common interpolation matrices for a few different common small values of ''k''<sub>''m''</sub> and ''k''<sub>''n''</sub>.

=== Toom-1 ===
Applying formally the definition, we may consider Toom-1 (''k''<sub>''m''</sub> = ''k''<sub>''n''</sub> = 1). This does not yield a multiplication algorithm, but a recursive algorithm that never halts, as it trivially reduces each input instance to a recursive call with the same instance. The algorithm requires 1 evaluation point, whose value is irrelevant, as it is used only to "evaluate" constant polynomials. Thus, the interpolation matrix is the identity matrix:

: <math>\left(\begin{matrix}1\end{matrix}\right)^{-1} = 
\left(\begin{matrix}1\end{matrix}\right).</math>

=== Toom-1.5 ===
Toom-1.5 (''k''<sub>''m''</sub> = 2, ''k''<sub>''n''</sub> = 1) is still degenerate: it recursively reduces one input by halving its size, but leaves the other input unchanged, hence we can make it into a multiplication algorithm only if we supply a 1 × ''n'' multiplication algorithm as a base case (whereas the true Toom–Cook algorithm reduces to constant-size base cases). It requires 2 evaluation points, here chosen to be 0 and ∞. Its interpolation matrix is then the identity matrix:

: <math>\left(\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right)^{-1} =
\left(\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right).</math>

The algorithm is essentially equivalent to a form of long multiplication: both coefficients of one factor are multiplied by the sole coefficient of the other factor.

=== Toom-2 ===
Toom-2 (''k''<sub>''m''</sub> = 2, ''k''<sub>''n''</sub> = 2) requires 3 evaluation points, here chosen to be 0, 1, and ∞. It is the same as [[Karatsuba multiplication]], with an interpolation matrix of:

: <math>\left(\begin{matrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{matrix}\right)^{-1} =
\left(\begin{matrix}
1 & 0 & 0 \\
-1 & 1 & -1 \\
0 & 0 & 1
\end{matrix}\right).</math>

=== Toom-2.5 ===
Toom-2.5 (''k''<sub>''m''</sub> = 3, ''k''<sub>''n''</sub> = 2) requires 4 evaluation points, here chosen to be 0, 1, −1, and ∞. It then has an interpolation matrix of:

: <math>\left(\begin{matrix}
1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
0 & 0 & 0 & 1
\end{matrix}\right)^{-1} =
\left(\begin{matrix}
1 & 0 & 0 & 0 \\
0 & \tfrac12 & -\tfrac12 & -1 \\
-1 & \tfrac12 & \tfrac12 & 0 \\
0 & 0 & 0 & 1
\end{matrix}\right).</math>