Блог пользователя snacache

FFT and overflows
Автор snacache, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

NTT

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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!

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 .

    → Ответить