\\ (C) 2007 Marco Bodrato <http://marco.bodrato.it/>
\\ This code is released under GNU-GPL 3.0 licence.

U = U4*x^4 + U3*x^3 + U2*x^2 + U1*x + U0

\\ P(x)[3]: P0=(0); P1=P'(0); P2=(-1); P3=(1); P4=; P5=; P6=; P7=P'(1/0); P8=(1/0)
\\ Evaluation[1]: 12 add|sub, 3+2 shift; 5 mul, 4 sqr (n)
W0 = U0 - U3 ; W1 = U3 - U1 ; W6 = U1 - U2
W4 = U1 + U2 ; W5 = W6 - U4 ;
W3 = W5 + W0<<1
W0 = W0 - W5
W6 = W0 + W6<<1
W7 = W6 + W1
W5 = W7 + W1 ; W8 = W5 + W4<<1
W4 = W4 - U4

W2 =(W4)*(W3)
W4 =(W6)*(W5)    ; W3 =(W7)*(W1)
W1 = U0 * U1 * 2 ; W7 = U3 * U4 * 2

W5 =(W8)^2       ; W6 =(W0)^2
W0 = U0 ^2       ; W8 = U4 ^2

\\ Interpolation[1,2]: 16 add|sub, 3 shift (2n)
W6 =(W6 + W5)>>1
W5 = W5 - W6
W4 =(W4 + W6)>>1
W3 = W3 + W5>>1
W6 = W6 - W4
W5 = W5 - W3 - W1
W4 = W4 - W8 - W0
W3 = W3 - W7
W2 = W2 - W8 - W1 - W7 + W4 + W5
W6 = W6 - W2
\\ Recomposition:
W  = W8*x^8 + W7*x^7 + W6*x^6 + W5*x^5 + W4*x^4 + W3*x^3 + W2*x^2 + W1*x + W0
W == U^2 \\ check
\\print(if(W==U^2,"OK","NO"))

\\ 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] J. CHUNG and M.A. Hasan,"Asymmetric squaring formulae";
\\ Technical Report CACR 2006-24, University of Waterloo,
\\ Ontario, Canada, 2006