Перегляд вихідного коду сторінки Множення Карацуби

'''Множення Карацуби ''' — метод швидкого [[множення]], який дозволяє перемножувати два [[позиційна система числення|'' n''-значних]] числа зі складністю обчислення:
: <math>M(n)=O(n^{\log_23}),\quad\log_23 \approx 1{,}5849\ldots</math>

Цей підхід відкрив новий напрямок в обчислювальній математиці<ref>Карацуба Є. А. [http://www.ccas.ru/personal/karatsuba/alg.htm Швидкі алгоритми і метод БВЕ] {{Webarchive|url=https://web.archive.org/web/20121104053354/http://www.ccas.ru/personal/karatsuba/alg.htm |date=4 листопада 2012 }}, 2008.</ref><ref>{{стаття | автор = Алексєєв В. Б. | заголовок = Від методу Карацуба для швидкого множення чисел до швидких алгоритмах для дискретних функцій | видання = Тр. МІАН | рік = 1997 | те = 218 | сторінки = 20-27 | посилання = http://mi.mathnet.ru/tm947}}</ref>.

== Історія ==
Проблема оцінки кількості бітових операцій, необхідних для обчислення добутку двох ''n''-значних чисел, або {{Джерело?|проблема функції складності множення <math>M(n)</math> при <math>n\to+\infty</math> була нетривіальною проблемою теорії швидких обчислень}}.

Множення двох ''n''-значних цілих чисел звичайним (шкільним) методом «у стовпчик» зводиться, по суті, до [[додавання]] ''n'' ''n''-значних чисел. Тому для складності цього «шкільного» або «наївного» методу є оцінка зверху:
: <math>M(n)=O(n^2).</Math>

У [[1956]] р. [[Колмогоров Андрій Миколайович|А. М. Колмогоров]] сформулював гіпотезу, що нижня оцінка для <math> M (n) </math> при будь-якому методі множення є також величина порядку <math>n^2</math> (так звана «гіпотеза <math>n^2</math>» Колмогорова). На правдоподібність гіпотези <math> n ^ 2 </math> вказував той факт, що метод множення «в стовпчик» відомий не менше чотирьох тисячоліть (наприклад, цим методом користувалися [[шумери]]), і якби існував швидший метод, то його, імовірно, уже б знайшли. Однак, [[1960]] року [[Карацуба Анатолій Олексійович|Анатолій Карацуба]]<ref>{{стаття | автор = Карацуба А., Офман Ю. | заголовок = Множення багатоцифрових чисел на автоматах | рік = 1962 | видання = Доповіді Академії Наук СРСР | тому = 145 | номер = 2}}</ref><ref>{{стаття | автор = Karacuba A. | заголовок = Berechnungen und die Kompliziertheit von Beziehungen | рік = 1975 | видання = Elektronische Informationsverarbeitung und Kybernetik | тому = 11 | мова = de}}</ref><ref>{{стаття | автор = Карацуба А. А. | заголовок = Складність обчислень | рік = 1995 | видання = Тр. МІАН | тому = 211 | сторінки = 186-202 | посилання = http://mi.mathnet.ru/tm1120}}</ref><ref>{{книга | автор =  [[Кнут, Дональд Ервін|Кнут Д.]]  | заголовок = Мистецтво програмування | видання = 3-е изд | місце = {{М.}} | видавництво =  [[Вільямс (видавництво)|Вильямс]] | тому = 2. Получісленние алгоритми | рік = 2007 | сторінок = 832 | isbn = 0-201-89684-2}}</ref> знайшов новий метод множення двох ''n''-значних чисел з оцінкою складності
: <math>M(n)=O(n^{\log_23})</math>
і тим самим спростував «гіпотезу <math>n^2</math>».

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

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

== Опис методу ==
=== Перший варіант ===
Цей варіант заснований на формулі
: <math>(a+bx)^2=a^2+((a+b)^2-a^2-b^2)x+b^2x^2.</Math>
Оскільки <math>4ab=(a+b)^2-(a-b)^2</math>, то множення двох чисел <math>a</math> і <math>b</math> еквівалентне за складністю піднесенню до квадрата.

Нехай <math>X</math> є <math>n</math>-значним числом, тобто
: <math>X=e_0+2e_1+\ldots+2^{n-1}e_{n-1},</math>
де <math>e_j\in{0,\;1},\;j=0,\;1,\;\ldots,\;n-1</math>.

Будемо вважати для простоти, що <math>n=2^m,\;m\geqslant1;\;n=2k</math>. Представляючи <math>X</math> у вигляді
: <math>X=X_1+2^kX_2,</math>
де
: <math>X_1=e_0+2e_1+\ldots+2^{k-1}e_{k-1}</math>
і
: <math>X_2=e_k+2e_{k+1}+\ldots+2^{k-1}e_{n-1},</math>
знаходимо:
: <math>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)</math>
Числа <math>X_1</math>і<math>X_2</math> є <math>k</math>-значними. Число <math>X_1+X_2</math> може мати <math>k+1</math> знаків. У цьому випадку представимо його у вигляді <math>2X_3+X_4</math>, де <math>X_3</math> є <math>k</math>-значне число, <math>X_4</math> — однозначне число. Тоді
: <math>(X_1+X_2)^2=4X_3^2+4X_3X_4+X_4^2.</Math>
Позначимо <math>\varphi(n)</math> - кількість операцій, достатня для піднесення <math> n </math>-значного числа в квадрат за формулою (1). З (1) випливає, що для <math>\varphi(n)</math> справедлива нерівність:
: <math>\varphi(n)\leqslant 3\varphi(n2^{-1})+cn,\qquad(2)</math>
де <math>c>0</math> є абсолютна константа. Справді, права частина (1) містить суму трьох квадратів <math> k </math>-значних чисел, <math>k=n2^{-1}</math>, які для свого обчислення потребують <math>3\varphi(m)=3\varphi(n2^{-1})</math> операцій. Усі інші обчислення в правій частині (1) (а саме: множення на <math>4,\;2^k,\;2^n</math>, п'ять додавань і одне віднімання) не більше ніж <math>2n</math>-значних чисел вимагають по порядку не більше <math>n</math> операцій. Звідси випливає (2). Застосовуючи (2) послідовно до
: <math>\varphi(n2^{-1}),\;\varphi(n2^{-2}),\;\ldots,\;\varphi(n2^{-m+1})</math>
і беручи до уваги, що
: <math>\varphi(n2^{-m})=\varphi(1)=1,</math>
отримуємо
: <math>\varphi(n)\leqslant 3(3\varphi(n2^{-2})+cn2^{-1})+cn=3^2\varphi(n2^{-2})+3c(n2^{-1})+cn\leqslant\ldots\leqslant</math>
:: <math>\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=</math>
:: <math>=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)=</math>
:: <math>=3^m+2cn\left(\left(\frac{3}{2}\right)^m-1\right)<3^m(2c+1)=(2c+1)n^{\log_23}.</math>
Таким чином для кількості <math>\varphi(n)</math> операцій, достатнього для зведення <math>n</math>-значного числа в квадрат за формулою (1) виконується оцінка:
: <math>\varphi(n)<(2c+1)n^{\log_23},\quad \log_23=1{,}5849\ldots</math>
Якщо ж <math> n </math> не є ступенем двох, то визначаючи ціле число <math>m</math> нерівностями <math>2^{m-1}<n\leqslant2^m</math>, представимо <math>X</math> як <math>2^m</math>-значне число, тобто вважаємо останні <math>2^mn</math> знаків рівними нулю:
: <math>E_n=\ldots=e_{2^m-1}=0.</Math>
Усі інші міркування залишаються в силі і для <math>\varphi(n)</math> виходить така ж верхня оцінка за порядком величини <math>n</math>.

=== Другий варіант ===
Це безпосереднє множення двох <math> n </math>-значних чисел, засноване на формулі
:<math> (a + bx) (c + dx) = ac + ((a + b) (c + d)-ac-bd) x + bdx ^ 2. </math>
Нехай, як і раніше <math> n = 2 ^ m </math>, <math> n = 2k </math>, <math> A </math> і <math> B </math> - два <math > n </math>-значних числа. Представляючи <math> A </math> і <math> B </math> у вигляді
: <math> A = A_1 +2 ^ kA_2, \quad B = B_1 +2 ^ kB_2, </math>
де <math> A_1, \; A_2, \; B_1, \; B_2 </math> — <math> k </math>-значні числа, знаходимо:
: <math> AB = A_1B_1 +2 ^ k ((A_1 + A_2) (B_1 + B_2) - (A_1B_1 + A_2B_2)) +2 ^ nA_2B_2. \quad (3) </math>
Таким чином, у цьому випадку формула (1) замінюється формулою (3). Якщо тепер позначити символом <math> \varphi (n) </math> кількість операцій, достатню для множення двох <math> n </math>-значних чисел за формулою (3), то для <math> \varphi (n) </math> виконується нерівність (2), і, отже, справедливою є нерівність:
: <math> \varphi (n) <(2c +1) n ^ {\log_23}, \quad \log_23 = 1 {,} 5849 \ldots </math>

=== Приклад ===
Множимо 648*356. Візьмемо B=100.
: Перший множник подамо як 6*100 + 48. <br/>Другий множник подамо як 3*100 + 56. <br/>За формулою Карацуби:<br/>x*y = (x<sub>1</sub>*B + x<sub>0</sub>)*(y<sub>1</sub>*B + y<sub>0</sub>) = x<sub>1</sub>*y<sub>1</sub>*B<sup>2</sup> + Z<sub>1</sub>*B + x<sub>0</sub>*y<sub>0</sub>,
: де Z<sub>1</sub> = (x<sub>1</sub> + x<sub>0</sub>)*(y<sub>1</sub> + y<sub>0</sub>) &minus; x<sub>1</sub>*y<sub>1</sub> &minus; x<sub>0</sub>*y<sub>0</sub>, <br/>а добутки x<sub>1</sub>*y<sub>1</sub> та x<sub>0</sub>*y<sub>0</sub> обчислюють лише один раз. <br/>Маємо: 648*356=(6*100+48)*(3*100+56)=6*3*100<sup>2</sup> + Z<sub>1</sub>*100 + 48*56. <br/>Обчислюємо 6*3 =18; 48*56 = 2688; <br/>{{nobr|1= Z<sub>1</sub> = (6+48)*(3+56) &minus; 6*3 &minus; 48*56 = 54*59 &minus; 18 &minus; 2688 = 480}}.

У цілому: <br/>{{nobr|1=18*100<sup>2</sup> + Z<sub>1</sub>*100 + 2688 = 18 00 00 + 480 00 + 2688 = 23 06 88}}.  
* Для множення пар чисел 54*59 та 48*56, можна застосувати формулу Карацуби [[Рекурсія (програмування)|рекурсивно]], поклавши B=10.   
* Оскільки [[Комп'ютер|ЕОМ]] оперують [[Двійкова система числення|двійковими числами]], то для машинних розрахунків варто обрати B=2<sup>k</sup>.

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

Якщо розбивати <math> X </math> не на два, а на більшу кількість доданків, то можна отримати асимптотично кращі оцінки складності обчислення добутку (піднесення до квадрату). Зокрема, такий шлях застосовано в {{нп|алгоритм Тоома — Кука|алгоритмі Тоома — Кука||Toom–Cook multiplication}}.

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

== Примітки ==
{{Примітки | 2}}

== Посилання ==
* Http://212.cmc-msu.ru/files/kniga.html {{Webarchive|url=https://web.archive.org/web/20220103080549/http://212.cmc-msu.ru/files/kniga.html |date=3 січня 2022 }}
* https://web.archive.org/web/20071031012910/http://gersoo.free.fr/docs/karat/kar.html
* Http://numbers.computation.free.fr/Constants/Algorithms/representation.html {{Webarchive|url=https://web.archive.org/web/20220103080547/http://numbers.computation.free.fr/Constants/Algorithms/representation.html |date=3 січня 2022 }}
* https://web.archive.org/web/20160417193210/http://www-math.uni-paderborn.de/mca/mult.html
* Http://www-2.cs.cmu.edu/ {{Webarchive|url=https://web.archive.org/web/20130204053910/http://www-2.cs.cmu.edu/ |date=4 лютого 2013 }} ~ cburch/251/karat /
* Http://www.cs.pitt.edu/ {{Webarchive|url=https://web.archive.org/web/20220305181346/https://www.cs.pitt.edu/ |date=5 березня 2022 }} ~ 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|url=https://web.archive.org/web/20190913142043/http://www.ccas.ru/personal/karatsuba/divcru.htm |date=13 вересня 2019 }}
* Http://www.ccas.ru/personal/karatsuba/alg.htm {{Webarchive|url=https://web.archive.org/web/20121104053354/http://www.ccas.ru/personal/karatsuba/alg.htm |date=4 листопада 2012 }}
* Http://habrahabr.ru/blogs/algorithm/124258/ {{Webarchive|url=https://web.archive.org/web/20111228123900/http://habrahabr.ru/blogs/algorithm/124258/ |date=28 грудня 2011 }}

{{Алгоритми теорії чисел}}
[[Категорія:Довга арифметика]]
[[Категорія:Комп'ютерна арифметика]]
[[Категорія:Множення|Карацуби]]