Уровень алгоритма

Схема Горнера, вещественная версия, последовательный вариант: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
(Перенос из Схема_Горнера_последовательная-0.1.1.docx.)
 
 
(не показано 48 промежуточных версий 6 участников)
Строка 1: Строка 1:
−
== Описание свойств и структуры алгоритма ==
+
{{algorithm
 +
| name              = Схема Горнера для деления многочлена n-й степени на приведённый двучлен
 +
| serial_complexity = <math>2n</math>
 +
| pf_height        = <math>11n-16</math>
 +
| pf_width          = <math>O(n^2)</math>
 +
| input_data        = <math>n^2</math>
 +
| output_data      = <math>n^2</math>
 +
}}
 +
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
  
−
=== Словесное описание алгоритма ===
+
== Свойства и структура алгоритма ==
 +
 
 +
=== Общее описание алгоритма ===
  
 
==== Решаемая задача ====
 
==== Решаемая задача ====
  
−
Какую задачу решает схема Горнера? Зачастую в учебной литературе её почему-то сводят к вычислению значения многочлена <math>P_n(x)</math> в точке <math>\alpha</math>. Между тем, в процессе вычислений схема Горнера решает попутно ценную задачу деления этого самого многочлена на двучлен <math>x - \alpha</math>, давая в качестве промежуточных результатов коэффициенты многочлена <math>Q_{n - 1}(x)</math> из соотношения
+
Схема Горнера<ref>Н.Я. Виленкин, Р.С. Гутер, С.И. Шварцбурд, Б.В. Овчинский, В.Г. Ашкинузе. Алгебра. Учебное пособие для 9-10 классов средних школ с математической специализацией. М.: Просвещение, 1972</ref> решает задачу деления многочлена <math>P_n(x)</math> с известными коэффициентами на двучлен <math>x - \alpha</math>. В качестве результатов выступают коэффициенты многочлена <math>Q_{n - 1}(x)</math> из соотношения
 +
 
 +
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>,
 +
 
 +
а также <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>.
  
 
==== Общая схема ====
 
==== Общая схема ====
Строка 13: Строка 27:
 
Фактически схема Горнера реализует «деление уголком» многочлена на двучлен <math>x - \alpha</math>, с нахождением остатка, который, по теореме Безу, равен значению многочлена <math>P_n(x)</math> в точке <math>\alpha</math>.
 
Фактически схема Горнера реализует «деление уголком» многочлена на двучлен <math>x - \alpha</math>, с нахождением остатка, который, по теореме Безу, равен значению многочлена <math>P_n(x)</math> в точке <math>\alpha</math>.
  
−
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
  
 
Исходные данные: одномерный массив <math>n + 1</math> чисел <math>a_k</math> и скаляр <math>\alpha</math>.
 
Исходные данные: одномерный массив <math>n + 1</math> чисел <math>a_k</math> и скаляр <math>\alpha</math>.
Строка 19: Строка 33:
 
Вычисляемые данные: одномерный массив <math>n + 1</math> чисел <math>b_k</math>.
 
Вычисляемые данные: одномерный массив <math>n + 1</math> чисел <math>b_k</math>.
  
−
Формулы метода: из соотношения  
+
Формулы метода с выводом: из соотношения  
  
 
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>
 
:<math>P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)</math>
Строка 25: Строка 39:
 
если записать оба многочлена в каноническом виде
 
если записать оба многочлена в каноническом виде
  
−
:<math>P_n(x) = a_0 x^n+ a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n</math>
+
:<math>
−
:<math>Q_{n - 1}(x) = b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 2} x + b_{n - 1}</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>
  
−
и вдобавок приписать «свободному» <math>b_n</math> значение <math>P_n(\alpha)</math>, то, подставив канонический вид в исходное соотношение и приравняв коэффициенты соответствующих степеней, в качестве решения получаем:
+
и приписать «свободному» <math>b_n</math> значение <math>P_n(\alpha)</math>, то, при подстановке многочленов в каноническом виде в исходное соотношение и приравнивании коэффициентов равных степеней, в качестве решения получается
  
−
:<math>b_0 = a_0</math>
+
:<math>
−
:<math>b_k = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n</math>
+
\begin{align}
 +
b_0 & = a_0, \\
 +
b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n
 +
\end{align}
 +
</math>
  
−
что и является формулами схемы Горнера.  
+
что и является '''формулами схемы Горнера'''.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 43: Строка 65:
 
Как уже записано в описании ядра алгоритма, основную часть вычисления схемы Горнера произведения составляет массовый последовательный набор «двойных› операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
 
Как уже записано в описании ядра алгоритма, основную часть вычисления схемы Горнера произведения составляет массовый последовательный набор «двойных› операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
  
−
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
  
−
Формулы метода описаны выше. Последовательность исполнения — по возрастанию индексов.
+
Формулы метода описаны выше. Последовательность исполнения — по возрастанию индекса ''k''.
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
Строка 53: Строка 75:
 
