\\ (C) 2007-2011 Marco Bodrato
\\ This code is released under GNU-GPL 3.0+ licence.
U = U3*x^3 + U2*x^2*y + U1*x*y^2 + U0*y^3
V = V1*x + V0*y
\\ P(x,y): P0=(0,1); P1=(2,1); P2=(1,1); P3=(-1,1); P4=(1,0)
\\ Evaluation[1]: 7+3 add/sub, 3 shift; 5mul (n)
W0 = U0 + U2 ; W4 = V0 + V1
W1 = U1 + U3 ; W2 = V0 - V1
W3 = W0 - W1
W0 = W0 + W1
W1 = W3 * W2 ; W2 = W0 * W4
W0 = U0 +(U1 +(U2 +U3<<1)<<1)<<1
W4 = W4 + V1
W3 = W0 * W4
W0 = U0 * V0 ; W4 = U3 * V1
\\ Interpolation[1,2]: 8 add/sub, 3 shift, 1 Sdiv (2n)
W3 =(W3 - W1)/3
W1 =(W2 - W1)>>1
W2 = W2 - W0
W3 =(W3 - W2)>>1 - W4<<1
W2 = W2 - W1
\\ Early recomposition[3] (save 0.5 sub):
W3 = W4*x + W3*y
W1 = W2*x + W1*y
W1 = W1 - W3
\\ Final recomposition:
W = W3*x^3+ W1*x*y^2 + W0*y^4
W == U*V
\\ References: http://bodrato.it/papers/#Toom-Cook
\\ [1] Marco BODRATO, "Towards Optimal Toom-Cook Multiplication
\\ for Univariate and Multivariate Polynomials in Characteristic
\\ 2 and 0"; "WAIFI'07 proceedings" (C.Carlet and B.Sunar, eds.)
\\ LNCS#4547, Springer, Madrid, Spain, June 2007, pp. 116-133.
\\ [2] M. BODRATO, A. ZANONI, "Integer and Polynomial
\\ Multiplication: Towards Optimal Toom-Cook Matrices";
\\ "Proceedings of the ISSAC 2007 conference", pp. 17-24
\\ ACM press, Waterloo, Ontario, Canada, July 29-August 1, 2007
\\ [3] Marco BODRATO, "High degree Toom'n'half for balanced and
\\ unbalanced multiplication"; "Proceedings of the 20th IEEE symposium
\\ on Computer Arithmetic", pp 15-22, Tuebingen, Germany, 2011