Editing Toom–Cook multiplication (section)

=== Evaluation ===
The Toom–Cook approach to computing the polynomial product ''p''(''x'')''q''(''x'') is a commonly used one. Note that a polynomial of degree ''d'' is uniquely determined by ''d''&nbsp;+&nbsp;1 points (for example, a line - polynomial of degree one is specified by two points). The idea is to evaluate ''p''(·) and ''q''(·) at various points. Then multiply their values at these points to get points on the product polynomial. Finally interpolate to find its coefficients.

Since {{nowrap|1=deg(''pq'') = deg(''p'') + deg(''q'')}}, we will need {{nowrap|1=deg(''p'') + deg(''q'') + 1 = ''k''<sub>''m''</sub> + ''k''<sub>''n''</sub> − 1}} points to determine the final result. Call this ''d''. In the case of Toom-3, ''d''&nbsp;=&nbsp;5. The algorithm will work no matter what points are chosen (with a few small exceptions, see matrix invertibility requirement in [[Toom–Cook multiplication#Interpolation|Interpolation]]), but in the interest of simplifying the algorithm it's better to choose small integer values like 0, 1, −1, and −2.

One unusual point value that is frequently used is infinity, written ∞ or 1/0. To "evaluate" a polynomial ''p'' at infinity actually means to take the limit of ''p''(''x'')/''x''<sup>deg ''p''</sup> as ''x'' goes to infinity. Consequently, ''p''(∞) is always the value of its highest-degree coefficient (in the example above coefficient m<sub>2</sub>).

In our Toom-3 example, we will use the points 0, 1, −1, −2, and ∞. These choices simplify evaluation, producing the formulas:

:<math>
\begin{array}{lrlrl}
p(0) & = & m_0 + m_1(0) + m_2(0)^2 & = & m_0 \\
p(1) & = & m_0 + m_1(1) + m_2(1)^2 & = & m_0 + m_1 + m_2 \\
p(-1) & = & m_0 + m_1(-1) + m_2(-1)^2 & = & m_0 - m_1 + m_2 \\
p(-2) & = & m_0 + m_1(-2) + m_2(-2)^2 & = & m_0 - 2m_1 + 4m_2 \\
p(\infty) & = & m_2 & &
\end{array}
</math>

and analogously for ''q''. In our example, the values we get are:

:{|
|-
|''p''(0) || = || ''m''<sub>0</sub> || = || 56789012 || = ||align="right"| 56789012
|-
|''p''(1) || = || ''m''<sub>0</sub> + ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 + 78901234 + 123456 || = ||align="right"| 135813702
|-
|''p''(−1) || = || ''m''<sub>0</sub> − ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 − 78901234 + 123456 || = ||align="right"| −21988766
|-
|''p''(−2) || = || ''m''<sub>0</sub> − 2''m''<sub>1</sub> + 4''m''<sub>2</sub> || = || 56789012 − 2 × 78901234 + 4 × 123456 || = ||align="right"| −100519632
|-
|''p''(∞) || = || ''m''<sub>2</sub> || = || 123456 || = ||align="right"| 123456
|-
|''q''(0) || = || ''n''<sub>0</sub> || = || 54321098 || = ||align="right"| 54321098
|-
|''q''(1) || = || ''n''<sub>0</sub> + ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 + 43219876 + 98765 || = ||align="right"| 97639739
|-
|''q''(−1) || = || ''n''<sub>0</sub> − ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 − 43219876 + 98765 || = ||align="right"| 11199987
|-
|''q''(−2) || = || ''n''<sub>0</sub> − 2''n''<sub>1</sub> + 4''n''<sub>2</sub> || = || 54321098 − 2 × 43219876 + 4 × 98765 || = ||align="right"| −31723594
|-
|''q''(∞) || = || ''n''<sub>2</sub> || = || 98765 || = ||align="right"| 98765.
|}

As shown, these values may be negative.

For the purpose of later explanation, it will be useful to view this evaluation process as a matrix-vector multiplication, where each row of the matrix contains powers of one of the evaluation points, and the vector contains the coefficients of the polynomial:

: <math>
\left(\begin{matrix}p(0) \\ p(1) \\ p(-1) \\ p(-2) \\ p(\infty)\end{matrix}\right) =
\left(\begin{matrix}
0^0 & 0^1 & 0^2 \\
1^0 & 1^1 & 1^2 \\
(-1)^0 & (-1)^1 & (-1)^2 \\
(-2)^0 & (-2)^1 & (-2)^2 \\
0 & 0 & 1
\end{matrix}\right)
\left(\begin{matrix}m_0 \\ m_1 \\ m_2\end{matrix}\right) =
\left(\begin{matrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
1 & -1 & 1 \\
1 & -2 & 4 \\
0 & 0 & 1
\end{matrix}\right)
\left(\begin{matrix}m_0 \\ m_1 \\ m_2\end{matrix}\right).
</math>

The dimensions of the matrix are ''d'' by ''k''<sub>''m''</sub> for ''p'' and ''d'' by ''k''<sub>''n''</sub> for ''q''. The row for infinity is always all zero except for a 1 in the last column.

==== Faster evaluation ====
Multipoint evaluation can be obtained faster than with the above formulas. The number of elementary operations (addition/subtraction) can be reduced. The sequence given by Bodrato<ref name="Bodrato2007"/> for Toom-3, executed here over the first operand (polynomial ''p'') of the running example is the following:

:{|
|-
|''p''<sub>0</sub> || ← || ''m''<sub>0</sub> + ''m''<sub>2</sub> || = || 56789012 + 123456 || = ||align="right"| 56912468
|-
|''p''(0) || = || ''m''<sub>0</sub> || = || 56789012 || = ||align="right"| 56789012
|-
|''p''(1) || = || ''p''<sub>0</sub> + ''m''<sub>1</sub> || = || 56912468 + 78901234 || = ||align="right"| 135813702
|-
|''p''(−1) || = || ''p''<sub>0</sub> − ''m''<sub>1</sub> || = || 56912468 − 78901234 || = ||align="right"| −21988766
|-
|''p''(−2) || = || (''p''(−1) + ''m''<sub>2</sub>) × 2 − ''m''<sub>0</sub> || = ||align="right"| (− 21988766 + 123456 ) × 2 − 56789012 || = || − 100519632
|-
|''p''(∞) || = || ''m''<sub>2</sub> || = || 123456 || = ||align="right"| 123456.
|}

This sequence requires five addition/subtraction operations, one less than the straightforward evaluation. Moreover the multiplication by 4 in the calculation of ''p''(−2) was saved.