Разделяй и властвуй. Повышение эффективности алгоритмов
Сложно ли перемножить два числа?
Да, мы привыкли, что перемножение двух байт, или двух 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^2)
И тут и возникает вопрос:, а можно ли перемножить два числа длины n бит более эффективным алгоритмом, чем O (n^2).
Далее мы попробуем поискать такие алгоритмы, и (спойлеры) Да! Такие более эффективные способы умножения двух чисел существуют!
Ленивый Гаусс
Иоганн Гаусс был гениален, но очень ленив. Гауссу приходилось часто умножать много чисел разной длины без какого-либо калькулятора и он начал искать способ делать это так, чтобы работать как можно меньше.
Гаусс быстро заметил, что складывать числа гораздо проще, чем умножать их. Мы и сами это увидели в прошлом абзаце. Умножение «столбиком» двух чисел длины n бит имеет сложность O (n^2) в то время, как сложение таких же чисел имеет сложность O (n)
Гаусс посмотрел на известную формулу умножения комплексных чисел
И заметил, что в этой формуле можно делать не 4 операции умножения [ac, ad, bc, ad]
А всего три операции умножения: [ac, bd, (a+b)(c+d)]
Красиво, на 25% работы стало меньше., но в современных реалиях, когда мы оцениваем сложность алгоритма в нотациях O (…) не имеет никакого значения, имеет ли алгоритм эффективность O (4n^2) или O (3n^2), постоянный множитель мы в этой нотации всегда опускаем.
Но сама идея сокращения количества умножений не так уже бесполезна. Рассмотрим пример.
Как и в прошлом абзаце у нас есть два числа x и y длиной n бит.
«Разрежем» эти числа пополам на старшую (левую) часть длиной n/2 бита и младшую (правую) часть длиной n/2 бита. Обозначим новые числа следующим способом:
![x=[x_Lx_R]=2^{n/2}x_L+x_R](https://habrastorage.org/getpro/habr/upload_files/6f6/33e/195/6f633e195f7947470bb5aabaa8b0c1a9.svg)
![y=[y_Ly_R]=2^{n/2}y_L+y_R](https://habrastorage.org/getpro/habr/upload_files/95b/570/47d/95b57047d942486ce4aa97ab914b9ef8.svg)
Например,
Тогда произведение xy можно записать, как
Что если мы будем считать произведение xy, используя формулу в правой части? Умножение на 2^n это всего лишь побитовый сдвиг, это даже за умножение не считаем, константная операция. Три сложения выполняются за линейное время 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^2)
То есть мы получили новый алгоритм умножения двух чисел, и он дает такую же эффективность, как и перемножение «столбиком». Обидно!
И тут то нам и приходит на помощь Гаусс. Что если в формуле (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=log2(n) нам нужно провести операций
А между верхним и нижним уровнем мы имеем нечто промежуточное полученное последовательным умножением на множитель 3/2 сколько то раз.
А значит, общая сложность алгоритма, это сумма сложностей на каждом уровне дерева, или, как мы видим, это просто сумма геометрической прогрессии с множителем 3/2 и первым членом O (n)
Опускаем вычитание константы и умножение на константу, получаем итоговую сложность алгоритма умножения.
Итак наш алгоритм несомненно более эффективный, чем умножение «столбиком» со сложностью O (n^2)
Подведем итог. Что мы сделали, чтобы получить эффективный алгоритм?
Мы разделили задачу длины n на 4 задачи длины n/2 и вдруг, обнаружили, что это эффективнее!
А можно ли так сделать и с другими алгоритмами, не только алгоритмом умножения?
Да, можно!
В этом и состоит принцип «Разделяй и властвуй» улучшения работы базовых алгоритмов.
Теперь в следующей части мы можем обобщить рассмотрение и попытаться понять, когда принцип «Разделяй и властвуй» дает выигрыш в сравнении с базовой реализацией алгоритма, а когда нет. Рассмотрим примеры других базовых алгоритмов, где принцип «Разделяй и властвуй» дал ощутимый выигрыш в эффективности.
