Дальнейшие обобщения

Полученный алгоритм умножения чисел представляет легко обобщить. Разобьем числа a и b на r частей, каждая из которых имеет длину . Для этого положим , , , где . В данных обозначениях и .

Заменим задачу умножения чисел a и b на задачу умножения многочленов и . Для вычисления произведения чисел a и b достаточно вычислить значение произведения этих многочленов в точке .

Для задания многочлена степени 2r достаточно знать его значения в -ой точке. В частности, многочлен w(x) полностью определяется равенствами w(i)=a(i)b(i), где . Для вычисления коэффициентов многочлена w(x) используем интерполяционный многочлен Ньютона. Интерполяционный многочлен в форе Ньютона записывается в виде , где - разделенная разность s-го порядка. Для вычислений всех разностей потребуется операций вычитания и деления на константу с числами длины . Вычисление значения многочлена по схеме Горнера . Умножение на скобку вида сводится к умножению на (или сдвигу на k разрядов), умножению на константу i и вычитанию. Трудоемкость каждой из перечисленных операций пропорциональна длине операндов. После выполнения этих операций длина результата увеличивается на k. Общая трудоемкость вычисления пропорциональна .

Из всего сказанного вытекает, что трудоемкость вычисления произведения чисел оценивается величиной , где - некоторая константа (вообще говоря, зависящая от программиста), а T(k) – трудоемкость умножения чисел длины k Если умножаем «столбиком», то и общая трудоемкость равна . При достаточно больших (тогда выполняется неравенство ) эта схема эффективней чем метод «столбиком». Для увеличения эффективности применим указанную схему к нахождению произведения , и так далее. В результате получим рекурсивный алгоритм умножения чисел.

Обозначим через трудоемкость этого алгоритма. Из сказанного выше следует формула . Положим . После многократного применения указанной схемы получим , где s удовлетворяет неравенствам , (откуда вытекает ). Свернем сумму по формуле суммы членов геометрической прогрессии . Заменив s соответствующими ограничениями, получим неравенство , где . Как следствие получается

Теорема. Для любого существует алгоритм умножения, трудоемкость которого ограничена величиной , где - константа, зависящая только от .

Доказательство. Выберем r удовлетворяющее неравенству . При таком выборе выполняется неравенство (r>1). Описанный выше алгоритм, с указанным выбором r, удовлетворяет условиям теоремы.