Вычисление полиномов

Полином = многочлен. Бинарный метод.Для возведения за минимальное количество операций, запишем в двоичной СС, единицу заменим на SX, а ноль на X. Крайнюю левую пару SX вычеркнем. Получим правило, где S – возведение в степень 2, а X – умножение на X.

Метод множителей.Если , где p – наименьший простой множитель числа n и q>1, то для вычисления мы можем сначала вычислить , а затем возвести это число в степень . В случае, если простое, можно сначала вычислить , а затем результат умножить на .Многократное применение этих правил даёт процедуру вычисления для любого данного . Степенное дерево

Путь от корня к узлу определяет последовательность вычислений.

Аддитивная сложность.Аддитивной цепочкой для n называется всякая последовательность целых чисел обладающих тем свойством, что при некоторых для всех .Заметим, что всегда равно 2, а равно 2, 3 или 4.Наименьшее значение длины аддитивных цепочек для обозначается через и называется аддитивной сложностью или высотой числа. Схема Горнера

Весь процесс требует умножений и сложений.

Обобщённая схема Горнера используется, когда требуется вычислить сразу полином и его производную.

Это удобно сделать, положив . Здесь и . Вычисление требует умножений и сложений, причём, нет необходимости хранить в памяти новые коэффициенты .

КА 5. Нахождение НОД от одной переменной

Пусть и полиномы, и мы хотим вычислить их НОД. «наивный» метод основан на алгоритме Евклида. Такие действия над полиномами с рациональными коэффициентами требуют неоднократного вычисления НОД целых чисел, и целые числа, фигурирующие в этих вычислениях, не всегда являются маленькими.

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

Неравенство Ландау-Миньотта. Теорема. Пусть –делитель полинома , где –целые числа). Тогда . Следствие 1. Каждый коэффициент НОД полиномов , ограничен величиной сверху. Следствие 2. Каждый коэффициент НОД полиномов , ограничен величиной снизу.

Лемма 1. Если число не делит старший коэффициент полиномов и (в частности, может делить один из них, но не оба одновременно), то степень степени . Поскольку НОД является единственным полиномом этой степени, который делит и , и , то мы можем проверить корректность наших вычислений НОД: если результат имеет ту же степень, что и (где удовлетворяет предположению следствия), и если он делит и , то он совпадает с НОД (с точностью до целого множителя).

Лемма 2.Пусть . Если число удовлетворяет условию следствия и, если не делит , то . Если , то мы говорим, что редукция задачи хорошая, или что – число с хорошей редукцией. В противном случае мы говорим, что –число с плохой редукцией. Из этой леммы, в частности, следует, что существует только конечное число значений , таких, что степень отличается от степени : это те , которые делят НОД старших коэффициентов или делят результат, упоминающийся в лемме. Вычисление НОД.Очевидный метод вычисления нетривиального НОД – воспользоваться неравенством Ландау-Миньотта, которое позволяет определить такое число , что все коэффициенты ограничены , и производить вычисления по модулю простого числа, большего, чем .

M := граница_Ландау_Миньотта(a,b);

цикл до бесконечности

p := найти_большое_простое(2M);

еслистепень_остатка(p, a) истепень_остатка(p, b) то

c := модулярный_НОД(a, b, p);

если делит(c, a) и делит(c, b) то вернутьc;

Алгоритм «степень_остатка» проверяет, что редукция по модулю не меняет степень, т.е. не делит старший коэффициент полинома. Все остальные алгоритмы и так понятно что делают.

Недостаток данного метода в том, что он требует многочисленных вычислений по модулю , которое может быть довольно большим. Поэтому обычно применяется метод, использующий несколько маленьких простых чисел и китайскую теорему об остатках. Если мы вычислим и , где –требуемый НОД, а – два простых числа, то эта теорема позволяет нам вычислить .