### sdssudhu's blog

By sdssudhu, history, 5 weeks ago, ,

This is the snippet I have for FFT. But I feel it is slow in many cases.

One example is http://codeforces.com/problemset/submission/958/41610928 which takes nearly 3.85 seconds to pass for n=200000

Can somebody help me to optimise it.

Thanks.

•
• +5
•

 » 5 weeks ago, # |   +6 Since module is small (equal to 1009) in this task you don't need to use sqrt(MOD) hack and can manually multiply two polynoms (but don't forget to take resulting product modulo 1009 after each multiplification).
•  » » 5 weeks ago, # ^ |   0 Yeah. In this case I did that to get AC. But how to improve it in general ??
•  » » » 5 weeks ago, # ^ |   +3 In case of this problem, maybe I'm blind but I see you using fft_modulo instead of mul which is definetely use sqrt(MOD)-hack.Regarding optimizing in general case: I'm sure I've read many articles, but I can't find anything (maybe because they are on Russian). But standart trick are to precalc all roots (wlen and w in your code) — it gives boost with multiple using of mul. Precalcing bit reverse (or calculating it in the linear time) can give a little speed up.Anyway, you can always look at realization of fft from top participants if you have enough time and patience.
•  » » » » 5 weeks ago, # ^ |   0 Oh sorry. I misunderstodd your first comment.And thanks for the pre-calculation parts.