В Харьковской ЗКШ 2011 была задача http://pastebin.com/cZbTuvbg
Вот мой код по ней, который я оптимизировал как только мог http://pastebin.com/X9ah6Ee4
И это решение получает ТЛ.
Я предподсчитал корни из 1, все операции со степенями двойки заменил на битовые.
Если использовать тип float то WA из-за точности, но в тайм вкладывается.
На практике Фурье в модульной арифметике работает дольше, так что пишу в комплексных числах.
Что еще можно оптимизировать в коде? Может что-то кардинально поменять?
Может я делаю какие-то лишние операции?
Вот мой код по ней, который я оптимизировал как только мог http://pastebin.com/X9ah6Ee4
И это решение получает ТЛ.
Я предподсчитал корни из 1, все операции со степенями двойки заменил на битовые.
Если использовать тип float то WA из-за точности, но в тайм вкладывается.
На практике Фурье в модульной арифметике работает дольше, так что пишу в комплексных числах.
Что еще можно оптимизировать в коде? Может что-то кардинально поменять?
Может я делаю какие-то лишние операции?
Все-равно таймит :(
Попытаюсь сегодня разобраться в способе, где делается 5 fft..
Я просто уже ничего ускорить не могу)
Вряд ли вы напишете его на соревновании :)
Схема Кули-Тьюки порядка 2 не является оптимальной, разумеется.
Кстати (в симметричной нормировке) дважды примененное прямое преобразование дает ту же самую последовательность, развернутую в обратную сторону ( F(F(X))[i] = X[-i], понимая последовательность как циклическую по модулю N, индексы с 0, т.е. 0 на месте).
Кстати 2. Если входной сигнал вещественный, можно ускорить преобразование Фурье в 2 раза.
Кстати 3. Если результат вещественный, можно ускорить преобразование Фурье в 2 раза (что-то вроде разности между вещественной и мнимой частью преобразования Фурье, взятого от последовательности (сумма вещественной и мнимой части начальной) ).
Надо просто уменьшить число коэфициентов в два раза, до 2N
Cпасибо! С этой оптимизацией и с 9-ми вызовами fft получил OK.
Кому интересно почему 9 вызовов:
обратное fft я использую только один раз в конце, а не на каждую букву отдельно. То есть, я суммирую значения четырех многочленов в точках-корнях из 1, а потом один раз делаю обратное быстрое преобразование Фурье, получаю массив-результат.
Нашел бы раньше этот разбор, поста бы не было :)
Хороший пост, не про "жену программиста". если бы небыло поста я бы не узнал этой фичи. И я бы не сдал эту задачу. кстати у меня зашло на e-olimp, с++ Максимальное время выполнения: 1.562 секунды из 2 секунды, 78.1%
9 fft на 2^m в целых числах
Если кому-то интересно, выложу код, спрашивайте.
Мы стараемся ставить ограничения по времени и памяти пожёстче. Одно дело - реальный 5-ти часовой контест, и другое - возможность посидеть, подумать сколько душе угодно и заняться оптимизацией алгоритма.
Сделано это исключительно в учебно-тренировочных целях.