FFT vs Karatsuba: need help

Revision en1, by lis05, 2023-01-13 21:41:12

Hi guys. I've been trying to learn fast polynomial multiplication. I found that the most famous(probably?) algorithms are FFT and Karatsuba algorithm.

Karatsuba algorithm is pretty easy, but it is slow. I couldn't submit few problems because of TLE. Even if a submission passed, it was on the edge between AC and TLE.

On the other side, FFT is much faster but also much more complex. By complex I mean that it's hard to truly understand and implement it.

I need an advice: what should I do? Should I stick with Karatsuba algorithm and learn how to implement it better? Or should I make one more try to understand FFT? If yes, where is the best place to learn it without much pain?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English lis05 2023-01-13 21:41:12 750 Initial revision (published)