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?