As k grows, one may combine many of the multiplication sub-operations, thus reducing the overall computational complexity of the algorithm.
Although the exponent e can be set arbitrarily close to 1 by increasing k, the constant term in the function grows very rapidly.
[5] This section discusses exactly how to perform Toom-k for any given value of k, and is a simplification of a description of Toom–Cook polynomial multiplication described by Marco Bodrato.
Say the two integers being multiplied are: These are much smaller than would normally be processed with Toom–Cook (grade-school multiplication would be faster) but they will serve to illustrate the algorithm.
We then separate m and n into their base B digits mi, ni: We then use these digits as coefficients in degree-(k − 1) polynomials p and q, with the property that p(B) = m and q(B) = n: The purpose of defining these polynomials is that if we can compute their product r(x) = p(x)q(x), our answer will be r(B) = m × n. In the case where the numbers being multiplied are of different sizes, it's useful to use different values of k for m and n, which we'll call km and kn.
In this case the i in B = bi is typically chosen by: The Toom–Cook approach to computing the polynomial product p(x)q(x) is a commonly used one.
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: The dimensions of the matrix are d by km for p and d by kn for q.
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.
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.
A difficult design challenge in Toom–Cook is to find an efficient sequence of operations to compute this product; one sequence given by Bodrato[6] for Toom-3 is the following, executed here over the running example: 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.
Thus, the interpolation matrix is the identity matrix: Toom-1.5 (km = 2, kn = 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 is the same as Karatsuba multiplication, with an interpolation matrix of: Toom-2.5 (km = 3, kn = 2) requires 4 evaluation points, here chosen to be 0, 1, −1, and ∞.