Рекурсивный алгоритм умножения

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

Однако существует и более эффективный рекурсивный алгоритм умножения.

Пусть х и у — два n-разрядных десятичных числа и пусть n — некоторая натуральная степень числа 2. Разобьем числа х и у на 2 равные группы, обозначив левые (старшие) цифры чисел х₁ и y_l соответственно, а правые (младшие) — х₂ и у₂. Тогда

x×y = (x₁×10^n/2 + x₂)(y_l×10^n/2 + y₂) =

= x₁× y_l×10ⁿ + (x₁× y₂+x₂×y_l)×10^n/2 + x₂×y₂

То есть умножение двух чисел, каждое из которых имеет не более n разрядов, мы свели к трем действиям умножения чисел в два раза меньшей длины, сдвигу результатов такого умножения на соответствующее число разрядов влево и сложению длинных чисел. Однако, числа (x₁+x₂)и (у₁+y₂), вообще говоря, имеют n/2+1 разряд и поэтому их произведение нельзя вычислить непосредственным рекурсивным применением нашего алгоритма. Поэтому, чтобы сделать алгоритм универсальным, перепишем его для произвольного числа n, обозначив буквой т остаток от деления п на 2:

х×у = (x₁×10^[n/2]+m + х₂)(у₁×10^[n/2]+m + у₂) =

= x₁×y₁×10^n+m + (x₁×y₂ + x₂×y₁)×10^[n/2]+m + х₂×у₂ =

= x₁×y₁×10^n+m + ((x₁+x₂)(y₁+y₂)-x₁×y₁ - х₂×y₂)×10^[n/2]+m + х₂×у₂

Теперь возможна рекурсивная реализация данного алгоритма. Если же при некотором рекурсивном вызове п окажется меньше пяти, то умножение х и у уже можно произвести непосредственно в рамках четырехбайтного целого типа.

Доказано, что с ростом п такой алгоритм является асимптотически более быстрым, нежели умножение «столбиком», однако его реализация более громоздкая и в ней приходится использовать несколько дополнительных массивов, что уменьшает максимальную длину чисел, для которых этот алгоритм может быть применен.