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 Schonhage–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.


You should double check with Modern Computer Algebra, p.238 - I believe the factors $\theta^j$ are evolving by adjoining "virtual" roots of unity, so that we compute a DFT in $R[x]/\langle x^n+1\rangle$ instead in $R[x]/\langle x^n - 1\rangle$. This is also the content of remark 2 in Modern Computer Arithmetic (you've cited above).

SSA isn't really a DFT - for a DFT you would need a principal root of unity. While DFT multiplication is based on cyclic convolution, SSA uses a negative wrapped convolution.

The algorithm 2.4 in Brent & Zimmermann is a SSA.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.