Сложно ли перемножить два числа?

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

Но, что если нам надо перемножить два числа любой длины? Не LONG, не байт, не число от 1 до 10, а любые два числа, которое, имеют в общем случае длину n бит, а результат умножения может иметь длину 2n бит.

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

Давайте применим его к нашей задаче.

В двоичной системе все выглядит проще, чем то, чему нас учили в школе для десятичных чисел. Берем два числа x и y в двоичном представлении. Чтобы получить произведение, нам надо сложить несколько раз числа x сдвинутые влево на позиции всех ненулевых битов y.

Есть сложность с последним сложением, но какова эта сложность? Для компьютера, получить эти слагаемые это семечки. Он очень хорошо умеет сдвигать двоичные числа. А вот сложить эти слагаемые…

В общем случае слагаемое может быть сдвинуто максимум на n позиций влево, значит каждое слагаемое имеет длину максимум в 2n бит. Чтобы сложить два числа длиной 2n бит, мы также можем применить сложение “столбиком”. Сложность этого алгоритма очевидна, мы проходим все разряды чисел от младшего к старшему. Для каждого разряда мы получаем сумму двух разрядов, добавляем перенос (если есть), учитываем перенос для следующего разряда. Все эти операции для одного разряда выполняются за константное время O(1). Очевидно, чтобы сложить два числа длиной 2n потребуется время O(2n) или просто O(n), опускаем, как это принято, постоянные множители.

Таким образом, чтобы получить произведение xy “столбиком” нам надо сложить, максимум n слагаемых длиной 2n. Каждое сложение имеет сложность O(n), значит сложность умножения “столбиком” это O(n²)

И тут и возникает вопрос: а можно ли перемножить два числа длины n бит более эффективным алгоритмом, чем O(n²).

Далее мы попробуем поискать такие алгоритмы, и (спойлеры) Да! Такие более эффективные способы умножения двух чисел существуют!

Ленивый Гаусс

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

Гаусс быстро заметил, что складывать числа гораздо проще, чем умножать их. Мы и сами это увидели в прошлом абзаце. Умножение “столбиком” двух чисел длины n бит имеет сложность O(n²) в то время, как сложение таких же чисел имеет сложность O(n)

Гаусс посмотрел на известную формулу умножения комплексных чисел

И заметил, что в этой формуле можно делать не 4 операции умножения [ac, bd, bc, ad]

А всего три операции умножения: [ac, bd, (a+b)(c+d)]

Красиво, на 25% работы стало меньше. но в современных реалиях, когда мы оцениваем сложность алгоритма в нотациях O(...) не имеет никакого значения, имеет ли алгоритм эффективность O(4n²) или O(3n²), постоянный множитель мы в этой нотации всегда опускаем.

Но сама идея сокращения количества операций умножения не так уже бесполезна. Рассмотрим пример.

Как и в прошлом абзаце у нас есть два числа x и y длиной n бит.

“Разрежем” эти числа пополам на старшую (левую) часть длиной n/2 бита и младшую (правую) часть длиной n/2 бита. Обозначим новые числа следующим способом:

Например,

Тогда произведение xy можно записать, как

Что если мы будем считать произведение xy, используя формулу в правой части? Умножение на 2ⁿ это всего лишь побитовый сдвиг, это даже за умножение не считаем, константная операция. Три сложения выполняются за линейное время O(n). Сложность представляют только четыре операции умножения: 

Но, заметим, что это операции теперь не с числами длиною n бит, а с числами длиною n/2 бит. Правда, с другой стороны, вместо одной операции умножения их стало четыре. 

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

Если нам надо перемножить два числа длиной n=2 бит, то мы можем эту операцию разбить на умножение четырех чисел, каждое длиною 1 бит. 

Если надо перемножить два числа длиною n=4 бит, то мы его можем эту операцию разбить на умножение четырех чисел, каждое длиною 2 бит, в свою очередь, это заменяется на операцию умножения 16 чисел длиною 1 бит. 

Напрашивается какой то рекурсивный алгоритм

