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

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

Обчислення значень многочленів.

Нехай – довільне кільце. Розглянемо добре відомий алгоритм Руфіні - Горнера для обчислення значень многочлена над кільцем у точці.

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

Алгоритм Руфіні-Горнера дозволяє отримати не тільки значення . Як показує наступна теорема, величини є в точності коефіцієнтами многочлена, що є лишком від ділення многочлена на .

Теорема 1

Справедлива рівність

Доведення

Маємо

Методи множення

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

де – ²найбільш значуща половина² числа , а – ²найменш значуща половина²; подібним же чином , .

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

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

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

,

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

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

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

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

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

і

на частин: