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

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

$M(n)=O(n^{\log_23}),\quad\log_23=1{,}5849\ldots$

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

Історія

Проблема оцінки кількості бітових операцій, достатнього для обчислення добутку двох n-значних чисел, або проблема зростання функції складності множення $M(n)$при$n\to+\infty$ є нетривіальною проблемою теорії швидких обчислень.

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

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

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

$M(n)=O(n^{\log_23})$

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

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

Нижче представлені два варіанти (з багатьох) множення Карацуба.

Опис методу

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

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

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

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

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

$X=e_0+2e_1+\ldots+2^{n-1}e_{n-1},$

де $e_j\in{0,\;1},\;j=0,\;1,\;\ldots,\;n-1$.

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

$X=X_1+2^kX_2,$

де

$X_1=e_0+2e_1+\ldots+2^{k-1}e_{k-1}$

і

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

знаходимо:

$X^2=(X_1+2^kX_2)^2=X_1^2+((X_1+ X_2)^2-(X_1^2+X_2^2))2^k+X_2^22^n.\qquad(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_3X_4+X_4^2.$

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

$\varphi(n)\leqslant 3\varphi(n2^{-1})+cn,\qquad(2)$

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

$\varphi(n2^{-1}),\;\varphi(n2^{-2}),\;\ldots,\;\varphi(n2^{-m+1})$

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

$\varphi(n2^{-m})=\varphi(1)=1,$

отримуємо

$\varphi(n)\leqslant 3(3\varphi(n2^{-2})+cn2^{-1})+cn=3^2\varphi(n2^{-2})+3c(n2^{-1})+cn\leqslant\ldots\leqslant$

$\leqslant 3^m\varphi(n2^{-m})+3^{m-1}c(n2^{-m+1})+3^{m-2}c(n2^{-m+2})+\ldots+3c(n2^{-1})+cn=$

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

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

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

$\varphi(n)<(2c+1)n^{\log_23},\quad \log_23=1{,}5849\ldots$

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

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

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

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

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

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

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

$A = A_1 +2 ^ kA_2, \ quad B = B_1 +2 ^ kB_2,$

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

$AB = A_1B_1 +2 ^ k ((A_1 + A_2) (B_1 + B_2) - (A_1B_1 + A_2B_2)) +2 ^ nA_2B_2. \ Qquad (3)$

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

$\ Varphi (n) <(2c +1) n ^ {\ log_23}, \ quad \ log_23 = 1 {,} 5849 \ ldots$

Зауваження

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

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

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

Див також

• Складність обчислення (бітова)
• АГС метод Гаусса
• Метод БВЕ
• Швидкі алгоритми
• Метод множення Шенхаге - штрассе
• Алгоритм Фюрера

Посилання

• Http://212.cmc-msu.ru/files/kniga.html
• Http://gersoo.free.fr/docs/karat/kar.html
• Http://numbers.computation.free.fr/Constants/Algorithms/representation.html
• Http://www-math.uni-paderborn.de/mca/mult.html
• Http://www-2.cs.cmu.edu/ ~ cburch/251/karat /
• Http://www.cs.pitt.edu/ ~ kirk/cs1501/animations /
• Http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html
• Http://www.ccas.ru/personal/karatsuba/divcru.htm
• Http://www.ccas.ru/personal/karatsuba/alg.htm
• Http://habrahabr.ru/blogs/algorithm/124258/