8.1. АНАЛОГИИ МЕЖДУ ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ

Наиболее очевидная аналогия между неотрицательными целыми числами и полиномами от одной переменной заключается в возможности представлять те и другие конечными степенными рядами . В случае целых чисел коэффициенты можно выбирать из множества при . В случае полиномов эти а, можно выбирать из некоторого множества коэффицентов 1), считая х переменной.

Существует естественная мера "размера" — это по существу длина степенного ряда, представляющего целое число или полином. В случае двоичного целого числа размером служит число битов, необходимых для его представления; в случае полинома размер — это число его коэффициентов. Таким образом, мы приходим к следующему определению.

Определение. Если неотрицательное целое число, то Если полином, то где степень полинома т.е. наибольшая степень переменной х с ненулевым коэффициентом.

Над целыми числами и полиномами можно выполнять приближенное деление. Если два целых числа и то найдется единственная пара целых чисел для которых

где соответственно частное и остаток от деления а на

Аналогично, если полиномы, причем отличен от постоянной, то можно найти такие полиномы что

Другая аналогия между целыми числами и полиномами — существование для тех и других удивительно быстрых алгоритмов умножения. В предыдущей главе мы показали, что два полинома степени с вещественными коэффициентами можно перемножить с помощью БПФ за время Здесь разумно измерять сложность числом арифметических операций, поскольку на практике мы представили бы полиномы их коэффициентами с фиксированной точностью и оперировали бы с полиномами, выполняя арифметические операции над такими коэффициентами.

Алгоритмом Шёнхаге — Штрассена из разд. 7.5 можно умножить два -разрядных двоичных целых числа за время Мы утверждаем, что в случае целых чисел интересны лишь битовые операции. Фактически только в двух ситуациях не стоит рассматривать умножение целых чисел как основную (первичную) операцию. Это прежде всего разработка аппаратной реализации умножения, где число битовых операций соответствует числу элементов, необходимых для схемы умножения, и кроме того, разработка алгоритмов любой точности для операций с фиксированной запятой, реализуемых на вычислительных машинах со словами фиксированной длины, где число битовых операций соответствует числу машинных команд, необходимых для умножения с точностью до разрядов.

Таким образом, результаты арифметических операций над полиномами и целыми числами окажутся очень похожими, если пользоваться двумя различными мерами сложности (арифметической и битовой). Эти две меры аналогичны в том смысле, что битовые операции — это операции над коэффициентами степенных рядов, представляющих целые числа, а арифметические — это операции над коэффициентами полиномов.