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

Отже, коефіцієнти

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

Крайній стовпчик складається із заданих значень

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

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

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

можна отримати коефіцієнти :

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

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

Отже, відповіддю до нашої вихідної задачі буде

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