Женский журнал

    Займемся общим многочленом вида: p(x) = a_nxⁿ + a_n-1x^n-1 + a_n-2x^n-2 + ... + a₂x² + a₁x + a₀.    Мы будем предполагать, что все коэффициенты a_n, ..., a₀ известны, постоянны и записаны в массив. Это означает, что единственным входным данным для вычисления многочлена служит значение x, а результатом программы должно быть значение многочлена в точке x.
    Стандартный алгоритм вычисления прямолинеен:
Evaluate(x)
x точка, в которой вычисляется значение многочлена
 
result = a[0] + a[1]*x
xPower = x
for i = 2 to n do
xPower = xPower*x
result = result + a*xPower
end for
return result

    Этот алгоритм совершенно прозрачен и его анализ очевиден. В цикле for содержится два умножения, которые выполняются n - 1 раз. Кроме того, одно умножение выполняется перед циклом, поэтому общее число умножений равно 2n - 1. В цикле выполняется также одно сложение, и одно сложение выполняется перед циклом, поэтому общее число сложений равно n.     Вычисление по схеме Горнера оказывается более эффективным, причем оно не очень усложняется. Эта схема основывается на следующем представлении многочлена: p(x) = (( ... ((a_nx + a_n-1)x + a_n-2)x + ... + a₂)x + a₁)x + a₀.    Вы можете легко проверить, что это представление задает тот же многочлен, что и выше. Соответствующий алгоритм выглядит так:

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

HornersMethod(x)
x		точка, в которой вычисляется значение многочлена
for i = n - 1 down to 0 do
	result = result*x
	result = result + a
end for
return result

    Цикл выполняется n раз, причем внутри цикла есть одно умножение и одно сложение. Поэтому вычисление по схеме Горнера требует n умножениё и n сложений - двукратное уменьшение числа умножений по сравнению со стандартным алгоритмом. Предварительная обработка коэффициентов     Результат можно даже улучшить, если обработать коэффициенты многочлена до начала работы алгоритма. Основная идея состоит в том, чтобы выразить многочлен через многочлены меньшей степени. Например, для вычисления значения x²⁵⁶ можно воспользоваться таким же циклом, как и в функции Evaluate в начале этой статьи; в результате будет выполнено 255 умножений. Альтернативный подход состоит в том, чтобы положить result = x*x, а затем семь раз выполнить операцию result = result*result. После первого выполнения переменная result будет содержать x⁴, после второго x⁸, после третьего x¹⁶, после четвертого x³², после пятого x⁶⁴, после шестого x¹²⁸, и после седьмого x²⁵⁶.
    Для того, чтобы метод предварительной обработки коэффициентов работал, нужно, чтобы многочлен был унимодальным (то есть старший коэффициент a_n должен равняться 1) , а степень многочлена должна быть на единицу меньше некоторой степени двойки (n = 2^k - 1 для некоторого k > 1). В таком случае многочлен можно представить в виде: p(x) = (x^j + b)q(x) + r(x),      где j = 2^k-1.     (1)     В обоих многочленах q и r будет вдвое меньше членов, чем в p. Для получения нужного результата мы вычислим по отдельности q(x) и r(x), а затем сделаем одно дополнительное умножение и два сложения. Если при этом правильно выбрать значение b, то оба многочлена q и r оказываются унимодальными, причем степень каждого из них позволяет применить к каждому из них ту же самую процедуру. Мы увидим, что ее последовательное применение позволяет сэкономить вычисления.
    Вместо того, чтобы вести речь о многочленах общего вида, обратимся к примеру. Рассмотрим многочлен: p(x) = x⁷ + 4x⁶ - 8x⁴ + 6x³ + 9x² + 2x - 3.     Определим сначала множитель x^j + b в уравнении (1). Степень многочлена p равна 7, то есть 2³ - 1, поэтому k = 3. Отсюда вытекает, что j = 2² = 4. Выберем значение b таким образом, чтобы оба многочлена q и r были унимодальными. Для этого нужно посмотреть на коэффициенты a_j-1 в p и положить b = a_j-1 - 1. В нашем случае это означает, что b = a₃ - 1 = 5. Теперь мы хотим найти значения q и r, удовлетворяющие уравнению: x⁷ + 4x⁶ - 8x⁴ + 6x³ + 9x² + 2x - 3 = (x⁴ + 5)q(x) + r(x).     Многочлены q и r совпадают соответственно с частным и остатком от деления p на x⁴ + 5. Деление с остатком дает: p(x) = (x⁴ + 5)(x³ + 4x² + 0x + 8) + (x³ - 11x² + 2x - 37).     На следующем шаге мы можем применить ту же самую процедуру к каждому из многочленов q и r: q(x) = (x² - 1)(x + 4) + (x + 12),    r(x) = (x² + 1)(x - 11) + (x - 26).     В результате получаем: p(x) = (x⁴ + 5)((x² - 1)(x + 4) + (x + 12)) + ((x² + 1)(x - 11) + (x - 26)).     Посмотрев на этот многочлен, мы видим, что для вычисления x² требуется одно умножение; еще одно умножение необходимо для подсчета x⁴ = x²*x². Помимо этих двух умножений в вычислении правой части равенства участвуют еще три умножения. Кроме того, выполняется 10 операций сложения. В таблице 1 приведены сравнительные результаты анализа этого метода и других методов вычисления. Экономия не выглядит значительной, однако это объясняется тем, что мы рассматриваем лишь частный случай. Общую формулу для сложности можно вывести, внимательно изучив процедуру. Заметим прежде всего, что в равенстве (1) участвуют одно умножение и два сложения. Поэтому для числа умножений M = M(k) и числа сложений A = A(k) мы получаем следующий набор рекуррентных соотношений:

M(1) = 0	A(1) = 0
M(k) = 2M(k - 1) + 1 при k > 1	A(k) = 2A(k - 1) + 2 при k > 1.

Способ	Умножения	Сложения
Стандартный	13	7
Схема Горнера	7	7
Предварительная обработка	5	10

    Решая эти соотношения, мы заключаем, что число умножений приблизительно равно N/2, а число сложений приблизительно равно (3N - 1)/2. Неучтенными, однако, остались умножения, необходимые для подсчета последовательности значений x², x⁴, x⁸, ..., x^2k-1; на это требуется дополнительно k - 1 умножение. Поэтому общее число умножений приблизительно равно N/2 + log₂N.

Способ	Умножения	Сложения
Стандартный	2N - 1	N
Схема Горнера	N	N
Предварительная обработка	N/2 + log2N	(3N - 1)/2

    В таблице 2 приведены результаты сравнительного анализа стандартного алгоритма, схемы Горнера и алгоритма с предварительной обработкой коэффициентов. При сравнении последних двух алгоритмов видно, что нам удалось сэкономить N/2 - log₂N умножений, но за счет дополнительных (N - 1)/2 сложений. Во всех существующих вычислительных системах обмен умножений на сложения считается выгодным, поэтому предварительная обработка коэффициентов повышает эффективность.