Множення Карацуби

Множення Карацуби — метод швидкого множення, який дозволяє перемножувати два n-значних числа зі складністю обчислення:

$M(n)=O(n^{{\log }_{2}3}),{\log }_{2}3\approx 1,5849\dots$

Цей підхід відкрив новий напрямок в обчислювальній математиці.

Історія

Проблема оцінки кількості бітових операцій, необхідних для обчислення добутку двох n-значних чисел, або Шаблон:Джерело?.

Множення двох n-значних цілих чисел звичайним (шкільним) методом «у стовпчик» зводиться, по суті, до додавання n n-значних чисел. Тому для складності цього «шкільного» або «наївного» методу є оцінка зверху:

$M(n)=O(n^2).$

У 1956 р. А. М. Колмогоров сформулював гіпотезу, що нижня оцінка для $M(n)$ при будь-якому методі множення є також величина порядку $n^2$ (так звана «гіпотеза $n^2$» Колмогорова). На правдоподібність гіпотези $n^2$ вказував той факт, що метод множення «в стовпчик» відомий не менше чотирьох тисячоліть (наприклад, цим методом користувалися шумери), і якби існував швидший метод, то його, імовірно, уже б знайшли. Однак, 1960 року Анатолій Карацуба знайшов новий метод множення двох n-значних чисел з оцінкою складності

$M(n)=O(n^{{\log }_{2}3})$

і тим самим спростував «гіпотезу $n^2$».

Згодом метод Карацуби узагальнили до парадигми «розділяй і володарюй», іншими важливими прикладами якої є метод двійкового розбиття, двійковий пошук, метод бісекції тощо.

Нижче подано два варіанти множення Карацуби.

Опис методу

Перший варіант

Цей варіант заснований на формулі

$(a+bx{)}^2=a^2+((a+b{)}^2-a^2-b^2)x+b^2{x}^2.$

Оскільки $4ab=(a+b{)}^2-(a-b{)}^2$, то множення двох чисел $a$ і $b$ еквівалентне за складністю піднесенню до квадрата.

Нехай $X$ є $n$-значним числом, тобто

$X=e_0+2e_1+\dots +2^{n-1}{e}_{n-1},$

де $e_j\in 0,1,j=0,1,\dots ,n-1$.

Будемо вважати для простоти, що $n=2^m,m⩾1;n=2k$. Представляючи $X$ у вигляді

$X=X_1+2^k{X}_2,$

де

$X_1=e_0+2e_1+\dots +2^{k-1}{e}_{k-1}$

і

$X_2=e_k+2e_{k+1}+\dots +2^{k-1}{e}_{n-1},$

знаходимо:

$X^2=(X_1+2^k{X}_2{)}^2=X_1^2+((X_1+X_2{)}^2-(X_1^2+X_2^2))2^k+X_2^2{2}^n.(1)$

Числа $X_1$і$X_2$ є $k$-значними. Число $X_1+X_2$ може мати $k+1$ знаків. У цьому випадку представимо його у вигляді $2X_3+X_4$, де $X_3$ є $k$-значне число, $X_4$ — однозначне число. Тоді

$(X_1+X_2{)}^2=4X_3^2+4X_3{X}_4+X_4^2.$

Позначимо $\phi (n)$ - кількість операцій, достатня для піднесення $n$-значного числа в квадрат за формулою (1). З (1) випливає, що для $\phi (n)$ справедлива нерівність:

$\phi (n)⩽3\phi (n{2}^{-1})+cn,(2)$

