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.

Marco Bodrato - 8 agosto 2011