1 июля 2012 г.

Оптимизация вычисления некоторых функций: полиномиальная функция

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



Вычисление значения напрямую требует i сложений и i*(i+1)/2 умножений. Реализация такого вычислительного процесса в системах реального времени может оказаться непомерно затратной.
Для оптимизации этого процесса используют алгоритм Горнера, суть которого в представлении исходного выражения в виде:



Вычисление данного выражения требует i умножений и i сложений. Кроме сокращения вычислительной сложности, данный подход требует для реализации меньшее число регистров сумматора, что важно при реализации в встраиваемых системах.

Конечно же имплементация тривиальна. Приведем ее только для справки на Javascript и Erlang.

// We define our own power function for purity of experiment
// Prototype give us "sugar": (2).power(8) => 256
Number.prototype.power = function (q) {
  var result = 1;
  for (var i = 0; i < q; i++)
    result *= this;
  return result;
}

// straightforward implementation
function naive (a, x) {
 var result = 0;
 for (var i = 0; i < a.length; i++)
   result = result + a[i] * x.power(i);
 return result;
}

// recursive implementation of Gorner
function gorner_recursive (a, x, i) { 
 if (i > a.length - 1) return 0;
 i = i || 0;
 return a[i] + x * gorner_recursive(a, x, i+1);
}

// loop implementation from recursive
function gorner_normal (a,x) {
  var b = a[a.length - 1];

  for (var i = a.length - 2; i >= 0; i--) {
    b = a[i] + x * b;    
  }
  return b;
}

// recursive in Erlang
gorner_recursive([H|T], X)->
    H + X*gorner_recursive(T,X);
gorner_recursive([],X)->
    0. 


В следующем посте расскажу про разные подходы в оптимизации тригонометрических функций.
Отправить комментарий