Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчисл (стр. 2 из 3)

Якщо

– час, необхідне для виконання множення -розрядних чисел, то ми маємо

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

,

якщо вибрати

– достатньо великим, для того, щоб ця нерівність виконувалася при , отримаємо

Тобто час, затрачуваний на множення, можна скоротити з величини порядку

до величини порядку , і, звичайно, при великому цей алгоритм набагато швидше.

Схожий, але більш складний метод виконання множення із часом порядку

був уперше запропонований А. Карацубою.

Час виконання можна скоротити ще більше, якщо помітити, що тільки що розглянутий метод є окремим випадком (при

) більш загального методу, що дає

для будь-якого фіксованого

. Цей більш загальний метод можна отримати в такий спосіб. Розіб'ємо

і

на

частин:

де кожне

і кожне є розрядними числами. Розглянемо многочлени

,

і покладемо

.

Оскільки

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

Цього можна досягти, обчислюючи

.

Коефіцієнти будь-якого многочлена степені

можна записати у вигляді лінійної комбінації значень цього многочлена в різних точках. Час, необхідний для узяття такої комбінації, якнайбільше пропорційно . У дійсності добутком є, точно кажучи, не добутками -розрядних чисел, а добутками чисел, розряд яких не перевищує , де – фіксована величина, що залежить від . Легко скласти програму множення для – розрядних чисел, що вимагає виконання лише операцій, тому що при фіксованому два добутки -розрядних чисел на -розрядні можна одержати за операцій. Можна показати, що для цього методу

.

Теорема 2

Для кожного

існує така постійна і такий алгоритм множення, що число елементарних операцій , які необхідно виконати, щоб помножити два - розрядних числа, відповідає оцінці . Ця теорема ще не найкращий результат. Для практичних цілей великий недолік, що метод різко ускладнюється при тобто . Ця теорема незадовільна й з теоретичної точки зору, тому що в ній не повною мірою використовується лежачий у її основі метод багаточленів.

Перш ніж розглянути алгоритм Тоома-Кука, розберемо один приклад. На цьому прикладі не можна побачити ефективність методу, оскільки ми маємо справу з невеликими числами. Але можна побачити деякі корисні спрощення, що застосовні в загальному випадку.

Приклад

Припустимо, нам потрібно помножити

на .

У двійковій системі числення

на .

Нехай

.

Багаточлени

, .

Звідси знаходимо

:

(3.1)

Тепер, використовуючи п'ять останніх величин, знайдемо п'ять коефіцієнтів багаточлена

.

Для перебування коефіцієнтів багаточлена

при заданих значеннях

можна скористатися одним цікавим невеликим алгоритмом. Спочатку запишемо

,

Позначаючи ліву частину виразу через

ми бачимо, що