After brief intro to Fourier series, CFT, DFT and their basic properties I enjoyed implementing forward and backward FFT algorithm in complex numbers. I was happy to, at least, have an idea how is it possible that the algorithm works :)
But! My objective is to implement fast integer multiplication algorithm so I began to study The Schönhage–Strassen algorithm (well written here, page 56 of the book/page 72 of the pdf). Also in some other papers I found reference to weighting. And this is what bothers me now.
Why do we need to weight the polynomial coeficients ($a_j$ and $b_j$) with $\theta^j$ before the transformations and unweight the convoluted coeficients ($c_j$) with $K\theta^j$?
There was no weighting function in complex FFT. 'Only' a normalization factor $1/2$ in the backward FFT. I think I've missed some important point :(
I also wonder if the SSA algorithm presendet by Brent & Zimmermann is better/faster/more efficient than algorithm presented here (the approach suggested by Schönhage and Strassen).