Алгоритм Шёнхаге-Штрассена для умножения целых чисел

[Nerazumovskiy]

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

Так вот у меня походу дела возник вопрос, зачем там применяеться преобразование фурьэ, там написано что это уменьшит количество умножений, но я както непонимаю всёже принципа роботи этого финта ушами. Может ктото обяснить поподробней?

[Xaositect]

Преобразование Фурье применяется для вычисления свертки (convolution). Дело в том, что операция свертки при применении преобразования фурье переходит в операцию покмпонентного умножения.
То есть получается вот что:
Если тупо вычислять свертку по формулам, то получится $\sim n^2$ операций.
Если сначала применить FFT ($\sim n\log n$), потом покомпонентно перемножить ($n$), а потом применить обратное FFT($\sim n\log n$), то операций будет $O(n\log n)$.

В алгоритме Ш-Ш для целых чисел свертка отрицательно обернутая, она вычисляется похожим образом, просто векторы коэффициентов умножаются на некоторые весовые векторы. (у Фюрера это называется Half-FFT)

[Nerazumovskiy]

А можете дать ссылку на книгу где этот Half-FFT нормально описан, ато тупо влоб закодить что написано у меня почемуто неполучаеться.

[Xaositect]

Ну можете еще второй том Кнута посмотреть.