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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Історія[ред.ред. код]

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

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

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

У 1956 у А. М. Колмогоров сформулював гіпотезу, що нижня оцінка для  M (n) при будь-якому методі множення є також величина порядку n^2 (так звана «гіпотеза n^2 »Колмогорова). На правдоподібність гіпотези  n ^ 2 вказував той факт, що метод множення «в стовпчик» відомий не менше чотирьох тисячоліть (наприклад, цим методом користувалися шумери), і якби був більш швидкий метод множення, то він, ймовірно, вже був би знайдений. Однак, в 1960 році Анатолій Карацуба[3][4][5][6] знайшов новий метод множення двох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-(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\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 ,  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. \quad (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 не на два, а на більшу кількість доданків, то можна отримувати асимптотично кращі оцінки складності обчислення добутку (зведення в квадрат).

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Карацуба Є. А. Швидкі алгоритми і метод БВЕ, 2008.
  2. Алексєєв В. Б. Від методу Карацуба для швидкого множення чисел до швидких алгоритмах для дискретних функцій (1997) С. 20-27.
  3. Карацуба А., Офман Ю. Множення багатоцифрових чисел на автоматах (1962).
  4. Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (1975).
  5. Карацуба А. А. Складність обчислень (1995) С. 186-202.
  6. Кнут Д. Мистецтво програмування. — 3-е изд. — М.: Вильямс, 2007. — 832 с. — ISBN 0-201-89684-2.

Посилання[ред.ред. код]