gerasimovd's blog

By gerasimovd, 13 years ago, In Russian

Захотелось научиться писать БПФ без арифметики с плавающей точкой - начал изучать по этой статье. Вроде все более-менее понял, написал и даже кое-что работает, но остается непонятными несколько вещей:

Во-первых - пусть A = B*C(в смысле полиномов) и мы посчитали FFT(B), FFT(C). Все значения в этих массивах меньше модуля. Потом мы должны скалярно перемножить (FFT(B), FFT(C)) и применить обратное FFT. Но когда мы перемножим - не все элементы этого массива уже будут меньше модуля - что с этим делать? просто брать их по тому же модулю и считать обратное? Если я так делаю, у меня начинает все неправильно работать(из-за таких переполнений), числа длиной около тысячи знаков умножаются правильно только при базе 10 или 100, что очень печально.
Во-вторых - пусть после FFT у нас получилось: FFT(A) = (1, 3), FFT(B) = (4, 0). После того как мы скалярно перемножим, у нас получится (4, 0), и после обратного FFT мы получим тот же B. Такое бывает(может я не понял чего-то в теории), и если да - что делать?
И последнее - модуль в статье на e-maxx подходит для случая, когда в векторе не более 2^20 элементов. Вряд ли мне понадобится больше - но вопрос - а где-то есть готовые последовательности типа "модуль - образующий элемент" ?. На oeis - только для небольших чисел, можно конечно прочитать и познать еще один алгоритм - но очень уж лень :)
Кстати - мне кажется, или на e-maxx единственная статья про целочисленное БПФ в интернете? Если есть еще что почитать(на русском или английском), очень буду рад ссылкам.
upd: еще на всякий случай код
  • Vote: I like it
  • +19
  • Vote: I do not like it