Для произведения двух многочленов первой степени P = aX + b и Q = cX + d достаточно легко находим формулы U = ac, W = bd, V = (a + b)(c + d) и PQ = =UX2 + (V – U – W)X +W, в которых появляются только три элементарных умножения, но четыре сложения. Можно рекурсивно применить этот процесс для умножения двух многочленов P и Q степени 2l – 1, представляя их в виде и применяя предыдущие формулы для вычисления PQ в зависимости от A, B, C и D, где каждое произведение AB, CD и (A + B)(C + D) вычисляется с помощью рекурсивного применения данного метода (это метод Карацубы). Всё это даёт мультипликативную сложность M(2l) и аддитивную сложность A(2l) такие, что:

M(2l) = 3M(2l – 1),…, M(2) = 3M(1), M(1) = 1,

A(2l) = 3A(2l – 1) + 3*2l,…, A(2) = 3A(1) + 6, A(1) = 1.

В этой последней формуле член 3*2l представляет собой число элементарных сложений, необходимых, чтобы сделать два сложения многочленов степени 2l – 1 – 1 (a + b и c + d) и два вычитания многочленов степени 2l – 1 (U – V – W). Суммируя каждое из этих выражений, находим для n, являющегося степенью двойки:

M(n) = nlog3/log2 » n1,585 и A(2) =7 nlog3/log2 – 6n.

К сожалению, этот принцип остаётся теоретическим, и на его основе нужно построить итерационный алгоритм, чтобы получить разумную эффективность (цена управления рекурсией очень велика).

3.4 Вычисление многочленов

Рассмотрим общую задачу вычисления многочлена n-й степени

u(x) = unxn + un – 1xn – 1 + . + u1x + u0, un ¹ 0, (1)

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

u(x) = (…(unx + un – 1)x + …)x + u0. (2)

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

Было предложено несколько обобщений схемы Горнера. Посмотрим сначала, как вычисляется в случае, когда – комплексное число, а коэффициенты вещественны. Комплексное сложение и умножение можно очевидным образом свести к последовательности обычных операций над вещественными числами:

вещественное + комплексное требует 1 сложение,

комплексное + комплексное требует 2 сложения,

вещественное * комплексное требует 2 умножения,

комплексное * комплексное требует 4 умножения и 2 сложения

или 3 умножения и 5 сложений.

Следовательно, схема Горнера (2) требует 4n – 2 умножений и 3n – 2 сложений или 3n – 1 умножений и 6n – 5 сложений для вычисления u(z), когда z комплексное. Вот другая процедура для вычисления u(x + iy):

a1 = un, b1 = un – 1, r = x + x, s = x2 + y2; (3)

aj = bj – 1 + raj –1, bj = un – j – saj –1, 1 < j £ n.

Легко доказать индукцией по n, что u(z) = zan + bn. Эта схема требует 2n + 2 умножений и 2n + 1 сложений, так что при n ³ 3 она лучше схемы Горнера.

Рассмотрим процесс деления многочлена u(x) на многочлен x – x0. В результате такого деления мы получаем u(x) = (x – x0)q(x) + r(x); здесь deg(r) < 1, поэтому r(x) есть постоянная, не зависящая от x и u(x0) = 0*q(x0) + r = r. Анализ этого процесса деления показывает, что вычисления почти те же самые, что в схеме Горнера для определения u(x0). Аналогично, когда мы делим u(z) на многочлен (z – z0)(z – z0) = z2 – 2x0z + x02 + y02, то соответствующие вычисления эквивалентны процедуре (3); мы получаем

u(z) = (z – z0)(z – z0)q(z) + anz + bn;

следовательно,

u(z0) = anz0 + bn.

Вообще, когда мы делим u(x) на, f(x) получая u(x) = f(x) q(x) +­ r(x), то из равенства f(x0) = 0 следует u(x0) = r(x0); это наблюдение ведёт к дальнейшим обобщениям правила Горнера. Мы можем положить, например, f(x) = x­2 – x02; это даст нам схему Горнера «второго порядка»

