Next: Higher degree Toom'n'half, Previous: Toom 3-Way Multiplication, Up: Multiplication Algorithms [Index]
Karatsuba and Toom-3 split the operands into 2 and 3 coefficients, respectively. Toom-4 analogously splits the operands into 4 coefficients. Using the notation from the section on Toom-3 multiplication, we form two polynomials:
X(t) = x3*t^3 + x2*t^2 + x1*t + x0 Y(t) = y3*t^3 + y2*t^2 + y1*t + y0
X(t) and Y(t) are evaluated and multiplied at 7 points, giving values of W(t) at those points. In GMP the following points are used,
Point Value t=0 x0 * y0, which gives w0 immediately t=1/2 (x3+2*x2+4*x1+8*x0) * (y3+2*y2+4*y1+8*y0) t=-1/2 (-x3+2*x2-4*x1+8*x0) * (-y3+2*y2-4*y1+8*y0) t=1 (x3+x2+x1+x0) * (y3+y2+y1+y0) t=-1 (-x3+x2-x1+x0) * (-y3+y2-y1+y0) t=2 (8*x3+4*x2+2*x1+x0) * (8*y3+4*y2+2*y1+y0) t=inf x3 * y3, which gives w6 immediately
The number of additions and subtractions for Toom-4 is much larger than for Toom-3. But several subexpressions occur multiple times, for example x2+x0, occurs for both t=1 and t=-1.
Toom-4 is asymptotically O(N^1.404), the exponent being log(7)/log(4), representing 7 recursive multiplies of 1/4 the original size each.