Умножение в столбик.

С умножением дело обстоит не так просто, как с операциями сложения и вычитания. Дело в том, что известный нам со школы алгоритм умножения “в столбик” не самый быстрый. Вот он.

Алгоритм 1.3. Умножение «в столбик» длинных чисел С = А*В

длины n цифр

1.       C := 0; (достаточно обнулить n младших цифр)

2.       для i = 0 … n-1 выполнить шаги 3-8;

3.       d :=0;

4.       для j = 0 … n-1 выполнить шаги 3-5;

5.       T :=Ci+j + Ai*Bi +d;

6.       Ci+j : = LODIGIT(T);

7.       d := HIDIGIT(T);

8.       Ci+n := d;

9.       конец.

Обратите внимание на то, что результат операции умножения в общем случае в 2 раза длиннее сомножителей, то есть имеет длину 2n цифр. Нетрудно видеть, что описанный алгоритм требует выполнения n операций умножения и еще некоторого количества операций сложения. И именно так умножали люди с давних времен, пока 39 лет назад московским математиком А.А. Карацубой не было совершено неожиданное открытие. Он придумал куда более эффективный метод.

Метод Карацубы

Пусть А и В — два n-значных длинных числа и n – четное. Эти числа можно представить в виде

А = bn/2U1 + U0, B = bn/2V1 + V0,

где U0, U1,V0,V1 — n-значные числа. Обычное умножение “в столбик” равносильно следующему:

АЧВ = (bn/2U1 + U0)(bn/2V1 + V0 ) = bnU1V1+ bn/2 (U1V0 + U0V1) + U0V0,

те. требует выполнения 4 операций умножения -значных чисел.

Однако, воспользовавшись тождеством

(U1 - U0) (V0 -V1) = -U1V1-U0V0+ U1V0+U0V1,

получаем

АЧВ=(bn/2U1+U0)(bn/2V1+V0 )=(bn+ bn/2)U1V1+ bn/2(U1 - U0)(V0 -V1)+(bn/2+1)U0V0.

При этом умножение n-значных чисел потребует выполнения З операций умножения-значных чисел и еще некоторое количество операций сложения и вычитания. Итак, налицо выигрыш  по сравнению с умножением в столбик. Но поскольку и умножение -значных чисел тоже можно выполнять таким же образом, организован рекурсивный вызов процедуры умножения и т.д., то теоретически получим сложность около n1.6 элементарных умножений, а не n2, как раньше.

На практике не все столь радужно, как показалось. При малых значениях n скорее всего можно проиграть на накладных расходах (организация рекурсии и циклов, дополнительные операции вычитания, трудности с учетом знака результата и т.п.). Практические вычисления показали, что реальный выигрыш наступает при разрядности операндов где-то около 16384 битов, что не может интересовать, поскольку ГОСТ Р 34.10-94 регламентирует длину модуля не более 1024, да и в реальной практике пока модулярные вычисления с разрядностью выше 2048 битов используются редко. А по сему реализацию этого метода рассматривать здесь не будем.

Интересующимся же заметим, что метод Карацубы был в 1963 году обобщен А. Тоомом, который нашел связь этой задачи с интерполяционными полиномами. И еще более продвинулись в решении задачи умножения А. Шенхаге и Ф. Штрассен, которые помимо интерполяционных полиномов использовали быстрое преобразование Фурье и построили алгоритм умножения с числом элементарных операций умножения не более О(nЧlog nЧlog log n). Однако, как и метод Карацубы, эти алгоритмы слишком сложны в реализации и дают практический выигрыш только при очень большой разрядности сомножителей.

Умножение на цифру

Далее при делении понадобится функция умножения «длинного» n-значного числа на цифру. В принципе, можно поступить просто и обратиться к алгоритму умножения, предварительно обобщив его на операнды различной длины. Поступим по-другому

Алгоритм 1.4. Умножения числа А длины n цифр на цифру х:

С = А*х

1.       Т:=0;

2.       для i = 0.. .n-1 выполнить 3-4;

3.       Т:=Т/b+Аi Ч х;

4.       Сi := LODIGIT(Т);

5.       Сn := HIDIGIT(T);

б.      конец.

Кстати, при этом получается число С длины n+ 1. Даже, если старшая цифра результата равна нулю, требуем, чтобы для нее была выделена память.