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

Полином – многочлен.

Общая запись: y = anxn + an-1xn-1+…+a1x + a0

Вычисление х в степени n (бинарный метод, метод множителей, степенное дерево, аддитивная сложность).

Бинарный метод

Запишем n в двоичной системе счисления и заменим в этой записи каждую цифру “1” парой букв SX, а каждую цифру “0” – буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат, читаемый слева на право, превращается в правило вычисления хⁿ, если букву “S” интерпретировать как операцию возведения в квадрат (S – square – квадрат), а букву “X ” – как операцию умножения на х.

Пример: n = 46, переводим в двоичную n = 101110₂, заменяем SxSSxSxSxS, записываем правило: x²x⁴x⁵x¹⁰x¹¹x²²x²³x⁴⁶ итого 8 умножений

Метод множителей

Если n=p·q, где р – наименьший простой множитель числа n и q >1, то для вычисления хⁿ мы можем сначала вычислить х^р, а затем возвести это число в степень q. В случае, когда n простое, мы можем вычислить сначала число х^n-1, а затем умножить его на х.

Если n=1, число хⁿ имеется без всяких вычислений. Многократное применение этих правил дает нам процедуру вычисления хⁿ для любого данного n.

Пример: n = pq ; p=7, q=13, n=91

y = x⁷ = ((x²)x)²x

y¹³ = (((y²)y)²)²y

итого 9 умножений

Степенное дерево

Допустим нужно вычислить xⁿ. Находим на дереве число n, и тогда путь от корня дерева к узлу n определяет последовательность эффективного вычисления xⁿ .

Аддитивная сложность

Аддитивной цепочкой для n называется всякая последовательность целых чисел 1=a₀,…,a_r=n, обладающих тем свойством, что a_i=a_j+a_k при некоторых k ≤ j < i для всех i=1,2,…,r.

Заметим, что а₁ всегда равно 2, а₂ равно 2, 3 или 4.

Наименьшее значение r длины аддитивных цепочек для n обозначается через l(n) и называется аддитивной сложностью или высотой числа n.

Схема Горнера.

f(x)=a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀, a_n≠0

f(x)=(…(a_nx+a_n-1)x+…)x+a₀

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

Обобщенная схема Горнера.

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

F’(x)=na_nx^n-1+(n -1)a_n-1x^n-2+…+a₁

Это удобно сделать, положив

c₀=a_n, b₀=0

c_j=c_j-1x+a_n-j, b_j=b_j-1x+c_j-1, 1≤j≤n.

Здесь c_n=f(x) и b_n=f’(x), вычисление требует (2n -1) умножений и (2n -1) сложений, причем нет необходимости хранить в памяти новые коэффициенты j·a_j.

Пример: f’(x)=2x⁷+0x⁶-3x⁵-4x⁴-x³-8

C₀=a₅=2

……

C₅=C₄*x+a₀ = (((2x²-3)*x-4)*x-1)*x-8= f(x)

b₀=0

b₁=b₀*x+C₀=2

…….

b₅=b₄x+C₄=2x⁴+3x²-4x-4

Литература: [1], [5].

5. Нахождение нод полиномов от одной переменной

Наивный метод.

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

Модулярные методы.

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

Вопросы: 1.- как вычислять нетривиальный НОД? 2.- что делать, если модулярный НОД не является модулярным образом НОД?м 3.- какова стоимость этого метода? Граница для коэффициентов НОД двух полиномов.

Неравенство Ландау-Миньотта, следствия.

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

Соответствие модулярное – целое.

Соответствие модулярное-целое: Лемма 1. Если число p не делит старший коэффициент НОД(a,b) полиномов a и b, то степень НОД(a_р,b_р) больше или равна степени НОД(f,g). Формулировка, которой легче пользоваться: Следствие. Если число р не делит старшие коэффициенты полиномов a и b (в частности, может делить один из них, но не оба одновременно), то степень НОД (a_р,b_р) >= степени НОД(a,b). Поскольку НОД является единственным полиномом этой степени, который делит и a, и b, то мы можем проверить корректность наших вычислений НОД: если результат имеет ту же степень, что и НОД(a_р,b_р) (где р удовлетворяет предположению следствия), и если он делит a и b, то он совпадает с НОД (с точностью до целого множителя). Пример. Пусть a=х⁸+х⁶-3х⁴+3х³+х²+2х-5; b=3х⁶+5х⁴-4х²-9х+21. Тогда НОД(a₂,b₂) = х+1, хотя мы уже знаем, НОД(a,b)=1.

Лемма 2. Пусть c=НОД(a,b). Если число р удовлетворяет условию следствия и, если р не делит Res_х(a/c,b/c), то НОД(a_р,b_р)=c_р. Если НОД(a_р,b_р)=НОД(a,b)_р, то мы говорим, что редукция задачи хорошая или что р - число с хорошей редукцией. В противном случае мы говорим, что р - число с плохой редукцией. Из этой леммы, в частности, следует, что существует только конечное число значений р, таких, что степень НОД(a_р,b_р) отличается от степени НОД (a,b): - это те р, которые делят НОД старших коэффициентов; - это те р, которые делят результант, упоминающийся в лемме (он не нулевой и потому имеет только конечное число делителей).

Вычисление НОД.

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

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

Цикл до ∞

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

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

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

если делит (c, a) и делит (c, b) то

выход c;

где:

алгоритм «граница_Ландау_Миньотта» применяет следствия и неравенства; алгоритм «найти_большое_простое» - возвращает большое простое число, не делящее его аргумент (каждый раз новое число); алгоритм «степень_остатка» проверяет, что редукция по модулю p не меняет степень, т.е. p не делит старший коэффициент; алгоритм «модулярный_НОД» применяет алгоритм Евклида по модулю p; алгоритм «делит» проверяет, что полиномы делятся над кольцом целых чисел. Недостаток этого метода состоит в том, что он требует многочисленных вычислений по модулю р, которое может быть довольно большим. Поэтому обычно примен-ся метод, использующий несколько маленьких простых чисел и китайскую теорему об остатках. Если мы вычислим c_р и c_q, где c-требуемый НОД, а р,q-два простых числа, то эта теорема позволяет нам вычислить c_рq.

Оценка стоимости алгоритма.

Оценим стоимость алгоритма. Время вычисления ограничивается величиной О(n³·log₂³·H), где n-такое, что степени полиномов a, b не больше этого числа; H-величина, удовлетворяющая неравенству.

Литература: [1], [5], [6].

ТЕОРИЯ ИНФОРМАЦИИ