Algorithm level

Difference between revisions of "Horners method"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][checked revision]
(Created page with "Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (#Описание л...")
 
 
(28 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]])
+
{{algorithm
 +
| name              = Horners method
 +
| serial_complexity = <math>2 n^3</math>
 +
| input_data        = <math>n^2</math>
 +
| output_data      = <math>n^2</math>
 +
| pf_height        = <math>11n-16</math>
 +
| pf_width          = <math>O(n^2)</math>
 +
}}
  
−
== Описание свойств и структуры алгоритма ==
+
Main authors: [[:ru:Участник:Frolov|Alexey Frolov]].
  
−
=== Словесное описание алгоритма ===
+
== Properties and structure of the algorithm ==
  
−
==== Решаемая задача ====
+
=== General description of the algorithm ===
  
−
Схема Горнера решает задачу деления многочлена <math>P_n(x)</math> с известными коэффициентами на двучлен <math>x - \alpha</math>. В качестве результатов выступают коэффициенты многочлена <math>Q_{n - 1}(x)</math> из соотношения
+
==== Formulation of the problem ====
  
−
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>,
+
Horner’s scheme is devoted to the division of a polynomial <math>P_n(x)</math> with known coefficients by the binomial <math>x - \alpha</math>. The results of this operation are the coefficients of the polynomial <math>Q_{n - 1}(x)</math> obtained by the relation
  
−
а также <math>P_n(\alpha)</math> (значение многочлена <math>P_n(x)</math> в точке <math>\alpha</math>)
+
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>  
  
−
К сожалению, зачастую в учебной литературе схему Горнера сводят к вычислению значения многочлена <math>P_n(x)</math> в точке <math>\alpha</math>.
+
and the value <math>P_n(\alpha)</math> of the polynomial <math>P_n(x)</math> at a given  point <math>\alpha</math>.
  
−
==== Общая схема ====
+
Unfortunately, Horner’s method is often reduced only to the calculation of a polynomial <math>P_n(x)</math> at the point <math>\alpha</math>.
  
−
Фактически схема Горнера реализует «деление уголком» многочлена на двучлен <math>x - \alpha</math>, с нахождением остатка, который, по теореме Безу, равен значению многочлена <math>P_n(x)</math> в точке <math>\alpha</math>.
+
==== General scheme ====
  
−
=== Математическое описание ===
+
Actually, Horner’s scheme implements the long division of a polynomial by the binomial <math>x - \alpha</math>. By the Bezout theorem, the remainder of this operation is equal to the value of a polynomial <math>P_n(x)</math> at a point <math>\alpha</math>.
  
−
Исходные данные: одномерный массив <math>n + 1</math> чисел <math>a_k</math> и скаляр <math>\alpha</math>.
+
=== Mathematical description of the algorithm ===
  
−
Вычисляемые данные: одномерный массив <math>n + 1</math> чисел <math>b_k</math>.
+
Input data: a one-dimensional array consisting of <math>n + 1</math> numbers <math>a_k</math> and a scalar <math>\alpha</math>.
  
−
Формулы метода с выводом: из соотношения
+
Output data: a one-dimensional array consisting of <math>n + 1</math> numbers <math>b_k</math>.
  
−
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>
+
The formulas of Horner's method are based on the relation
  
−
если записать оба многочлена в каноническом виде
+
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>.
 +
 
 +
Now we represent the above polynomials in canonical form:
  
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
 
P_n(x)      & = a_0 x^n+ a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n, \\
 
P_n(x)      & = a_0 x^n+ a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n, \\
−
Q_{n - 1}(x) & = b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 2} x + b_{n - 1}
+
Q_{n - 1}(x) & = b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 2} x + b_{n - 1}.
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
и приписать «свободному» <math>b_n</math> значение <math>P_n(\alpha)</math>, то, при подстановке многочленов в каноническом виде в исходное соотношение и приравнивании коэффициентов равных степеней, в качестве решения получается
+
By <math>b_n</math> we denote <math>P_n(\alpha)</math>. Substituting these polynomials in their canonical form into the above relation and equating the coefficients at equal powers of <math>x</math>, we come to the following formulas of Horner’s scheme:
  
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
 
b_0 & = a_0, \\
 
b_0 & = a_0, \\
−
b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n
+
b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n.
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
что и является '''формулами схемы Горнера'''.
+
=== Computational kernel of the algorithm ===
  
−
=== Вычислительное ядро алгоритма ===
+
The computational kernel of Horner’s algorithm in its serial version can be represented as a sequential set of <math>n</math> «double» operations: the multiplication of elements of the output array by one and the same scalar and the addition of the result to the next element of the input array.
  
−
Вычислительное ядро схемы Горнера в последовательном варианте можно представить в качестве последовательного набора <math>n</math> «двойных» операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
+
=== Macro structure of the algorithm ===
  
−
=== Макроструктура алгоритма ===
+
From the computational kernel of Horner’s algorithm it follows that its major part consists of the sequential set of the above «double» operations.
  
−
Как уже записано в описании ядра алгоритма, основную часть вычисления схемы Горнера произведения составляет массовый последовательный набор «двойных› операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
+
=== Implementation scheme of the serial algorithm ===
  
−
=== Описание схемы реализации последовательного алгоритма ===
+
The formulas of the algorithm are described above. The operations are performed in increasing order of <math>k</math>.
  
−
Формулы метода описаны выше. Последовательность исполнения — по возрастанию индекса ''k''.
+
=== Serial complexity of the algorithm ===
  
−
=== Последовательная сложность алгоритма ===
+
For a polynomial of degree <math>n</math>, the number of multiplications is equal to <math>n</math> and the number of additions is also equal to <math>n</math>. Hence, Horner’s algorithm is of linear complexity with respect to the number of serial operations.
  
−
Для вычисления схемы Горнера для многочлена степени <math>n</math>, количество операций умножения равно количеству операций сложения и равно <math>n</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по количеству последовательных операций.
+
=== Information graph ===
  
−
=== Информационный граф ===
+
The graph of the algorithm is illustrated in Fig.1 for <math>n = 9</math>. As can be seen, the graph is serial.
  
−
Опишем граф алгоритма в виде рисунка. Изображён граф для <math>n = 9</math>. Как видно, граф чисто последовательный.
+
[[file:Basic_sequental_algorithm_graph.png|center|thumb|800px|Figure 1. Horner’s scheme: a serial version.]]
  
−
[[file:Basic sequental algorithm graph.png|center|thumb|800px|Схема Горнера - последовательный вариант. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "умножить входное данное на скаляр и прибавить к другому данному".]]
+
Here the abbreviations In (Input) and Out (Output) are used to denote the first coefficient of the input array and the value of the polynomial at a given point <math>\alpha</math>, respectively. By Op we denote the "double" operation: the multiplication of an input variable by a scalar and the addition of the result to another variable.
  
−
=== Описание ресурса параллелизма алгоритма ===
+
=== Parallelization resource of the algorithm ===
  
−
Последовательный вариант вычисления схемы Горнера не имеет ресурсов параллелизма. Его ярусно-параллельная форма (ЯПФ) — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна <math>n</math> операций умножения плюс <math>n</math> операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по высоте параллельной формы. Ширина параллельной формы равна <math>1</math>, что даёт нам ''постоянную'' сложность по ширине параллельной формы.
+
The serial version of Horner’s algorithm has no parallelization resource. Its parallel form consists of a single layer and is coincident with the serial algorithm. Thus, the height of the parallel form is equal to <math>n</math> multiplications plus <math>n</math> additions. Hence, this algorithm is of linear complexity with respect to the height of the parallel form. The width of the parallel form is equal to <math>1</math>; hence, this algorithm is of constant complexity with respect to the width of the parallel form.
  
−
=== Описание входных и выходных данных ===
+
=== Input and output data of the algorithm ===
  
−
Входные данные: массив <math>a</math> (элементы <math>a_i</math> с номерами от <math>0</math> до <math>n</math>), скаляр <math>\alpha</math>.
+
Input data: an array <math>a</math> (its elements are denoted by <math>a_i</math>, where <math>i = 0, \dots, n</math>) and a scalar <math>\alpha</math>.
  
−
Дополнительные ограничения: отсутствуют.
+
Additional constraints: absent.
  
−
Объём входных данных: <nowiki/><math>n + 2</math>.
+
Amount of input data: <nowiki/><math>n + 2</math>.
  
−
Выходные данные: массив <math>b</math> (элементы <math>b_k</math> с номерами от <math>0</math> до <math>n</math>).
+
Output data: an array <math>b</math> (its elements are denoted by <math>b_k</math>, where <math>k = 0, \dots, n</math>)
  
