Быстрое умножение многочленов при помощи преобразования Фурье

13 лет назад, # ^ |

Что конкретно про них написать?

→ Ответить

nk.karpov

13 лет назад, # ^ |

← Rev. 2 →

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

Тоесть как его писать и может время как оно работает на больших и средних n.

→ Ответить

13 лет назад, # ^ |

Не знал. Можешь рассказать поподробнее?

→ Ответить

nk.karpov

13 лет назад, # ^ |

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

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

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

Ну что-то в этом духе.

→ Ответить

Vaness

13 лет назад, # |

Было бы неплохо, если бы ты еще выложил ссылки, куда можно посдавать сам БПФ или задачи на него.

→ Ответить

13 лет назад, # ^ |

Там в комментах есть отличная задача на SPOJ.

→ Ответить

13 лет назад, # ^ |

чё-то не сдаётся она у меня - ТЛ, делаю ФФТ, разбив числа по два разряда, умножаю многочлены длины 150 к. кто-нибудь решил её?

→ Ответить

13 лет назад, # ^ |

Решили многие, к примеру Антон Лунёв, после чего разместил задачку с другими ограничениями у нас.

→ Ответить

13 лет назад, # ^ |

моё решение зашло.
Среднее время выполнения: 0.58 секунды
Максимальное время выполнения: 1.484 секунды из 4 секунды, 37.1%
Использовано памяти: 6000 KB из 65536 KB, 9.2%

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

Я эту задачу на spoj не решил. Плохое у меня FFT. В итеративной реализации из Кормэна большие прыжки по памяти. Дмитрий Жуков на зимней школе в Харькове рассказывал как круто его писать, чтоб не было прыжков по памяти.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

у меня рекурсия, но она не сильно проигрывает по времени моей итеративной реализации (тоже из-за прыжков по памяти). Не знаю как на SPOJ надо соптимизировать, чтобы заходило.

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

Когда я в свое время пытался сдать эту задачу, нашел такой сайт
http://www.fftw.org/index.html
Там, конечно, народ мегашарит в FFT. Но разбираться было сильно влом.
А вообще есть следующая идея, как ускорить FFT в два раза. Так как массивы вещественные, то можно работать только с одной половиной массива а вторая восстанавливается однозначно и очень легко по первой. Можно даже совсем все делать в вещественных и числах, но код жуткий получается. Так делал Виталий Неспирный в своей задаче с зимней школы
http://pastie.org/1879332
Можно попробовать эту идею.

→ Ответить

Ripatti

13 лет назад, # ^ |

=========================================
Погуглите преобразование Хартли. Я когда то давно писал - оно работает быстрее fft, во всяком случае, моего. Возможно, поможет.

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

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

P.S.: То же решение на e-olimp прошло за 750 ms

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Круто. Я как ни оптимизировал не могу сдать. Получается у вас в два раза быстрее работает FFT

UPD: а по сколько циферок били числа?

→ Ответить

KADR	13 лет назад, # ^ \| 0 Мой код проходит на e-olimp с максимальным временем 0.265, но на spoj получает ТЛ. → Ответить

13 лет назад, # ^ |

← Rev. 2 →

У нас тесты состоят из 1-го примера и ограничение по времени больше.
На spoj и ограничение по времени меньше и сами ограничения на входные данные больше, да плюс ещё и тесты - мультитестовые.
Значит нужно продолжать оптимизировать решение.

→ Ответить

KADR	13 лет назад, # ^ \| 0 ==================================== Странно просто, что решение которое проходит на spoj работает на e-olimp в 2.8 размедленнее моего, которое ТЛит на spoj. Может, разве что, у них куча маленьких тестов на которых мое решение очищает какие-то массивы лишний раз. → Ответить

13 лет назад, # ^ |

Попробуйте вместо double использовать long double - на spoj ограничения побольше и может возникать переполнение.

→ Ответить

KADR	13 лет назад, # ^ \| 0 ============================== Да нет, оно и так прошло. Правда за 2.98. Причем один и тот же код то получает ТЛ, то проходит на грани. Так что дело там не в переполнении. → Ответить

13 лет назад, # ^ |

Могу я увидеть ваше решение? Мое зашло на spoj за 2.67

→ Ответить

KADR	13 лет назад, # ^ \| 0 ====================== Вот код того решения. Сейчас я его поменял чтобы делалось 2 преобразования Фурье вместо трех, а так же небольшой предподсчет - теперь за 2.21 проходит. → Ответить

13 лет назад, # ^ |

Есть зеркала контестов Дмитрия Жукова как раз на эту тему из Зимней школы 2011 в Харькове: Высшая лига и Юниорская Лига - выбирайте задачки сами "на вкус" или по сложности.

→ Ответить

AlexSkidanov

13 лет назад, # |

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

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

→ Ответить

13 лет назад, # ^ |

Поле вычетов скоро тоже будет. По комплексным, мне кажется, проще рассказывать и понимать.

→ Ответить

e-maxx

13 лет назад, # ^ |

afaik в комплексных числах быстрее, чем в целых по модулю (хотя это и выглядит очень странно на первый взгляд)

→ Ответить

winger

13 лет назад, # ^ |

Все логично, арифметика по модулю сильно медленнее арифметики с плавающей точкой

→ Ответить

13 лет назад, # ^ |

когда я тестировал, моё решение в целых числах быстрее работало.

→ Ответить

Nyatl

13 лет назад, # ^ |

Как я понимаю, асболютная погрешность не должна превышать 0.5. При каких больших данных мы её получим?

→ Ответить

13 лет назад, # |

← Rev. 3 →

интересно, что твоя итеративная реализация со всеми примочками, описанная в статье, проигрывает моей рекурсивной по скорости процентов 10

→ Ответить

13 лет назад, # ^ |

Я заметил по результатам SPOJ :)
А какие еще оптимизации? Или просто код целиком по-другому написан?
Думаю, что посмотрю лекцию еще раз, когда приеду домой.

→ Ответить

13 лет назад, # ^ |

вот просто по-другому написан, без извратов.

→ Ответить

13 лет назад, # ^ |

Скачал и протестил. На многочлене степени 2¹⁸ у меня быстрее процентов на 20.
Скоро попробую на больших

→ Ответить

13 лет назад, # ^ |

видимо зависит от кеша процессора, чем больше массив тем медленее твоя реализация работает. вот код.

SIZE 65536 = 1 << 16

Iterative 46

Recursive 47

SIZE 131072 = 1 << 17

Iterative 94

Recursive 109

SIZE 262144 = 1 << 18

Iterative 250

Recursive 219

SIZE 524288 = 1 << 19

Iterative 563

Recursive 453

SIZE 1048576 = 1 << 20

Iterative 1156

Recursive 985

→ Ответить

13 лет назад, # ^ |

а тоже самое, но в целых числах работает на 25-30 % быстрее

→ Ответить

I_love_natalia

13 лет назад, # |

Я не заметил, вы делали учет вещественности и прочие фичи дня?

→ Ответить

13 лет назад, # ^ |

Нет. Приеду домой - собираюсь посмотреть лекцию из зимней школы и написать вторую часть.
Но вообще говоря я перед собой ставил цель показать, что это достаточно просто.

→ Ответить

I_love_natalia

13 лет назад, # ^ |

← Rev. 2 →

Учет вещественности - три строки кода в прямую (когда вход вещественный) и около 10 в обратную сторону (когда результат вещественный).
Разгоняет в два раза.

→ Ответить