\\ (C) 2007-2008 Marco Bodrato <http://marco.bodrato.it/>
\\ This code is released under GNU-GPL 3.0 licence.
\\ Toom-4, evaluation-sequence for squaring,
\\ general interpolation with a hook for FFT recursion.

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

\\ P(x)[2]: P0=0; P1=1/2; P2=1; P3=-1; P4=2; P5=-2; P6=1/0
\\ Evaluation[1]: 8+3 add|sub, 5 shift, 7 sqr (n)
W0 = U1<<1
W3 = W0 + U3<<3 ; W2 = U0 + U2<<2
W1 = W3 - W2    ; W3 = W3 + W2

W4 =(W3)^2      ; W5 =(W1)^2

W2 = U0 + U2    ; W3 = U3 + U1
W1 = W3 - W2    ; W3 = W3 + W2
W0 =(W0 + U2 + U0<<2)<<1 + U3

W2 =(W3)^2      ; W3 =(W1)^2
W1 =(W0)^2
W6 = U3 ^2      ; W0 = U0 ^2

\\ Interpolation[2]: 18 add|sub, 6 shift, 2 Smul, 3 Sdiv (2n)
W1 = W1 + W4
W5 = W4 - W5
W4 = W4 - W0 - W6<<6
W4 =(W4<<1 - W5)>>3
W3 =(W2 - W3)>>1
W2 = W2 - W3

W1 = W1 - W2*65
W2 = W2 - W0 - W6
W1 = W1 + W2*45
W4 =(W4 - W2)/ 3
W2 = W2 - W4

W5 =(W1 - W5)/30
W1 =(W1 - W3<<4)/ 18
W3 = W3 - W1

\\ partial check (may be useful for FFT recursion)
(U^2) % (x^4+1) == (W0-W4) + (W5)*x + (W2-W6)*x^2 + W3*x^3

W5 =(W1 - W5)>>1
W1 = W1 - W5

\\ Recomposition: check
U^2 == W6*x^6 + W5*x^5 + W4*x^4 + W3*x^3 + W2*x^2 + W1*x + W0

\\ 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