де $c>0$ є абсолютна константа. Справді, права частина (1) містить суму трьох квадратів $k$-значних чисел, $k=n{2}^{-1}$, які для свого обчислення потребують $3\phi (m)=3\phi (n{2}^{-1})$ операцій. Усі інші обчислення в правій частині (1) (а саме: множення на $4,2^k,2^n$, п'ять додавань і одне віднімання) не більше ніж $2n$-значних чисел вимагають по порядку не більше $n$ операцій. Звідси випливає (2). Застосовуючи (2) послідовно до

$\phi (n{2}^{-1}),\phi (n{2}^{-2}),\dots ,\phi (n{2}^{-m+1})$

і беручи до уваги, що

$\phi (n{2}^{-m})=\phi (1)=1,$

отримуємо

$\phi (n)⩽3(3\phi (n{2}^{-2})+cn{2}^{-1})+cn=3^2\phi (n{2}^{-2})+3c(n{2}^{-1})+cn⩽\dots ⩽$

$⩽3^m\phi (n{2}^{-m})+3^{m-1}c(n{2}^{-m+1})+3^{m-2}c(n{2}^{-m+2})+\dots +3c(n{2}^{-1})+cn=$

$=3^m+cn({\left(\frac{3}{2}\right)}^{m-1}+{\left(\frac{3}{2}\right)}^{m-2}+\dots +\left(\frac{3}{2}\right)+1)=$

$=3^m+2cn({\left(\frac{3}{2}\right)}^m-1)<3^m(2c+1)=(2c+1)n^{{\log }_{2}3}.$

Таким чином для кількості $\phi (n)$ операцій, достатнього для зведення $n$-значного числа в квадрат за формулою (1) виконується оцінка:

$\phi (n)<(2c+1)n^{{\log }_{2}3},{\log }_{2}3=1,5849\dots$

Якщо ж $n$ не є ступенем двох, то визначаючи ціле число $m$ нерівностями $2^{m-1}<n⩽2^m$, представимо $X$ як $2^m$-значне число, тобто вважаємо останні $2^{m}n$ знаків рівними нулю:

$E_n=\dots =e_{2^m-1}=0.$

Усі інші міркування залишаються в силі і для $\phi (n)$ виходить така ж верхня оцінка за порядком величини $n$.

Другий варіант

Це безпосереднє множення двох $n$-значних чисел, засноване на формулі

$(a+bx)(c+dx)=ac+((a+b)(c+d)-ac-bd)x+bd{x}^2.$

Нехай, як і раніше $n=2^m$, $n=2k$, $A$ і $B$ - два $n$-значних числа. Представляючи $A$ і $B$ у вигляді

$A=A_1+2^k{A}_2,B=B_1+2^k{B}_2,$

де $A_1,A_2,B_1,B_2$ — $k$-значні числа, знаходимо:

$AB=A_1{B}_1+2^k((A_1+A_2)(B_1+B_2)-(A_1{B}_1+A_2{B}_2))+2^n{A}_2{B}_2.(3)$

Таким чином, у цьому випадку формула (1) замінюється формулою (3). Якщо тепер позначити символом $\phi (n)$ кількість операцій, достатню для множення двох $n$-значних чисел за формулою (3), то для $\phi (n)$ виконується нерівність (2), і, отже, справедливою є нерівність:

$\phi (n)<(2c+1)n^{{\log }_{2}3},{\log }_{2}3=1,5849\dots$

Приклад

Множимо 648*356. Візьмемо B=100.

Перший множник подамо як 6*100 + 48.
Другий множник подамо як 3*100 + 56.
За формулою Карацуби:
x*y = (x₁*B + x₀)*(y₁*B + y₀) = x₁*y₁*B² + Z₁*B + x₀*y₀,

де Z₁ = (x₁ + x₀)*(y₁ + y₀) − x₁*y₁ − x₀*y₀,
а добутки x₁*y₁ та x₀*y₀ обчислюють лише один раз.
Маємо: 648*356=(6*100+48)*(3*100+56)=6*3*100² + Z₁*100 + 48*56.
Обчислюємо 6*3 =18; 48*56 = 2688;
Шаблон:Nobr.

У цілому:
Шаблон:Nobr.

• Для множення пар чисел 54*59 та 48*56, можна застосувати формулу Карацуби рекурсивно, поклавши B=10.
• Оскільки ЕОМ оперують двійковими числами, то для машинних розрахунків варто обрати B=2^k.

Зауваження

Представлений вище перший спосіб множення можна трактувати як алгоритм обчислення з точністю до $n$ знаків функції $y=x^2$ в деякій точці $x=x_1$.

Якщо розбивати $X$ не на два, а на більшу кількість доданків, то можна отримати асимптотично кращі оцінки складності обчислення добутку (піднесення до квадрату). Зокрема, такий шлях застосовано в Шаблон:Нп.

Метод множення Шьонхаге — Штрассена має меншу асимптотичну складність, ніж алгоритм Карацуби, однак на практиці він має перевагу лише для великих значень n.

Посилання

• Http://212.cmc-msu.ru/files/kniga.html Шаблон:Webarchive
• https://web.archive.org/web/20071031012910/http://gersoo.free.fr/docs/karat/kar.html
• Http://numbers.computation.free.fr/Constants/Algorithms/representation.html Шаблон:Webarchive
• https://web.archive.org/web/20160417193210/http://www-math.uni-paderborn.de/mca/mult.html
• Http://www-2.cs.cmu.edu/ Шаблон:Webarchive ~ cburch/251/karat /
• Http://www.cs.pitt.edu/ Шаблон:Webarchive ~ kirk/cs1501/animations /
• https://web.archive.org/web/20070125091442/http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html
• Http://www.ccas.ru/personal/karatsuba/divcru.htm Шаблон:Webarchive
• Http://www.ccas.ru/personal/karatsuba/alg.htm Шаблон:Webarchive
• Http://habrahabr.ru/blogs/algorithm/124258/ Шаблон:Webarchive