高效的多項結果

我有一個Multinomial類私有：高效的多項結果

unsigned int power; 
double *factors;

我想知道是否有來計算給定參數多項的結果更有效的方式？

我當前的代碼是：

double Multinomial::calculateFor(double x) const{ 
    double sum = this->factors[0]; 
    double prod = 1; 
    for(size_t i = 1; i <= this->power; i++){ 
     prod *= x; 
     if(this->factors[i]){ 
      sum += this->factors[i] * prod; 
     } 
    } 
    return sum; 
}

來源

2014-04-06 Michał

是否分支的成本不是簡單地無條件地計算術語嗎？請參閱[爲什麼處理排序數組的速度比未排序的數組快？]（http://stackoverflow.com/questions/11227809）的一些解釋。您還應該查看[Horner's Method]（http://en.wikipedia.org/wiki/Horner%27s_method）以減少乘法次數。 –

@JonathanLeffler如果我只計算一次多項式，排序仍然有用嗎？ –

你是如何到達術語「多項式」的？它是維特斯（1591年）「多項式」的Stevins（1585年）的前身，但自19世紀初以來，「多項式」的使用僅限於討論超過兩個加權的擴張的條件像（a + b + c + ... + y + z）^ n。 – LutzL

我看到兩種方式來加速計算的。

有條件的分支可能會減慢現代流水線處理器的計算速度，所以可能會避免條件會加快速度。一些解釋請參見Why is processing a sorted array faster than an unsorted array?。使用節省乘法次數。

放在一起，這導致：

double Multinomial::calculateFor(double x) const 
{ 
    double sum = this->factors[this->power]; 
    for (size_t i = this->power; i > 0;) 
     sum = this->factors[--i] + sum * x; 
    return sum; 
}

來源

2014-04-06 17:25:01

高效的多項結果

回答

相關問題