Если количество элементарных операций которые нам надо проделать для перемножения двух чисел длиною n бит этим рекурсивным алгоритмом обозначить, как T(n), то для вычисления такого произведения, мы вычисляем рекурсивно четыре произведения T(n/2) и добавляем операции сложения и сдвига линейной сложности O(n).

Не будем заниматься подробно вычислением этого уравнения, так как этот алгоритм не стоит того, ответ будет T(n)=O(n²)

То есть мы получили новый алгоритм умножения двух чисел, и он дает такую же эффективность, как и перемножение “столбиком”. Обидно!

И тут то нам и приходит на помощь Гаусс. Что если в формуле (1) можно делать не четыре, а всего три операции умножения. Конечно, ведь

И нам надо вычислить всего три произведения n/2-битных чисел

А все остальное - это опять сложения и сдвиги, которые выполняются за линейное время.

Сложность такого алгоритма, построенного рекурсивным способом:

Решим это уравнение, построив рекурсивное дерево. На вершине этого дерева, произведение двух чисел xy длины n бит.

Уровнем рекурсии ниже дерево расходится на три произведения для чисел длины n/2

С каждым новым уровнем, количество ветвей дерева утраивается, при этом длина в битах умножаемых чисел делится на два.

На k-ом уровне мы имеем 3^k операций умножения, каждое из которых имеет длину n/2^k бит. На k-ом уровне алгоритм проводит еще некоторое время, выполняя линейные операции сложения и сдвига для чисел длиною n/2^k бит, т.е. операцию сложностью O(n/2^k)

Операции умножения чисел длиною n/2^k мы не учитываем, так как эта операция выполняется на k+1 ом уровне рекурсии и на наш уровень уже передан ответ. Мы выполняем на k-ом уровне только 3^k линейных операций сложения и сдвига, каждое из которых O(n/2^k) и передаем ответы уровню выше.

Т.е. количество операций на k-ом уровне рекурсии это

Получается, что количество операций по уровням дерева, это геометрическая прогрессия с множителем 3/2

На самом верхнем уровне k=0 по этой формуле получается просто O(n)

На самом нижнем уровне k=log₂(n) нам нужно провести операций 

А между верхним и нижним уровнем мы имеем нечто промежуточное полученное последовательным умножением на множитель 3/2 сколько то раз.

А значит, общая сложность алгоритма, это сумма сложностей на каждом уровне дерева, или, как мы видим, это просто сумма геометрической прогрессии с множителем 3/2 и первым членом O(n)

Опускаем вычитание константы и умножение на константу, получаем итоговую сложность алгоритма умножения.

Итак наш алгоритм несомненно более эффективный, чем умножение “столбиком” со сложностью O(n²).

Данный алгоритм называется алгоритмом Карацубы. В конце 1950-ых Адрей Колмогоров выдвинул гипотезу о том, что умножение "в столбик" со сложностью O(n²) является асимптотически оптимальным алгоритмом умножения двух чисел, что означает, что любой другой алгоритм, решающий эту задачу потребует Ω(n²) элементарных операций. В 1960-ом, Колмогоров проводил семинар по математическим проблемам кибернетики в МГУ, где он озвучил эту гипотезу, и ряд других задач по вычислительной сложности алгоритмов. В течение недели, 23-летний студент Анатолий Карацуба нашел данный алгоритм O(n^log(3)) и, таким образом, опроверг гипотезу. Колмогоров был восхищен открытием. Он рассказал об алгоритме на следующий день на семинаре. С алгоритмом Карацубы Колмогоров провел несколько лекций и выступлений на конференциях по всему миру. Алгоритм был опубликован в 1962 году: Ю. П. Офман, А. А. Карацуба, «Умножение многозначных чисел на автоматах» Доклады АН СССР. — 1962 — Т. 145. — С. 293—294.

Подведем итог. Что мы сделали, чтобы получить эффективный алгоритм?

Мы разделили задачу длины n на 3 задачи  длины n/2 и вдруг, обнаружили, что это эффективнее!

А можно ли так сделать и с другими алгоритмами, не только алгоритмом умножения?

Да, можно!

В этом и состоит принцип «Разделяй и властвуй» улучшения работы базовых алгоритмов.

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

Ссылка на вторую часть