Schonhage-Strassen (FFT-based integer multiplication) tutorial

Правка en1, от 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!

Теги fft, biginteger

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский sammyMaX 2018-11-25 08:37:33 768 Initial revision (published)