Schonhage-Strassen (FFT-based integer multiplication) tutorial

Revision en1, by sammyMaX, 2018-11-25 08:37:33

I recently wrote an article about Schonhage-Strassen on my personal blog here. It is an algorithm to multiply two N bit integers in time. If you want additional background on the signal processing stuff mentioned in the article, read the first part of the post here.

I doubt this will be useful for competitive programming because Schonhage-Strassen has a pretty high constant factor and is pretty tedious to implement--in general floating point FFT-based solutions are fine for competitive programming size inputs and NTT-based stuff like this is overkill. Hopefully some of you will still find it interesting though!

Tags fft, biginteger


  Rev. Lang. By When Δ Comment
en1 English sammyMaX 2018-11-25 08:37:33 768 Initial revision (published)