sammyMaX's blog

By sammyMaX, history, 3 years ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it