Главная
Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью:
T ( n ) = O ( n log 2 3 ) , log 2 3 = 1,584 9 … {displaystyle T(n)=O(n^{log _{2}3}),quad log _{2}3=1{,}5849ldots } .Изобретён Анатолием Карацубой в 1960 году, является исторически первым алгоритмом умножения, превосходящим традиционный по асимптотической сложности. Являлся быстрейшим алгоритмом умножения до появления в 1971 году метода Шёнхаге — Штрассена.
История
В 1960 году Андрей Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух n {displaystyle n} -разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало O ( n 2 ) {displaystyle O(n^{2})} элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше n 2 {displaystyle n^{2}} по порядку величины. На правдоподобность «гипотезы n 2 {displaystyle n^{2}} » указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний Анатолий Карацуба предложил новый метод умножения двух n {displaystyle n} -значных чисел с оценкой времени работы O ( n log 2 3 ) {displaystyle O(n^{log _{2}3})} и тем самым опроверг «гипотезу n 2 {displaystyle n^{2}} ».
Метод Карацубы относится к алгоритмам вида «разделяй и властвуй», наравне с такими алгоритмами как двоичный поиск, быстрая сортировка и др. Формулы рекурсивного сведения, используемые в методе Карацубы, были известны ещё Чарльзу Бэббиджу, который, однако, не обратил внимания на возможность использования лишь трёх рекурсивных умножений вместо четырёх.
Описание метода
Пусть есть два n {displaystyle n} -значных двоичных числа A = a x + b {displaystyle A=ax+b} и B = c x + d {displaystyle B=cx+d} , где n {displaystyle n} — чётное число и x = 10 n / 2 { extstyle x=10^{n/2}} . То есть, a {displaystyle a} и c {displaystyle c} получены из старших n / 2 {displaystyle n/2} разрядов A {displaystyle A} и B {displaystyle B} , а b {displaystyle b} и d {displaystyle d} — из младших.
В таких обозначениях произведение чисел A {displaystyle A} и B {displaystyle B} может быть переписано как
A B = ( a x + b ) ( c x + d ) = a c x 2 + ( a d + b c ) x + b d . {displaystyle AB=(ax+b)(cx+d)=acx^{2}+(ad+bc)x+bd.}Таким образом, умножение n {displaystyle n} -значных чисел было сведено к четырём задачам умножения n / 2 {displaystyle n/2} -значных чисел и последующему битовому сдвигу и сложению результатов, которые выполняются за O ( n ) {displaystyle O(n)} .
Время работы T ( n ) {displaystyle T(n)} полученной процедуры может быть оценено по основной теореме о рекуррентных оценках:
T ( n ) = 4 T ( n 2 ) + Θ ( n ) = Θ ( n 2 ) {displaystyle T(n)=4Tleft({frac {n}{2}} ight)+Theta (n)=Theta (n^{2})}Пока что данный подход не даёт выигрыша во времени работы, однако Карацуба заметил, что на самом деле достаточно лишь трёх умножений n / 2 {displaystyle n/2} -значных чисел, так как
( a d + b c ) = ( a + b ) ( c + d ) − a c − b d . {displaystyle (ad+bc)=(a+b)(c+d)-ac-bd.}Таким образом, всё произведение A B {displaystyle AB} может быть получено из a c {displaystyle ac} , b d {displaystyle bd} и ( a + b ) ( c + d ) {displaystyle (a+b)(c+d)} линейными операциями сложения, вычитания и битового сдвига, а общее время работы оценивается как
T ( n ) = 3 T ( n 2 ) + Θ ( n ) = Θ ( n log 2 3 ) {displaystyle T(n)=3Tleft({frac {n}{2}} ight)+Theta (n)=Theta (n^{log _{2}3})}Пример
Рассмотрим задачу умножения двух восьмизначных (в десятичной записи) чисел: N = 12345678 {displaystyle N=12345678} и M = 98765432 {displaystyle M=98765432} .
Представим каждое из них в виде суммы двух чисел вдвое меньшей разрядности, одно из которых взято со сдвигом:
{ N = 1234 ⋅ 10000 + 5678 M = 9876 ⋅ 10000 + 5432 {displaystyle {egin{cases}N=1234cdot 10000+5678M=9876cdot 10000+5432end{cases}}}Раскрывая скобки, произведение N {displaystyle N} и M {displaystyle M} можно переписать как
( 1234 ⋅ 10000 + 5678 ) ( 9876 ⋅ 10000 + 5432 ) = {displaystyle (1234cdot 10000+5678)(9876cdot 10000+5432)=} 1234 ⋅ 9876 ⋅ 10000 2 + 10000 ( 1234 ⋅ 5432 + 5678 ⋅ 9876 ) + 5678 ⋅ 5432 = {displaystyle 1234cdot 9876cdot 10000^{2}+10000(1234cdot 5432+5678cdot 9876)+5678cdot 5432=} 1234 ⋅ 9876 ⋅ 10000 2 + 10000 ( ( 1234 + 5678 ) ⋅ ( 9876 + 5432 ) − 1234 ⋅ 9876 − 5678 ⋅ 5432 ) + 5678 ⋅ 5432 {displaystyle 1234cdot 9876cdot 10000^{2}+10000((1234+5678)cdot (9876+5432)-1234cdot 9876-5678cdot 5432)+5678cdot 5432}При этом чтобы вычислить всё произведение, достаточно совершить только три умножения 1234 ⋅ 9876 {displaystyle 1234cdot 9876} , 5678 ⋅ 5432 {displaystyle 5678cdot 5432} и ( 1234 + 5678 ) ( 9876 + 5432 ) {displaystyle (1234+5678)(9876+5432)} и несколько сложений, вычитаний и сдвигов.
Для их умножения применяется тот же алгоритм: 1234 ⋅ 9876 {displaystyle 1234cdot 9876} представляется как ( 12 ⋅ 100 + 34 ) ( 98 ⋅ 100 + 76 ) {displaystyle (12cdot 100+34)(98cdot 100+76)} и так далее.
На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.
Описанная здесь логика сохраняется и при работе в двоичной системе счисления, используемой вычислительной техникой. В таком случае x {displaystyle x} является степенью не десяти, а двух. В качестве примера, вычисление произведения двух 4096-битных двоичных чисел методом Карацубы требует 3 12 ≈ 530 {displaystyle 3^{12}approx 530} тысяч элементарных однобитовых умножений вместо ( 2 12 ) 2 ≈ 16 , 8 {displaystyle (2^{12})^{2}approx 16,8} млн при умножении наивным методом.