Next: FFT Multiplication, Previous: Toom 4-Way Multiplication, Up: Multiplication Algorithms [Index]

The Toom algorithms described above (see Toom 3-Way Multiplication,
see Toom 4-Way Multiplication) generalizes to split into an arbitrary
number of pieces. In general a split of two equally long operands into
*r* pieces leads to evaluations and pointwise multiplications done at
*2*r-1* points. To fully exploit symmetries it would be better to have
a multiple of 4 points, that’s why for higher degree Toom’n’half is used.

Toom’n’half means that the existence of one more piece is considered for a
single operand. It can be virtual, i.e. zero, or real, when the two operand
are not exactly balanced. By choosing an even *r*,
Toom-*r+1/2* requires *2r* points, a multiple of four.

The quadruplets of points include 0, *inf*, +1, -1 and
*+-2^i*, *+-2^-i* . Each of them giving shortcuts for the
evaluation phase and for some steps in the interpolation phase. Further tricks
are used to reduce the memory footprint of the whole multiplication algorithm
to a memory buffer equal in size to the result of the product.

Current GMP uses both Toom-6’n’half and Toom-8’n’half.