=== Информационный граф ===
 
=== Информационный граф ===
  
−
Опишем граф алгоритма в виде рисунка. Изображён граф для <math>n = 9</math>. Как видно, граф чисто последовательный.
+
На рис.1 изображён граф алгоритма для <math>n = 9</math>. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "умножить входное данное на скаляр и прибавить к другому данному".
  
−
[[file:linear graph.png|center|thumb|800px]]
+
[[file:Basic sequental algorithm graph.png|center|thumb|800px|Рисунок 1. Схема Горнера: последовательная версия]]
  
−
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
−
Последовательный вариант вычисления схемы Горнера не имеет ресурсов параллелизма. Его ЯПФ — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна <math>n</math> операций умножения плюс <math>n</math> операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по высоте параллельной формы. Ширина параллельной формы равна <math>1</math>, что даёт нам ''постоянную'' сложность по ширине параллельной формы.
+
Последовательный вариант вычисления схемы Горнера не имеет ресурсов параллелизма. Его ярусно-параллельная форма (ЯПФ) — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна <math>n</math> операций умножения плюс <math>n</math> операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по высоте параллельной формы. Ширина параллельной формы равна <math>1</math>, что даёт нам ''постоянную'' сложность по ширине параллельной формы.
  
−
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
  
 
Входные данные: массив <math>a</math> (элементы <math>a_i</math> с номерами от <math>0</math> до <math>n</math>), скаляр <math>\alpha</math>.
 
Входные данные: массив <math>a</math> (элементы <math>a_i</math> с номерами от <math>0</math> до <math>n</math>), скаляр <math>\alpha</math>.
Строка 67: Строка 89:
 
Дополнительные ограничения: отсутствуют.
 
Дополнительные ограничения: отсутствуют.
  
−
Объём входных данных: <nowiki/><math>n + 2 \frac{n (n -1)}{2}</math>.
+
Объём входных данных: <nowiki/><math>n + 2</math>.
  
 
Выходные данные: массив <math>b</math> (элементы <math>b_k</math> с номерами от <math>0</math> до <math>n</math>).
 
Выходные данные: массив <math>b</math> (элементы <math>b_k</math> с номерами от <math>0</math> до <math>n</math>).
Строка 75: Строка 97:
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
  
