\\ (C) 2007-2011 Marco Bodrato
\\ This code is released under GNU-GPL 3.0+ licence.
U = U2*x^2 + U1*x*y + U0*y^2
V = V2*x^2 + V1*x*y + V0*y^2
\\ P(x,y)[3]: P0=(0,1); P1=(-2,1); P2=(1,1); P3=(-1,1); P4=(1,0)
\\ Evaluation[1]: 5*2 add/sub, 2 shift; 5mul (n)
W3 = U0 + U2 ; W2 = V0 + V2
W0 = W3 - U1 ; W4 = W2 - V1
W3 = W3 + U1 ; W2 = W2 + V1
W1 = W3 * W2 ; W2 = W0 * W4
W0 =(W0 + U2)<<1 - U0; W4 =(W4 + V2)<<1 - V0
W3 = W0 * W4
W0 = U0 * V0 ; W4 = U2 * V2
\\ Interpolation[2]: 8 add/sub, 3 shift, 1 Sdiv (2n)
W3 =(W3 - W1)/3
W1 =(W1 - W2)>>1
W2 = W2 - W0
W3 =(W2 - W3)>>1 + W4<<1
W2 = W2 + W1
\\ Early recomposition[3]:
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