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

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

$M(n)=O(n^{\log _{2}3}),\quad \log _{2}3\approx 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 _{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}+\ldots +2^{n-1}e_{n-1},$

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

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

$X=X_{1}+2^{k}X_{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^{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}.\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_{3}X_{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 _{2}3}.$

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

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

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

$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}$, $n=2k$, $A$ і $B$ - два $n$-значних числа. Представляючи $A$ і $B$ у вигляді

$A=A_{1}+2^{k}A_{2},\quad 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}.\quad (3)$

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

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

Приклад

Множимо 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;
Z₁ = (6+48)*(3+56) − 6*3 − 48*56 = 54*59 − 18 − 2688 = 480.

У цілому:
18*100² + Z₁*100 + 2688 = 18 00 00 + 480 00 + 2688 = 23 06 88.

• Для множення пар чисел 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 [Архівовано 3 січня 2022 у Wayback Machine.]
• https://web.archive.org/web/20071031012910/http://gersoo.free.fr/docs/karat/kar.html
• Http://numbers.computation.free.fr/Constants/Algorithms/representation.html [Архівовано 3 січня 2022 у Wayback Machine.]
• https://web.archive.org/web/20160417193210/http://www-math.uni-paderborn.de/mca/mult.html
• Http://www-2.cs.cmu.edu/ [Архівовано 4 лютого 2013 у Wayback Machine.] ~ cburch/251/karat /
• Http://www.cs.pitt.edu/ [Архівовано 5 березня 2022 у Wayback Machine.] ~ 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 [Архівовано 13 вересня 2019 у Wayback Machine.]
• Http://www.ccas.ru/personal/karatsuba/alg.htm [Архівовано 4 листопада 2012 у Wayback Machine.]
• Http://habrahabr.ru/blogs/algorithm/124258/ [Архівовано 28 грудня 2011 у Wayback Machine.]