m0 || = || 56789012 || = ||align="right"| 56789012 |- |p(1) || = || p0 + m1 || = || 56912468 + 78901234 || = ||align="right"| 135813702 |- |p(−1) || = || p0 − m1 || = || 56912468 − 78901234 || = ||align="right"| −21988766 |- |p(−2) || = || (p(−1) + m2) × 2 − m0 || = ||align="right"| (− 21988766 + 123456 ) × 2 − 56789012 || = || − 100519632 |- |p(∞) || = || m2 || = || 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. Pointwise multiplication Unlike multiplying the polynomials p(·) and q(·), multiplying the evaluated values p(a) and q(a) just involves multiplying integers — a smaller instance of the original problem. We recursively invoke our multiplication procedure to multiply each pair of evaluated points. In practical implementations, as the operands become smaller, the algorithm will switch to schoolbook long multiplication. Letting r be the product polynomial, in our example we have: {| |- |r(0) || = || p(0)q(0) || = || 56789012 × 54321098 || = ||align="right"| 3084841486175176 |- |r(1) || = || p(1)q(1) || = || 135813702 × 97639739 || = ||align="right"| 13260814415903778 |- |r(−1) || = || p(−1)q(−1) || = || −21988766 × 11199987 || = ||align="right"| −246273893346042 |- |r(−2) || = || p(−2)q(−2) || = || −100519632 × −31723594 || = ||align="right"| 3188843994597408 |- |r(∞) || = || p(∞)q(∞) || = || 123456 × 98765 || = ||align="right"| 12193131840. |} As shown, these can also be negative. For large enough numbers, this is the most expensive step, the only step that is not linear in the sizes of m and n. Interpolation This is the most complex step, the reverse of the evaluation step: given our d points on the product polynomial r(·), we need to determine its coefficients. In other words, we want to solve this matrix equation for the vector on the right-hand side: This matrix is constructed the same way as the one in the evaluation step, except that it's d × d. We could solve this equation with a technique like Gaussian elimination, but this is too expensive. Instead, we use the fact that, provided the evaluation points were chosen suitably, this matrix is invertible (see also Vandermonde matrix), and so: All that