Наиболее эффективный способ вычислить многочлен

Question

полиномиальной: a0x^0 + a1x^1 + a2x^2 + A3x^3 + ... + апх^п

Массив: array_a [] = {a0, a1, a2, a3 ... an};

Я написал функцию для вычисления этого многочлена в Java:

public double cal(double x) { 
    double y = 0.0; 
    for (int index = array_a.length - 1; index >= 0; index--) { 
     y = array_a[index] + y * x; 
    } 
    return y; 
} 

Это кажется чем петля y += array_a[index] * Math.Pow(x, index);

Но я интересно, если есть лучший способ, чтобы вычислить этот полином 5 раз быстрее?

** Для кого-то думает, что это другой расчет: я проверил функцию выше. Он делает то же самое с y += array_a[index] * Math.Pow(x, index);, и они вычисляют тот же результат.

Спасибо.

Answer 1

Это Метод Хорнера. Если вы хотите, чтобы вычислить его один раз в полином, this is the most efficient algorithm:

... метод Хорнера требует только п дополнения и п умножений, а его требование к хранению только п раз число бит x. ...

Метод Хорнера оптимален в том смысле, что любой алгоритм для оценки произвольного многочлена должен использовать по крайней мере столько же операций. В 1954 году Александр Островский доказал, что количество необходимых дополнений минимально. В 1966 году Виктор Пан доказал, что количество умножений минимально.

Если вам нужно оценить полином очень много раз, и степень очень высока, то есть методы, чтобы трансформировать представление полинома (предобусловливания), так что число умножения сводится к & lfloor; n/2 & rfloor; + 2. Это кажется не очень практичным, хотя, по крайней мере, я никогда не видел этого в дикой природе. I've found an online paper that describes some of the algorithms if you are interested.

также упоминается в документе, из-за архитектуры процессора может быть более эффективным, если вы оценки даже и нечетные термины по отдельности, так что они могут быть размещены в параллельных трубопроводов:

public double cal(double x) { 
    double x2 = x * x; 
    double y_odd = 0.0, y_even = 0.0; 
    int index = array_a.length - 1; 
    if (index % 2 == 0) { 
     y_even = array_a[index]; 
     index -= 1; 
    } 
    for (; index >= 0; index -= 2) { 
     y_odd = array_a[index] + y_odd * x2; 
     y_even = array_a[index-1] + y_even * x2; 
    } 
    return y_even + y_odd * x; 
} 

JIT-/ компилятор может быть в состоянии сделать это преобразование для вас или даже использовать SIMD, чтобы сделать его очень быстрым автоматически. Во всяком случае, для такой микро-оптимизации всегда нужен профиль, прежде чем перейти к окончательному решению.