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

,

і покладемо

.

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

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

.

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

.

Теорема 2

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

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

Приклад

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

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

Нехай .

Багаточлени , .

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

(3.1)

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

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

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

,

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

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

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