sdssudhu's blog

Help With FFT
By sdssudhu, history, 6 years ago, In English

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

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

Can somebody help me to optimise it.

Thanks.

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

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah. In this case I did that to get AC. But how to improve it in general ??

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh sorry. I misunderstodd your first comment.

        And thanks for the pre-calculation parts.

        → Reply