Фурье в суррогтаных полях, практическое применение Опции

[Major]

Наткнулся на работу 1983 Галкин, Желуковский "Машинный алгоритм преобразования фурье без ошибок округления".
Используется поле GF для чисел Мерсенна.
Развернуто нашел у Ричарда Блейхута (жаль у него нет новы изданий с учетом современных реалий).

Но практических работ использующих отображение в поле целых чисел не нашел.
Это игра ума, или современные реализации на double или double double плюс FMA убивают смысл затеи?
Есть корефеии, заставшие эту тему?

P.S. Про Блейхута ошибся, в 2010 вышла новая версия "Fast Algorithms for Signal Processing"

[Pavia]

Тут эксперты получше меня. Объясняю как я понимаю.

Это обычные длинные числа. Проблемо в том что на каждом умножении они удваеваются. Откуда имеем скорость работы O((N^2)Log^2(N)) и потребление памяти O(N*2^(N*Log(N)))
Для N=8 вам потребуется 1 Гб при 9 около 4 Гб. Поэтому и неприменяют.

Далее вы начинаете использовать дроби и их сокращение.
Это вам позволит сократить память и продержаться до N=100.
В книге есть приписька по этому поводу сокрощения. Но никто нетестировал.

Затем вы решаете перейти на поле вычетов. Это экономит память.
Но вконце надо делать обратное преобразование. А это умножение
серии длинных чисел. Сильно ничего не выигрываете.

В любом случае ответ усекать. Числа. Откуда приходим к реальным числам. С фикированной или плавающей.
Для float есть теория о точности вычисления.

Вот тут можно посмотреть про оценку точности свёртки для double
http://www.daemonology.net/tricl/

[Major]

Про умножение и памяь не очень понял.
Попробую сам, возможно ошибаюсь.
Нам требуется выбрать число p такое, чтобы результат свертки был меньше этого p.
Если есть две последовательности длиной N, состоящие из чисел M, то макс коэф. будет равен N*M^2.
Если для M надо q разрядов, то слово памяти должно быть равно 2*q+log2(N).
M=65535, N=1024 => 32+10=42 бита.
Для вычисления (через фурье) надо памяти порядка O(N).
Если заранее знать одну из последовательностей, то оценка на максимальное число бит в результате может быть лучше.
Промежуточные значения у нас по модулю p в поле GF(p), и их переполнение не влияет на результат.

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

[krasava329]

Я б сказал что из минусов только ручная работа.