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

Быстрое умножение многочленов при помощи преобразования Фурье — это просто
Автор yeputons, 15 лет назад, По-русски

Добрый вечер.
Пару дней назад опубликовал статью на Хабре про БПФ. Постарался объяснить и доказать всё без матриц (как на e-maxx), потому что не умею с ними еще работать на интуитивном уровне. Там точно также есть код и оптимизации (кстати, одной очень важной - прекалк корней, на e-maxx нет).
Если кому-нибудь помогло разобраться - буду рад.

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

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А про рекурсивный на больших + нерекурсивный на маленьких не собираешся написать?
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Что конкретно про них написать?
    → Ответить
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      По моему это тоже сильный оптимайз(посильнее предподсчёта корней) за счёт того как алгоритм работает с памятью.

      Тоесть как его писать и может время как оно работает на больших и средних n.
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Не знал. Можешь рассказать поподробнее?
        → Ответить
        • 15 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Ну схема примерно такая, когда мы шли в рекурсии мы делили массив, считали для того на что поделили, сливали результат в большой.

          Теперь давайте сделаем так устроим порядок как в нерекурсивном варианте, тогда мы можем просто считать для двух кусков и сливать.

          Но есть пара моментов из-за кэша такой вариант работает быстрее на больших n, ну а на маленьких лучше работает то, что без рекурсии. А в таком варианте слить эти две функции не очень сложно.

          Ну что-то в этом духе.
          → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Было бы неплохо, если бы ты еще выложил ссылки, куда можно посдавать сам БПФ или задачи на него.
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Там в комментах есть отличная задача на SPOJ.
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      чё-то не сдаётся она у меня - ТЛ, делаю ФФТ, разбив числа по два разряда, умножаю многочлены длины 150 к. кто-нибудь решил её? 
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Решили многие, к примеру Антон Лунёв, после чего разместил задачку с другими ограничениями у нас.
        → Ответить
        • 15 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          моё решение зашло.
          Среднее время выполнения: 0.58 секунды
          Максимальное время выполнения: 1.484 секунды из 4 секунды, 37.1%
          Использовано памяти: 6000 KB из 65536 KB, 9.2%
          → Ответить
        • 15 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Я эту задачу на spoj не решил. Плохое у меня FFT. В итеративной реализации из Кормэна большие прыжки по памяти. Дмитрий Жуков на зимней школе в Харькове рассказывал как круто его писать, чтоб не было прыжков по памяти.
          → Ответить
          • 15 лет назад, скрыть # ^ |
            ← Rev. 2  
            Проголосовать: нравится 0 Проголосовать: не нравится

            у меня рекурсия, но она не сильно проигрывает по времени моей итеративной реализации (тоже из-за прыжков по памяти). Не знаю как на SPOJ надо соптимизировать, чтобы заходило.
            → Ответить
            • 15 лет назад, скрыть # ^ |
               
              Проголосовать: нравится 0 Проголосовать: не нравится
              Когда я в свое время пытался сдать эту задачу, нашел такой сайт
              http://www.fftw.org/index.html
              Там, конечно, народ мегашарит в FFT. Но разбираться было сильно влом.
              А вообще есть следующая идея, как ускорить FFT в два раза. Так как массивы вещественные, то можно работать только с одной половиной массива а вторая восстанавливается однозначно и очень легко по первой. Можно даже совсем все делать в вещественных и числах, но код жуткий получается. Так делал Виталий Неспирный в своей задаче с зимней школы
              http://pastie.org/1879332
              Можно попробовать эту идею.
              → Ответить
              • 15 лет назад, скрыть # ^ |
                 
                Проголосовать: нравится 0 Проголосовать: не нравится
                =========================================
                Погуглите преобразование Хартли. Я когда то давно писал - оно работает быстрее fft, во всяком случае, моего. Возможно, поможет.
                → Ответить
              • 15 лет назад, скрыть # ^ |
                ← Rev. 3  
                Проголосовать: нравится 0 Проголосовать: не нравится

                Заинтриговали... :)
                FFT в комплексных числах (по идям Жукова с Зимней Школы 2011) зашло на SPOJ за 2.47 сек

                P.S.: То же решение на e-olimp прошло за 750 ms
                → Ответить
                • 15 лет назад, скрыть # ^ |
                  ← Rev. 2  
                  Проголосовать: нравится 0 Проголосовать: не нравится

                  Круто. Я как ни оптимизировал не могу сдать. Получается у вас в два раза быстрее работает FFT
                  UPD: а по сколько циферок били числа?
                  → Ответить
                • 15 лет назад, скрыть # ^ |
                   
                  Проголосовать: нравится 0 Проголосовать: не нравится
                  Мой код проходит на e-olimp с максимальным временем 0.265, но на spoj получает ТЛ.
                  → Ответить
                  • 15 лет назад, скрыть # ^ |
                    ← Rev. 2  
                    Проголосовать: нравится 0 Проголосовать: не нравится

                    У нас тесты состоят из 1-го примера и ограничение по времени больше.
                    На spoj и ограничение по времени меньше и сами ограничения на входные данные больше, да плюс ещё и тесты - мультитестовые.
                    Значит нужно продолжать оптимизировать решение.
                    → Ответить
                    • 15 лет назад, скрыть # ^ |
                       
                      Проголосовать: нравится 0 Проголосовать: не нравится
                      ====================================
                      Странно просто, что решение которое проходит на spoj работает на e-olimp в 2.8 размедленнее моего, которое ТЛит на spoj. Может, разве что, у них куча маленьких тестов на которых мое решение очищает какие-то массивы лишний раз.
                      → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится
    Есть зеркала контестов Дмитрия Жукова как раз на эту тему из Зимней школы 2011 в Харькове: Высшая лига и Юниорская Лига - выбирайте задачки сами "на вкус" или по сложности.
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Я спросил в личку, но что-то ты не ответил :о)

Для длинного умножения зачем использовать комплексные числа, а не поле вычетов? В первом случае есть не нулевой шанс напороться на погрешность, правильно?

 

→ Ответить
15 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

интересно, что твоя итеративная реализация со всеми примочками, описанная в статье, проигрывает моей рекурсивной по скорости процентов 10
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Я не заметил, вы делали учет вещественности и прочие фичи дня?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится
О преобразование Хартли можно прочитать в "Matters Computational" (Jörg Arndt).
→ Ответить