−
Объём выходных данных: <nowiki/><math>n + 1</math>.
+
Amount of output data: <nowiki/><math>n + 1</math>.
  
−
=== Свойства алгоритма ===
+
=== Properties of the algorithm ===
  
−
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''константой'' (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных даже на 1 больше, чем количество операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. По устойчивости схема Горнера оптимальна для вычисления значения многочлена с известными коэффициентами.
+
In the case of unlimited computer resources, the ratio of the serial complexity to the parallel complexity is ''constant'' (1). Computational power of the algorithm considered as the ratio of the number of operations to the total amount of input and output data is equal to 1 (the number of input and output data is even larger by 1 than the number of operations). The algorithm is completely deterministic. The arcs of the information graph are local. The stability of Horner’s scheme is optimal for the calculation of the values of a polynomial with known coefficient.
  
−
== Программная реализация ==
+
== Software implementation of the algorithm ==
  
−
=== Особенности реализации последовательного алгоритма ===
+
=== Implementation peculiarities of the serial algorithm ===
  
−
На Фортране схему Горнера можно записать так:
+
Horner’s scheme can be represented in Fortran as
 
<source lang="fortran">
 
<source lang="fortran">
 
b(0) = a(0)
 
b(0) = a(0)
Line 103: Line 112:
 
</source>
 
</source>
  
−
=== Описание локальности данных и вычислений ===
+
=== Possible methods and considerations for parallel implementation of the algorithm  ===
−
==== Описание локальности реализации алгоритма ====
 
−
===== Описание структуры обращений в память и качественная оценка локальности =====
 
−
 
 
−
[[file:Gorner_1.png|thumb|center|500px|Рисунок 12.1. Реализация схемы Горнера. Общий профиль обращений в память]]
 
−
 
 
−
На рис. 12.1 представлен профиль обращений в память последовательной вещественной реализации схемы Горнера. Исходя из рисунка 12.1, данный профиль устроен очень просто и состоит из двух последовательных переборов элементов, выполняемых параллельно для двух массивов.
 
−
 
 
−
Однако даже в таком простом примере для полного понимания структуры обращений в память нужен более детальный анализ на уровне отдельных обращений. На рис. 12.2 рассмотрим подробнее фрагмент 1, выделенный на рис. 12.1 зеленым. Можно увидеть, что верхний последовательный перебор несколько отличается от нижнего – в первом случае к каждому элементу выполняется по два обращения подряд. Отметим, однако, что данное уточнение строения профиля слабо сказывается на локальности всего профиля.
 
−
 
 
−
В целом, общий профиль обладает высокой пространственной локальностью, поскольку перебор элементов массивов осуществляется последовательно, однако очень низкой временно́й локальностью – в одном из массивов к каждому элементу выполняется обращение только дважды, во втором массиве повторные обращения вообще отсутствуют.
 
−
 
 
−
[[file:Gorner_2.jpg|thumb|center|500px|Рисунок 12.2. Фрагмент 1 (первые 100 обращений общего профиля)]]
 
−
 
 
−
===== Количественная оценка локальности =====
 
−
 
 
−
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/vectors/vectors.h здесь] (функция KernelGorner). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
 
−
 
 
−
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
 
−
 
 
−
На рисунке 12.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Согласно данному рисунку, реализация схемы Горнера показывает низкую производительность работы с памятью. Может показаться странным, что значение daps в этом случае значительно меньше, чем для тестов STREAM, несмотря на то, что профиль обращений во всех случаях очень похож – несколько одновременно выполняемых последовательных переборов массивов.
 
−
 
 
−
Причина такого поведения связана с особенностями строения подсистемы памяти. В реализации схемы Горнера, как было отмечено выше, к элементам одного из массивов выполняется по два обращения подряд. Однако если посмотреть исходный код реализации, можно увидеть, что на самом деле второе обращение выполняется на следующей итерации – это обращение к предыдущему элементу:
 
−
<source lang="c">
 
−
for (int i = 1; i < size; i++) {
 
−
    c[i] = a[i] + c[i - 1] * x;
 
−
}
 
−
</source>
 
−
В результате из-за зависимости итераций аппаратный префетчер гораздо хуже справляется с подтягиванием требуемых кэш-строк, что приводит к заметному замедлению выполнения программы по сравнению с другими реализациями, основанными на последовательном переборе (например, тесты STREAM).
 
−
 
 
−
Подобный пример лишний раз показывает, насколько сложно утроена подсистема памяти – совсем небольшое изменение строения тела цикла приводит к достаточно неожиданному серьезному замедлению программы.
 
−
 
 
−
[[file:Gorner_daps_ru.png|thumb|center|700px|Рисунок 12.3. Сравнение значений оценки daps]]
 
−
 
 
−
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
 
−
 
 
−
На рисунке 12.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что реализация схема Горнера обладает очень высокой локальностью согласно оценке cvg.
 
−
 
 
−
[[file:Gorner_cvg.png|thumb|center|700px|Рисунок 12.4. Сравнение значений оценки cvg]]
 
−
 
 
−
Как мы видели ранее, это плохо соотносится с реальной производительностью работы с памятью из-за особенностей строения памяти. Однако здесь необходимо сделать два замечания. Во-первых, подобные случаи, когда производительность работы с памятью настолько сильно зависит от специфичных аппаратных особенностей строения подсистемы памяти, на практике встречаются не так часто. Во-вторых, cvg предназначена для получения машинно-независимой оценки локальности; на данном уровне учесть подобные аппаратные особенности, по крайней мере, без потери доли машинно-независимых свойств, вряд ли представляется возможным.
 
−
 
 
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
  
−
Описываемый алгоритм не предполагает параллельной реализации.
+
This algorithm is not designed to be implemented in parallel.
  
−
=== Масштабируемость алгоритма и его реализации ===
+
In addition to [[#Implementation peculiarities of the serial algorithm|the above simplest implementation]], there exist more primitive codes implementing only a part of Horner’s scheme. This can be explained by the fact that in many cases it is necessary to know the value of a polynomial (the remainder of division), but it is not necessary to know only the quotient polynomial with the remainder dropped. In such cases one and the same scalar should be used instead of all the elements of the array <math>b</math>.
  
−
Понятие масштабируемости неприменимо, поскольку описываемый алгоритм не предполагает параллельной реализации.
+
=== Run results ===
 +
=== Conclusions for different classes of computer architecture ===
  
−
=== Динамические характеристики и эффективность реализации алгоритма ===
+
== References ==
−
=== Выводы для классов архитектур ===
 
−
=== Существующие реализации алгоритма ===
 
  
−
Помимо [[#Особенности реализации последовательного алгоритма|выписанной выше простейшей реализации]], существуют более примитивные коды, реализующие часть функционала схемы Горнера. Это объясняется тем, что для многих нужно только значение многочлена (остаток от деления), но не нужен многочлен-частное. В таком случае вместо всех элементов массива <math>b</math> используется один и тот же скаляр.
+
<references />
  
 
[[ru: Схема Горнера, вещественная версия, последовательный вариант]]
 
[[ru: Схема Горнера, вещественная версия, последовательный вариант]]
  
−
[[Категория:Статьи в работе]]
+
[[Category:Finished articles]]

Latest revision as of 10:15, 8 July 2022


Horners method
Sequential algorithm
Serial complexity [math]2 n^3[/math]
Input data [math]n^2[/math]
Output data [math]n^2[/math]
Parallel algorithm
Parallel form height [math]11n-16[/math]
Parallel form width [math]O(n^2)[/math]


Main authors: Alexey Frolov.

1 Properties and structure of the algorithm

1.1 General description of the algorithm

1.1.1 Formulation of the problem

Horner’s scheme is devoted to the division of a polynomial [math]P_n(x)[/math] with known coefficients by the binomial [math]x - \alpha[/math]. The results of this operation are the coefficients of the polynomial [math]Q_{n - 1}(x)[/math] obtained by the relation

[math]P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)[/math]

and the value [math]P_n(\alpha)[/math] of the polynomial [math]P_n(x)[/math] at a given point [math]\alpha[/math].

Unfortunately, Horner’s method is often reduced only to the calculation of a polynomial [math]P_n(x)[/math] at the point [math]\alpha[/math].

1.1.2 General scheme

Actually, Horner’s scheme implements the long division of a polynomial by the binomial [math]x - \alpha[/math]. By the Bezout theorem, the remainder of this operation is equal to the value of a polynomial [math]P_n(x)[/math] at a point [math]\alpha[/math].

1.2 Mathematical description of the algorithm

Input data: a one-dimensional array consisting of [math]n + 1[/math] numbers [math]a_k[/math] and a scalar [math]\alpha[/math].

Output data: a one-dimensional array consisting of [math]n + 1[/math] numbers [math]b_k[/math].

The formulas of Horner's method are based on the relation

[math]P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)[/math].

Now we represent the above polynomials in canonical form:

[math] \begin{align} P_n(x) & = a_0 x^n+ a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n, \\ Q_{n - 1}(x) & = b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 2} x + b_{n - 1}. \end{align} [/math]

By [math]b_n[/math] we denote [math]P_n(\alpha)[/math]. Substituting these polynomials in their canonical form into the above relation and equating the coefficients at equal powers of [math]x[/math], we come to the following formulas of Horner’s scheme:

[math] \begin{align} b_0 & = a_0, \\ b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n. \end{align} [/math]

1.3 Computational kernel of the algorithm

The computational kernel of Horner’s algorithm in its serial version can be represented as a sequential set of [math]n[/math] «double» operations: the multiplication of elements of the output array by one and the same scalar and the addition of the result to the next element of the input array.

1.4 Macro structure of the algorithm

From the computational kernel of Horner’s algorithm it follows that its major part consists of the sequential set of the above «double» operations.

1.5 Implementation scheme of the serial algorithm

The formulas of the algorithm are described above. The operations are performed in increasing order of [math]k[/math].

1.6 Serial complexity of the algorithm

For a polynomial of degree [math]n[/math], the number of multiplications is equal to [math]n[/math] and the number of additions is also equal to [math]n[/math]. Hence, Horner’s algorithm is of linear complexity with respect to the number of serial operations.

1.7 Information graph

The graph of the algorithm is illustrated in Fig.1 for [math]n = 9[/math]. As can be seen, the graph is serial.

Figure 1. Horner’s scheme: a serial version.

Here the abbreviations In (Input) and Out (Output) are used to denote the first coefficient of the input array and the value of the polynomial at a given point [math]\alpha[/math], respectively. By Op we denote the "double" operation: the multiplication of an input variable by a scalar and the addition of the result to another variable.

1.8 Parallelization resource of the algorithm

The serial version of Horner’s algorithm has no parallelization resource. Its parallel form consists of a single layer and is coincident with the serial algorithm. Thus, the height of the parallel form is equal to [math]n[/math] multiplications plus [math]n[/math] additions. Hence, this algorithm is of linear complexity with respect to the height of the parallel form. The width of the parallel form is equal to [math]1[/math]; hence, this algorithm is of constant complexity with respect to the width of the parallel form.

1.9 Input and output data of the algorithm

Input data: an array [math]a[/math] (its elements are denoted by [math]a_i[/math], where [math]i = 0, \dots, n[/math]) and a scalar [math]\alpha[/math].

Additional constraints: absent.

Amount of input data: [math]n + 2[/math].

Output data: an array [math]b[/math] (its elements are denoted by [math]b_k[/math], where [math]k = 0, \dots, n[/math])

Amount of output data: [math]n + 1[/math].

1.10 Properties of the algorithm

In the case of unlimited computer resources, the ratio of the serial complexity to the parallel complexity is constant (1). Computational power of the algorithm considered as the ratio of the number of operations to the total amount of input and output data is equal to 1 (the number of input and output data is even larger by 1 than the number of operations). The algorithm is completely deterministic. The arcs of the information graph are local. The stability of Horner’s scheme is optimal for the calculation of the values of a polynomial with known coefficient.

2 Software implementation of the algorithm

2.1 Implementation peculiarities of the serial algorithm

Horner’s scheme can be represented in Fortran as 

	b(0) = a(0)
	DO I = 1, N
		b(I) = a(I)+b(I-1)*alpha
	END DO

2.2 Possible methods and considerations for parallel implementation of the algorithm

This algorithm is not designed to be implemented in parallel.

In addition to the above simplest implementation, there exist more primitive codes implementing only a part of Horner’s scheme. This can be explained by the fact that in many cases it is necessary to know the value of a polynomial (the remainder of division), but it is not necessary to know only the quotient polynomial with the remainder dropped. In such cases one and the same scalar should be used instead of all the elements of the array [math]b[/math].

2.3 Run results

2.4 Conclusions for different classes of computer architecture

3 References

Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Horners_method&oldid=10354"