15.1.5 Higher degree Toom’n’half

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 four-plets 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 equanl in size to the result of the product.

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