Xreferat.com » Рефераты по математике » Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

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

Методи множення. Складність обчислень" width="14" height="15" align="BOTTOM" border="0" />. Цей більш загальний метод можна отримати в такий спосіб. Розіб'ємо


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


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


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


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

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


і покладемо


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


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

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


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


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


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

Теорема 2

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

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

Приклад

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

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

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

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

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

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

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

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

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


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


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

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


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


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


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


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


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


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


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


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


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


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


Послідовно виходять коефіцієнти багаточленів


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


Відповідно до останньої таблиці ми маємо


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

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

Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: