Программа 1.3 Расчет значения полинома по схеме Горнера с использованием указателя

Таблица 1. Границы размеров задач в зависимости от сложности алгоритма

Таблица 2. Эффект стократного увеличения скорости счёта

Видно, что для алгоритма A₅ стократное увеличение скорости увеличивает размер задачи, которую можно решить за то же время, только на 6, тогда как для алгоритма A₃ размер задачи удесятеряется.

Вместо эффекта увеличения скорости рассмотрим эффект применения более действенного алгоритма. Вернёмся к таблице 1. Если в качестве основы сравнения взять 1 минуту, то, заменяя алгоритм A₄ алгоритмом A₃, можно решить задачу в 6 раз бóльшую, а, заменяя A₄ на A₂, можно решить задачу, бóльшую в 125 раз. Эти результаты производят гораздо бóльшее впечатление, чем пятикратное улучшение, достигаемое за счёт 100-кратного увеличения скорости. Если в качестве основы для сравнения взять один час, то различие оказывается еще более значительным. Отсюда можно заключить, что асимптотическая сложность алгоритма служит важной мерой качества алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.

Но необходимо учитывать не только порядок n, но и константу c, которая тоже может влиять на качество алгоритма. Предположим, что временные сложности алгоритмов A₁, …, A₅ в действительности равны соответственно 1000×n, 100×n×logn, 10×n², n³ и 2ⁿ. Тогда A₅ будет наилучшим для задач размера 2£n£9, A₃ - для 10£n£58, A₂ - для 59£n£1024, A₁ - для n>1024.

Пример 1.1. Составить на языке C программу расчета значения полинома по заданным степени полинома, его коэффициентам и величине x.

Требуется вычислить значение:

P_n(x) = a_n×xⁿ + a_n-1×x^n-1 + … + a₁×x + a₀ (1.1)

по заданным: a₀, a_1, …, a_n; степени полинома n и значению x. Попробуем написать программу для этой процедуры в виде функции на языке C, не вдаваясь в подробности ввода указанной информации.

Сначала составим программу, пользуясь прямым алгоритмом, не учитывая особенности машинных программ.

// Программа 1.1

double Polinom_Calculation(double Array[], unsigned int Order, double Value)

/* Функция расчета значения полинома по заданным коэффициентам, степени

полинома и значению переменной x. */

{

double p=Array[0];

unsigned int index;

/* Array - массив коэффициентов полинома a₀, a_1,…, a_n; Order - степень полинома;

Value - значение переменной x, для которого рассчитывается P_n(x);

p и index - вспомогательные переменные. */

for (index=1; index<=Order; index++)

p+=Array[index]*pow(Value,index);

return p;

}//Конец Polinom_Calculation

Из-за того, что в языках C,C++ не определена операция возведения в степень, в программе воспользовались библиотечной функцией pow(y,z), которая возводит переменную y в степень z и описана в библиотеке math.h Borland C++.

Данный алгоритм потребовал n сложений, n умножений и n операций возведения в степень. Но операция возведения в степень - одна из самых медленных в ЭВМ, поэтому приведённый алгоритм можно признать неудачным с точки зрения временной сложности. Попробуем составить более быстрый алгоритм. Здесь на помощь приходит классическая схема Горнера (Horner’s rule). Представим (1.1) в следующем виде:

P_n(x) = a_n×xⁿ + a_n-1×x^n-1 + … + a₁×x + a₀ = (…(a_n×x + a_n-1)×x + … + a₁)×x + a₀ (1.2)

Выражение (1.2) не требует операций возведения в степень. Составим программу для этого алгоритма.

// Программа 1.2

double Polinom_Calculation_Horner(double Array[], unsigned int Order, double Value)

/* Функция расчета по схеме Горнера значения полинома по заданным

коэффициентам, степени полинома и значению переменной x. */

{

double p=Array[Order];

unsigned int index;

/* Array - массив коэффициентов полинома a0, a1, …, an; Order - степень полинома;

Value - значение переменной x, для которого рассчитывается P_n(x);

p и index - вспомогательные переменные. */

for (index=Order; index; index--)

p=p*Value+Array[index-1];

return p;

}//Полином Polinom_Calculation_Horner

Сравнивая первый и второй алгоритмы, можно заметить, что второй требует тоже n сложений и n умножений, но операции возведения в степень в нем отсутствуют. Поэтому по временной сложности второй метод предпочтительнее первого.

Но возникает вопрос, нельзя ли составить программу более быстрого вычисления значения полинома, чем программа 1.2, приведённая выше? Алгоритм Горнера является оптимальным для неветвящихся программ, поэтому ещё сократить время вычислений можно только, учитывая особенности работы компилятора алгоритмического языка программирования. Резерв имеется следующий. Для вычисления значения полинома оба описанных алгоритма в цикле используют элемент Array[index]. То есть программа в каждом шаге цикла отыскивает соответствующий элемент массива полиномиальных коэффициентов. Поиск элемента в массиве достаточно медленная операция, поэтому её желательно заменить более быстрой. В языке C для этого имеются указатели на элементы массива. С их помощью можно составить следующую программу.

double Polinom_Calculation_Fast(double Array[], unsigned int Order, double Value)

/* Функция расчета по схеме Горнера значения полинома по заданным коэффициентам,

степени полинома и значения переменной x. */

{

double p, *ptr;

unsigned int index;

/* Array - массив коэффициентов полинома a₀, a₁, …, a_n; Order - степень полинома;

Value - значение переменной x, для которого рассчитывается P_n(x);

p и index - вспомогательные переменные; *ptr - указатель на элемент массива */

ptr=&Array[Order];

p=*ptr--;

for (index=Order; index; index--){

p*=Value; p+=*ptr--;}

return p;

}//Конец Polinom_Calculation_Fast

Для проверки скорости работы описанных вариантов программы был проведён численный эксперимент. По заданным коэффициентам полинома и величине x были проведены расчеты значений полинома в 1000 точках при различных степенях полиномов. Результаты времени счёта программ на IBM-совместимой ЭВМ с процессором Intel 80286 в миллисекундах показаны в таблице 3. ð