−
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''константой'' (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных почти столько же, сколько операций; если точнее — даже больше в 2 раза)''. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны.
+
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''константой'' (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных даже на 1 больше, чем количество операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. По устойчивости схема Горнера оптимальна для вычисления значения многочлена с известными коэффициентами.
  
−
== Программная реализация ==
+
== Программная реализация алгоритма ==
  
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
  
−
На Фортране можно записать так:
+
На Фортране схему Горнера можно записать так:
 
<source lang="fortran">
 
<source lang="fortran">
 
b(0) = a(0)
 
b(0) = a(0)
Строка 89: Строка 111:
 
</source>
 
</source>
  
−
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
−
==== Описание локальности алгоритма ====
+
 
−
==== Описание локальности реализации алгоритма ====
+
Описываемый алгоритм не предполагает параллельной реализации.
−
===== Описание структуры обращений в память и качественная оценка локальности =====
+
 
−
===== Количественная оценка локальности =====
+
Помимо [[#Особенности реализации последовательного алгоритма|выписанной выше простейшей реализации]], существуют более примитивные коды, реализующие часть функционала схемы Горнера. Это объясняется тем, что для многих нужно только значение многочлена (остаток от деления), но не нужен многочлен-частное. В таком случае вместо всех элементов массива <math>b</math> используется один и тот же скаляр.
−
===== Анализ на основе теста Apex-Map =====
+
 
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
−
=== Масштабируемость алгоритма и его реализации ===
 
−
==== Описание масштабируемости алгоритма ====
 
−
==== Описание масштабируемости реализации алгоритма ====
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
−
=== Существующие реализации алгоритма ===
 
  
−
Помимо [[#Особенности реализации последовательного алгоритма|выписанной выше простейшей реализации]], существуют более примитивные коды, реализующие часть функционала схемы Горнера. Это объясняется тем, что для многих нужно только значение многочлена (остаток от деления), но не нужен многочлен-частное. В таком случае вместо всех элементов массива <math>b</math> используется один и тот же скаляр.
+
Схема Горнера - метод для архитектуры классического, фон-неймановского типа. Даже на современных суперскалярных одноядерных системах эффективность её исполнения очень низка.
 +
 
 +
== Литература ==
 +
 
 +
<references />
 +
 
 +
[[en: Horners method]]
 +
 
 +
[[Категория:Законченные статьи]]
 +
[[Категория:Алгоритмы с низким уровнем параллелизма]]

Текущая версия на 10:14, 8 июля 2022


Схема Горнера для деления многочлена n-й степени на приведённый двучлен
Последовательный алгоритм
Последовательная сложность [math]2n[/math]
Объём входных данных [math]n^2[/math]
Объём выходных данных [math]n^2[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]11n-16[/math]
Ширина ярусно-параллельной формы [math]O(n^2)[/math]

Основные авторы описания: А.В.Фролов.

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

1.1.1 Решаемая задача

Схема Горнера[1] решает задачу деления многочлена [math]P_n(x)[/math] с известными коэффициентами на двучлен [math]x - \alpha[/math]. В качестве результатов выступают коэффициенты многочлена [math]Q_{n - 1}(x)[/math] из соотношения

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

а также [math]P_n(\alpha)[/math] (значение многочлена [math]P_n(x)[/math] в точке [math]\alpha[/math])

К сожалению, зачастую в учебной литературе схему Горнера сводят к вычислению значения многочлена [math]P_n(x)[/math] в точке [math]\alpha[/math].

1.1.2 Общая схема

Фактически схема Горнера реализует «деление уголком» многочлена на двучлен [math]x - \alpha[/math], с нахождением остатка, который, по теореме Безу, равен значению многочлена [math]P_n(x)[/math] в точке [math]\alpha[/math].

1.2 Математическое описание алгоритма

Исходные данные: одномерный массив [math]n + 1[/math] чисел [math]a_k[/math] и скаляр [math]\alpha[/math].

Вычисляемые данные: одномерный массив [math]n + 1[/math] чисел [math]b_k[/math].

Формулы метода с выводом: из соотношения

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

если записать оба многочлена в каноническом виде

[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]

и приписать «свободному» [math]b_n[/math] значение [math]P_n(\alpha)[/math], то, при подстановке многочленов в каноническом виде в исходное соотношение и приравнивании коэффициентов равных степеней, в качестве решения получается

[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 Вычислительное ядро алгоритма

Вычислительное ядро схемы Горнера в последовательном варианте можно представить в качестве последовательного набора [math]n[/math] «двойных» операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).

1.4 Макроструктура алгоритма

Как уже записано в описании ядра алгоритма, основную часть вычисления схемы Горнера произведения составляет массовый последовательный набор «двойных› операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).

1.5 Схема реализации последовательного алгоритма

Формулы метода описаны выше. Последовательность исполнения — по возрастанию индекса k.

1.6 Последовательная сложность алгоритма

Для вычисления схемы Горнера для многочлена степени [math]n[/math], количество операций умножения равно количеству операций сложения и равно [math]n[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

1.7 Информационный граф

На рис.1 изображён граф алгоритма для [math]n = 9[/math]. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "умножить входное данное на скаляр и прибавить к другому данному".

Рисунок 1. Схема Горнера: последовательная версия

1.8 Ресурс параллелизма алгоритма

Последовательный вариант вычисления схемы Горнера не имеет ресурсов параллелизма. Его ярусно-параллельная форма (ЯПФ) — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна [math]n[/math] операций умножения плюс [math]n[/math] операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности по высоте параллельной формы. Ширина параллельной формы равна [math]1[/math], что даёт нам постоянную сложность по ширине параллельной формы.

1.9 Входные и выходные данные алгоритма

Входные данные: массив [math]a[/math] (элементы [math]a_i[/math] с номерами от [math]0[/math] до [math]n[/math]), скаляр [math]\alpha[/math].

Дополнительные ограничения: отсутствуют.

Объём входных данных: [math]n + 2[/math].

Выходные данные: массив [math]b[/math] (элементы [math]b_k[/math] с номерами от [math]0[/math] до [math]n[/math]).

Объём выходных данных: [math]n + 1[/math].

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является константой (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных даже на 1 больше, чем количество операций). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. По устойчивости схема Горнера оптимальна для вычисления значения многочлена с известными коэффициентами.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

На Фортране схему Горнера можно записать так: 

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

2.2 Возможные способы и особенности параллельной реализации алгоритма

Описываемый алгоритм не предполагает параллельной реализации.

Помимо выписанной выше простейшей реализации, существуют более примитивные коды, реализующие часть функционала схемы Горнера. Это объясняется тем, что для многих нужно только значение многочлена (остаток от деления), но не нужен многочлен-частное. В таком случае вместо всех элементов массива [math]b[/math] используется один и тот же скаляр.

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

Схема Горнера - метод для архитектуры классического, фон-неймановского типа. Даже на современных суперскалярных одноядерных системах эффективность её исполнения очень низка.

3 Литература

  1. ↑ Н.Я. Виленкин, Р.С. Гутер, С.И. Шварцбурд, Б.В. Овчинский, В.Г. Ашкинузе. Алгебра. Учебное пособие для 9-10 классов средних школ с математической специализацией. М.: Просвещение, 1972
Источник — https://algowiki-project.org/w/ru/index.php?title=Схема_Горнера,_вещественная_версия,_последовательный_вариант&oldid=29058