u(x) = (…(u2ë n/2 û x2­­­ + u2ë n/2 û – 2)x2 + u0 +

+((….u2é n/2 ù - 1 x2 + u2é n/2 ù - 3)x2 + … +)x2u1) x. (4)

3.4.2 Интерполяционная формула Ньютона и табулирование значений многочлена

Рассмотрим специальный случай вычисления многочлена. Интерполяционный многочлен Ньютона степени n, определяемый формулой

u[n](x) = an(x – x0) (x – x1)…(x – xn – 1) +…+ an (x – x0) (x – x1) + a1 (x – x0) + a0, (5)

является единственным многочленом степени £ n от x, который принимает предписанные значения y0, y1, …, yn в заданных n + 1 различных точках x0, x1, …, xn соответственно. После того, как значения постоянных a найдены, интерполяционная формула Ньютона становится удобной для вычислений, так как мы можем, обобщив правило Горнера, записать

u[n](x) = ((…(an(x – xn – 1) + an – 1)(x – xn – 2) + …)(x – x1) + a1)*

*(x – x0) + a0. (6)

Теперь рассмотрим, как находятся постоянные a в формуле Ньютона. Их можно определить, находя «разделённые разности» и сводя вычисления в следующую таблицу (иллюстрирующую случай n = 3):

y0

(y1 – y0)/(x1 – x0) = y¢1

y1 (y2 – y’1)/(x2 – x0) = y¢¢2

(y2 – y1)/(x2 – x1) = y¢2 (y’’3 – y’’2)/(x3 – x0) = y¢¢¢3

y2 (y3 – y’2)/(x3 – x1) = y¢¢3

(y3 – y2)/(x3 – x2) = y¢3

y3 (7)

Можно доказать, что a0 = y0, a1 = y’1, a2 = y’2, и т. д. Следовательно, для нахождения величин может быть использована следующая вычислительная процедура (соответствующая таблице (7)):

Начать с того, что установить (a0, a1, …, an) ¬ (y0, y1, … , yn); затем для k = 1, 2, …, n (именно в таком порядке) установить yj ¬ (yj – yj – 1)/(xj – xj – k) для j = n, n – 1, …, k (именно в таком порядке).

Если мы хотим вычислить многочлен u(x) степени n сразу для многих значений x, образующих арифметическую прогрессию (т. е. хотим вычислить u(x0), u(x0 + h), u(x0 + 2h),…), то весь процесс можно после нескольких первых шагов свести к одному только сложению вследствие того факта, что n-я разность от многочлена есть постоянная.

1 Найти коэффициенты bn, …, b1, b0 представления нашего многочлена в виде интерполяционного многочлена Ньютона

u(x) = bn / n! hn(x – x0 – (n – 1)h)…(x – x0 – h)(x – x0) +…+ b2 / 2! h2* *(x – x0 – h)(x – x0) + b1 / h2 (x – x0) + b0. (8)

(Это можно сделать, беря повторные разности, в точности так же, как мы определяли выше постоянные a в (5) (надо принять xj = x0 + jh), с тем исключением, что все деления на xj – xj – k из вычислительной процедуры устраняются.)

2 Установить x ¬ x0.

3 Теперь значением u(x) является b0.

4 Установить bj ¬ bj + bj + 1 для j = 0, 1, …, n – 1 (именно в таком порядке). Увеличить x на h и вернуться в шаг 3.

4. Дискретное логарифмирование

Пусть p – простое число. Ещё Эйлер знал, что мультипликативная группа кольца циклична, т. е. существуют такие целые числа а, что сравнение

ax º b (mod p) (2)

разрешимо относительно x при любом bÎZ, не делящимся на p. Числа а с этим свойством называются первообразными корнями, и количество их равно j(p – 1), где j – функция Эйлера. Целое х, удовлетворяющее сравнению (2), называется индексом или дискретным логарифмом числа b.