Implements the proven optimal evaluation[1] and interpolation[2] sequences. Toom-3 is very efficient and requires only one small division and some small shifts. Because of this it can be used in any ring where 2 and 3 are invertible. This makes the algorithm particularly useful for large integer multiplication or for operations on polynomial rings with large enough characteristic. Two different formulas are given, for the balanced 3x3, and the unbalanced 4x2 cases. Both use the five evaluation points {0,-2,1,-1,1/0}.
On a specialized page you can find Toom 3 and other Toom formulas for binary rings.
Only evaluation phase differ, interpolation and recomposition are exactly the same.
Licence: GNU GPL.
Download: bt-3way-z-2.gp, bt-3way-4x2-z-2.gp, or bt-3way-z.gp, bt-3way-4x2-z.gp.
Reference:
[1]Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0 by Marco Bodrato
[2]What
About Toom-Cook Matrices Optimality? by Marco Bodrato and
Alberto Zanoni
[3]
High degree Toom'n'half for balanced and unbalanced multiplication by Marco Bodrato
The code below optimises both evaluation[1] and interpolation[2] sequences proposed for the 5-way asymmetrical squaring[3].
This code was optimised for the use of no temporaries, minimising the total number of operations[1], with a preference given to shifts against sum/subtraction. Ready for the GP-Pari interactive shell.
Comparison between classical and asymmetric squaring, splitting in four.
Licence: GNU GPL.
Download: bt-5way-squaring-z.gp, bt-4way-squaring-z.gp, bt-4way-toom-square-z.gp.
Reference:
[1]Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0 by Marco Bodrato
[2]What About Toom-Cook Matrices Optimality? by Marco Bodrato and Alberto Zanoni
[3]Asymmetric Squaring Formulae by Chung and Hasan (reprint of: Asymmetric Squaring Formulae)
Thanks to Paul Zimmermann and Jörg Arndt for useful hints and helpful codings.