Вычисление значения полинома

Рассмотрим программу для расчета значения полинома в общем виде:
y = a_nxⁿ + a_n-1x^n-1 + ... + a₁x¹ + a₀

Решение "в лоб" даст нам:

y = a[0]
xi = 1
for i = 1 to n
  xi = x * xi
  y = y + a[i] * xi

Код делает 2*n умножений(n - размерность полинома). Многовато, с учетом того, что умножение не самая элементарная операция. К счастью существует более быстрая программа.

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

y = a[n]
for i = n-1 downto 0
  y = x * y + a[i]

В программе используется n умножений и она обычно работает вдвое быстрее.

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

 Расчет значения полинома в общем виде, самое простое решение "в лоб" ссылка |режим:

static float PolinomSlow(float[] a, float x)
{
    float y = a[0];
    float xi = 1;
    for (int i = 1; i <= a.Length-1; i++)
    {
        xi = x * xi;
        y = y + a[i] * xi;
    }
    return y;
}

static float PolinomSlow(float[] a, float x) { float y = a[0]; float xi = 1; for (int i = 1; i <= a.Length-1; i++) { xi = x * xi; y = y + a[i] * xi; } return y; }

Расчет значения полинома в общем виде, самое простое решение "в лоб".

В результате выполнения производится 2*n умножений.
Вариант по схеме Горнера делает n умножений, т.е. в 2 раза меньше.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

 

 Быстрый расчет значения полинома по схеме Горнера ссылка |режим:

static float PolinomGorner(float[] a, float x)
{
    int n = a.Length - 1;
    float y = a[n];
    for (int i = n - 1; i >= 0; i--)
    {
        y = x*y + a[i];
    }
    return y;
}

static float PolinomGorner(float[] a, float x) { int n = a.Length - 1; float y = a[n]; for (int i = n - 1; i >= 0; i--) { y = x*y + a[i]; } return y; }

Быстрый расчет значения полинома по схеме Горнера

В результате выполнения производится всего n умножений.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0