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 + x0Y(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=0x0 * y0, which gives w0 immediatelyt=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=infx3 * 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.