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

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

Множення Карацуби - метод швидкого множення, який дозволяє перемножувати два 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), і, отже, справедливою є нерівність:

Зауваження[ред.ред. код]

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

Якщо розбивати не на два, а на більшу кількість доданків, то можна отримувати асимптотично кращі оцінки складності обчислення добутку (піднесення до квадрату).

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

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

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

  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.

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