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

Умножение целых чисел и , представленных в позиционной системе счисления по основанию p сводится к выполнению следующих действий.

1. Вычислим образ (естественно и - вектор, составленный из цифр числа a)

2. Вычислим образ ( - вектор, составленный из цифр числа b).

3. Перемножим компоненты векторов u и w. Результирующий вектор обозначим через c.

4. Вычислим прообраз (вектор c образован коэффициентами произведения многочленов ).

5. Нормализацией числа получим искомое произведение.

Ранее отмечалось, что задача нахождения прообраза сводится к задаче нахождения образа, например, по формуле . При вычислении образов u и w удобно использовать разложение матрицы быстрого преобразования Фурье, в котором матрица перестановок расположена слева. А при вычислении прообраза z лучше использовать разложение матрицы быстрого преобразования Фурье, в котором матрица перестановок стоит справа. При этом возникает возможность не выполнять сами перестановки, поскольку . Этот факт позволяет уменьшить трудоемкость и дает возможность реализовать быстрое преобразование Фурье с использованием списков, не привлекая структуру данных массив.

Если k+m не очень велико, то есть найдётся несколько простых чисел (естественно для которых возможно быстрое преобразование Фурье) больших k+m и убирающихся в ячейку, то можно вначале вычислить прообразы над полями вычетов, а затем на основании китайской теоремы об остатках восстановить z и далее действовать по плану. Реализация такого плана предпочтительней вычисления образа быстрого преобразования Фурье над полем комплексных чисел.

При использовании быстрого преобразования Фурье над полем комплексных чисел приходится использовать арифметику с фиксированной запятой. Число знаков после запятой определяется из следующих соображений.

Компоненты вектора z должны быть вычислены с точностью не меньше 0,5. Следовательно, компоненты вектора c должны быть вычислены с точностью (см. раздел «Анализ точности БПФ над полем комплексных чисел.»). Поскольку и , то компоненты векторов u и w достаточно вычислить с точностью . Для обеспечения требуемой точности достаточно все вычисления проводить с погрешностью . Для обеспечения требуемой точности придется добавить разрядов после запятой. Легко проверить, что длина максимального по абсолютной величине промежуточного результата ограничена такой же величиной. Если умножать промежуточные результаты столбиком, то общая трудоемкость метода составит (следует учесть, что при последовательном применении БПФ оценка понижается, например, до ).