Відкрити головне меню

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

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

Зміст

ІсторіяРедагувати

Проблема оцінки кількості бітових операцій, необхідних для обчислення добутку двох n-значних чисел, або проблема зростання функції складності множення   при   є нетривіальною проблемою теорії швидких обчислень[джерело?].

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

 

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

 

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

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

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

Опис методуРедагувати

Перший варіантРедагувати

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

 

Оскільки  , то множення двох чисел   і   еквівалентне за складністю виконання піднесенню до квадрата.

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

 

де  .

Будемо вважати для простоти, що  . Представляючи   у вигляді

 

де

 

і

 

знаходимо:

 

Числа  і є -значними. Число   може мати   знаків. У цьому випадку представимо його у вигляді  , де  є -значне число,   - однозначне число. Тоді

 

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

 

де   є абсолютна константа. Справді, права частина (1) містить суму трьох квадратів  -значних чисел,  , які для свого обчислення вимагають   операцій. Усі інші обчислення в правій частині (1), а саме множення на  , п'ять додавань і одне віднімання не більше ніж  -значних чисел вимагають по порядку не більше   операцій. Звідси випливає (2). Застосовуючи (2) послідовно до

 

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

 

отримуємо

 
 
 
 

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

 

Якщо ж   не є ступенем двох, то визначаючи ціле число   нерівностями  , представимо   як  -значне число, тобто вважаємо останні   знаків рівними нулю:

 

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

Другий варіантРедагувати

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

 

Нехай, як і раніше  ,  ,   і   - два  -значних числа. Представляючи   і   у вигляді

 

де   -  -значні числа, знаходимо:

 

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

 

ЗауваженняРедагувати

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

Якщо розбивати   не на два, а на більшу кількість доданків, то можна отримувати асимптотично кращі оцінки складності обчислення добутку (піднесення до квадрату). Зокрема, такий шлях застосовано в алгоритмі Тоома — Кука[en].

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

ПриміткиРедагувати

  1. Карацуба Є. А. Швидкі алгоритми і метод БВЕ, 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 с. — ISBN 0-201-89684-2.

ПосиланняРедагувати