Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень
і
![]()
на
частин:
![]()
де кожне
і кожне
є
розрядними
числами. Розглянемо
многочлени
,
![]()
і покладемо
.
Оскільки
і
,
то ми маємо
,
і тому, якщо
знати коефіцієнти
,
можна легко
обчислити
.
Завдання полягає
в тому, щоб знайти
гарний спосіб
обчислення
коефіцієнтів
,
виконуючи лише
операцій множення
-
розрядних чисел
плюс деякі
додаткові
операції, для
яких час виконання
пропорційно
.
Цього можна досягти, обчислюючи
.
Коефіцієнти
будь-якого
многочлена
степені
можна
записати у
вигляді лінійної
комбінації
значень цього
многочлена
в
різних точках.
Час, необхідний
для узяття
такої комбінації,
якнайбільше
пропорційно
.
У дійсності
добутком
є, точно кажучи,
не добутками
-розрядних
чисел, а добутками
чисел, розряд
яких не перевищує
,
де
–
фіксована
величина, що
залежить від
.
Легко скласти
програму множення
для
– розрядних
чисел, що вимагає
виконання лише
операцій, тому
що при фіксованому
два добутки
-розрядних
чисел на
-розрядні
можна одержати
за
операцій. Можна
показати, що
для цього методу
.
Теорема 2
Для кожного
існує така
постійна
і такий алгоритм
множення, що
число елементарних
операцій
,
які необхідно
виконати, щоб
помножити два
-
розрядних
числа, відповідає
оцінці
.
Ця теорема ще
не найкращий
результат. Для
практичних
цілей великий
недолік, що
метод різко
ускладнюється
при
тобто
.
Ця теорема
незадовільна
й з теоретичної
точки зору,
тому що в ній
не повною мірою
використовується
лежачий у її
основі метод
багаточленів.
Перш ніж розглянути алгоритм Тоома-Кука, розберемо один приклад. На цьому прикладі не можна побачити ефективність методу, оскільки ми маємо справу з невеликими числами. Але можна побачити деякі корисні спрощення, що застосовні в загальному випадку.
Приклад
Припустимо,
нам потрібно
помножити
на
.
У двійковій
системі числення
на
.
Нехай
.
Багаточлени
,
.
Звідси знаходимо
:
(3.1)
Тепер, використовуючи
п'ять останніх
величин, знайдемо
п'ять коефіцієнтів
багаточлена
.
Для перебування коефіцієнтів багаточлена
![]()
при заданих
значеннях
можна скористатися
одним цікавим
невеликим
алгоритмом.
Спочатку запишемо
,

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

Отже, коефіцієнти
можна обчислити
за допомогою
дуже простого
методу, якому
можна продемонструвати
для багаточлена
,
визначеного
співвідношеннями
(3.1):

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

У загальному вигляді можна записати

ця формула
показує, яким
чином з коефіцієнтів
можна отримати
коефіцієнти
:

Послідовно виходять коефіцієнти багаточленів
Відповідно до останньої таблиці ми маємо
![]()
Отже, відповіддю
до нашої вихідної
задачі буде
де
виходить у
результаті
дій додавання
і зрушення.
Крім того, якщо
коефіцієнти
багаточлена
– ненегативні,
то такими будуть
і числа
,
а тоді всі проміжні
результати,
одержувані
в процесі проведення
обчислення,
є ненегативними.
Размещено на