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

FFT Problem Optimization
Автор Diguised, история, 10 лет назад, По-английски

Hi —

Recently I submit this solution to a polynomial FFT multiplication problem — POLYMUL.

Even on my computer — this solution runs very slow, and I cannot identify the reason. I'm wondering if anyone can assist in optimizing this solution — there must be something wrong for it to run so slowly.

Thanks in advance, Disguised

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

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

The main optimization you can do, in my opinion, is to set a higher base case threshold. That is, instead of evaluating the base case when there's only a single element left, use a O(N2) evaluation when the number of elements is less than 32 (32 is usually a good threshold ^^). In my experience (not only in FFT, but also in Karatsuba and the like) this makes a huge difference.

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

Start with getting rid of:

  1. push_back, it's O(1), but does reallocations. Pre-allocate memory (or just use vector.reserve).
  2. Recursive calls and allocations of memory, do everything in-place.
  3. complex<double> — it's slow somewhy, implement same class yourself.
  4. Replace two FFTs with one. FT of a + 0·i it's excessive, so no need to perform two separate transformations for a + 0·i and b + 0·i, do one for a + bi and then restore two results with some formulas.

I'm not sure that these are the most important, but they came to my mind first. By the way, here you can find FFT implementation from SPb SU 4's notebook.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    Looking at the std::complex implementation, I noticed that there are template specializations for standard types that use complex operations from the C language. Seems that it is slow because of additional function calls.

    I tested fft with the custom double "implementation" (i.e. a wrapper class around double with all operators overloaded) and std::complex and it shows the same perfomance with the custom complex class. But this implementation is even bigger than the one with the custom complex class, so it seems that it cannot be used to shorten the code.

    P.S. Maybe there is another way to override template specialization than creating the custom class, but don't know it.

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

    vector.preserve sounds interesting.

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

http://uoj.ac/problem/34/statistics

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

Please let me know if anyone can provide FFT and NTT implementations in JAVA?

→ Ответить