remains is to compute this matrix-vector product. Although the matrix contains fractions, the resulting coefficients will be integers — so this can all be done with integer arithmetic, just additions, subtractions, and multiplication/division by small constants. A difficult design challenge in Toom–Cook is to find an efficient sequence of operations to compute this product; one sequence given by Bodrato for Toom-3 is the following, executed here over the running example: {| |- |r0 || ← || r(0) || = || 3084841486175176 |- |r4 || ← || r(∞) || = || 12193131840 |- |r3 || ← || (r(−2) − r(1))/3 || = || (3188843994597408 − 13260814415903778)/3 |- | || || || = || −3357323473768790 |- |r1 || ← || (r(1) − r(−1))/2 || = || (13260814415903778 − (−246273893346042))/2 |- | || || || = || 6753544154624910 |- |r2 || ← || r(−1) − r(0) || = || −246273893346042 − 3084841486175176 |- | || || || = || −3331115379521218 |- |r3 || ← || (r2 − r3)/2 + 2r(∞) || = || (−3331115379521218 − (−3357323473768790))/2 + 2 × 12193131840 |- | || || || = || 13128433387466 |- |r2 || ← || r2 + r1 − r4 || = || −3331115379521218 + 6753544154624910 − 12193131840 |- | || || || = || 3422416581971852 |- |r1 || ← || r1 − r3 || = || 6753544154624910 − 13128433387466 |- | || || || = || 6740415721237444. |} We now know our product polynomial r: If we were using different km, kn, or evaluation points, the matrix and so our interpolation strategy would change; but it does not depend on the inputs and so can be hard-coded for any given set of parameters. Recomposition Finally, we evaluate r(B) to obtain our final answer. This is straightforward since B is a power of b and so the multiplications by powers of B are all shifts by a whole number of digits in base b. In the running example b = 104 and B = b2 = 108. {| |- | || || || || || || || ||3084||8414||8617||5176 |- | || || || || || ||6740||4157||2123||7444|| || |- | || || || ||3422||4165||8197||1852|| || || || |- | || |align=right| 13||1284||3338||7466|| || || || || || |- | + ||121||9313||1840|| || || || || || || || |- |colspan=100| |- | ||121||9326||3124||6761||1632||4937||6009||5208||5858||8617||5176 |} And this is in fact the product of 1234567890123456789012 and 987654321987654321098. Interpolation