given 'n' polynomials to mupliply,
3+x 2x^2+2
take the first polynomials coefficients,
3+x --> 3, 1
add enough slack coefficients n^2,
3, 1 --> 3, 1, 0, 0
indexed 0 1 2 3
assign into odd & even partitions,
even --> 3,0 odd --> 1,0 indexed a,b
transform like so
given a,b --> (a+b,a-b)
hense --> 3,0 --> 3,3
hense --> 1,0 --> 1,1
introduce roots of unity,
"1 i -1 -i" --> 3, 1, 3, 1
use the even coefficients twice
transformation is now
'even --> even = even + unity'
'odd --> even = even - unity'
'--> 3 3 3 3
+ - + -
"1 i -1 -i"
--> 4 2
--> 3-i 3+i '
repeat on second polynomial
'2x^2 + 2 --> 2 + 0x + 2x^2 + 0
2,0,2,0 '
even --> '2,2 --> (2+2,2-2) --> 4,0'
odd --> '0,0 --> (0+0,0-0) --> 0,0'
even = '4 0 4 0'
multiply
' 4 3-i 2 3+i
- 4 0 4 0
= 16 0 8 0 '
even --> '16,8'
off --> ' 0,0'
'16,0,8,0'
inverse both
even --> 'a,b = (a+b)/2, (a-b)/2 = 24/2,8/2 = 12,4'
odd --> '0,0 = 0,0'
'x0,2 = e0+o0/2
x1,3 = e1-o0/2
12/2, 4/2, 12/2, 4/2
6 , 2, 6, 2 '
apply the magnitudes
x^0 + x^1 + x^2 + x^3
6 + 2x + 6x^2 + 2x3