Длинная арифметика

Для всех ранее изученных алгоритмов требуется эффективная арифметика больших чисел (не умещающихся в регистры процессора).

Наиболее банальный способ представления больших чисел — последовательность цифр в какой-нибудь системе счисления (обычно с основанием \(2^{k}\), где \(k\) — разрядность процессора ЭВМ).

При таком представлении сложение чисел «в столбик» имеет сложность, пропорциональную максимальному количеству цифр складываемых чисел.

С умножением всё хуже — для умножения двух \(N\)-значных чисел «в столбик» вычислительная сложность составляет \(N^2\).

Сейчас мы рассмотрим простейший (и заодно — исторически первый) способ умножать числа быстрее, чем просто «в столбик».

Алгоритм Карацубы

Пусть \(d\) — основание используемой нами системы счисления и мы умножаем два \(2N\)-значных числа:

\[ (A d^N + B)\cdot (X d^N + Y) = AX d^{2N} + (AY + BX) d^N + BY \]

В 1960-м году А.А. Карацуба на одном из семинаров А.Н. Колмогорова заметил, что в вышенаписанном равенстве можно выбрать \(d=1\), что даст полезное соотношение

\[ AY+BX = (A+B)(X+Y) - AX - BY \]

То есть для нахождения всех цифр произведения можно использовать не четыре \(N\)-разрядных умножения и три \(2N\)-разрядных сложения, а три \(N\)-разрядных умножения, два \(2N\)-разрядных сложения и два \(N\)-разрядных сложения.

Пример

Вычислим алгоритмом Карацубы \(57\cdot 28\):

\[ \begin{aligned} 5\cdot2 & = 10 \\ 7\cdot8 & = 56 \\ 5\cdot8 + 7\cdot 2 & = (5+7)\cdot(2+8) - 10 - 56 = 12\cdot 10 - 66 = 120 - 66 = 54 \end{aligned} \]

Итого \(57\cdot 28 = 1000 + 540 + 56 = 1596\).