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

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

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

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

Історія

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

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

${\displaystyle M(n)=O(n^{2}).}$

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

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

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

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

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

Опис методу

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

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

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

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

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

${\displaystyle X=e_{0}+2e_{1}+\ldots +2^{n-1}e_{n-1},}$

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

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

${\displaystyle X=X_{1}+2^{k}X_{2},}$

де

${\displaystyle X_{1}=e_{0}+2e_{1}+\ldots +2^{k-1}e_{k-1}}$

і

${\displaystyle X_{2}=e_{k}+2e_{k+1}+\ldots +2^{k-1}e_{n-1},}$

знаходимо:

${\displaystyle 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)}$

Числа ${\displaystyle X_{1}}$і${\displaystyle X_{2}}$ є ${\displaystyle k}$-значними. Число ${\displaystyle X_{1}+X_{2}}$ може мати ${\displaystyle k+1}$ знаків. У цьому випадку представимо його у вигляді ${\displaystyle 2X_{3}+X_{4}}$, де ${\displaystyle X_{3}}$ є ${\displaystyle k}$-значне число, ${\displaystyle X_{4}}$ — однозначне число. Тоді

${\displaystyle (X_{1}+X_{2})^{2}=4X_{3}^{2}+4X_{3}X_{4}+X_{4}^{2}.}$

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

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

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

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

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

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

отримуємо

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

${\displaystyle \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=}$

${\displaystyle =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)=}$

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

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

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

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

${\displaystyle E_{n}=\ldots =e_{2^{m}-1}=0.}$

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

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

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

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

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

${\displaystyle A=A_{1}+2^{k}A_{2},\quad B=B_{1}+2^{k}B_{2},}$

де ${\displaystyle A_{1},\;A_{2},\;B_{1},\;B_{2}}$ — ${\displaystyle k}$-значні числа, знаходимо:

${\displaystyle 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). Якщо тепер позначити символом ${\displaystyle \varphi (n)}$ кількість операцій, достатню для множення двох ${\displaystyle n}$-значних чисел за формулою (3), то для ${\displaystyle \varphi (n)}$ виконується нерівність (2), і, отже, справедливою є нерівність:

${\displaystyle \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.

Зауваження

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

Якщо розбивати ${\displaystyle X}$ не на два, а на більшу кількість доданків, то можна отримати асимптотично кращі оцінки складності обчислення добутку (піднесення до квадрату). Зокрема, такий шлях застосовано в ^[en].

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

Примітки

1. Карацуба Є. А. Швидкі алгоритми і метод БВЕ [ 4 листопада 2012 у Wayback Machine.], 2008.
2. Алексєєв В. Б. Від методу Карацуба для швидкого множення чисел до швидких алгоритмах для дискретних функцій // Тр. МІАН. — 1997. — С. 20-27.
3. Карацуба А., Офман Ю. Множення багатоцифрових чисел на автоматах // Доповіді Академії Наук СРСР. — 1962. — № 2.
4. Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen // Elektronische Informationsverarbeitung und Kybernetik. — 1975.
5. Карацуба А. А. Складність обчислень // Тр. МІАН. — 1995. — С. 186-202.
6. Кнут Д. Мистецтво програмування. — 3-е изд. — М. : Вильямс, 2007. — 832 с. — .

Посилання

• Http://212.cmc-msu.ru/files/kniga.html [ 3 січня 2022 у Wayback Machine.]
• Http://numbers.computation.free.fr/Constants/Algorithms/representation.html [ 3 січня 2022 у Wayback Machine.]
• 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 /
• 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.]