snacache's blog

FFT and overflows
By snacache, 8 years ago, In English

Hi everyone! I was recently doing some FFT-related problems, and I found a very interesting one.

It's from the CERC 2015 (problem F)

This problem involves many things from number theory, and one of them is doing some convolutions mod 106 + 3. After several WA, I found my error. The FFT algorithm produce many overflows after doing the convolution.

I know that FFT was one of the expected solutions, but how this issues can be handled? Is there a way to apply FFT with modular arithmetic?

Thanks!

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

NTT

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

This comment (in Russian) explains a way to do it. The idea is to split every number into two parts, such that each part is smaller than square root of modulus. After applying four convolutions using normal FFT (on small numbers, so there are no precision errors), you can get the result.

EDIT: Actually you need only 3 convolutions (just like in the Karatsuba algorithm).

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

    I just found the same article and got AC! It's an awesome way to solve these kind of problems.

    I had some bugs with precision though, had to use long double.

    Thanks!

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

    3 convolutions = 9 FFT? But you actually can calculate the whole product in just 4 FFT without reducing it to less amount of convolutions.

    So, you only have to calculate these:

    here means calculating Fourier transform for and simultaneously in one FFT considering polynomial .

    → Reply