performance - 高速乗算

Question

次の系列を計算するときは、次の1+x+x^2+x^3+...ようにします。(1+x)(1+x^2)(1+x^4)...これは、乗算の数を大幅に減らすことができるように、（ある種の繰り返しの2乗のようなものです）。

系列を計算したいのですが1+x/1!+(x^2)/2!+(x^3)/3!+...、同様の手法を使用して乗算の数を改善するにはどうすればよいですか？

どんな提案でも大歓迎です！

Answer 1

あなたが参照する最適化の方法は、おそらくホーナー法です：

a + bx +cx^2 +dx^3 = ((c+dx)x + b)x + a

交項級数A*（1-x）（1 + x ^ 2）（1-x ^ 4）（1 + x ^ 8）... OTOHは、A /（1 + x）の除算の近似を計算するのに役立ちます。 、ここでxは小さいです。

sigma x^n/n!exp（x）のテイラー級数はかなりひどく収束します。正確な値を取得するには、他の近似が適しています。より少ない乗算でそれを作るためのトリックがある場合、それは一時的な値で反復することです：

  sum=1; temp=x; k=1; 
  // The sum after first iteration is (1+x) or 1+x^1/1!
  for (i=1;i<=N;i++) { sum=sum+temp; k=k*(i+1); temp = temp * x / k; }
  // or
  prod=1.0; for (i=N;i>0;i--) prod = prod * x/(double)i + 1.0;

階乗を乗算すると、精度が少し向上するはずです。実際の状況ではtemp=temp*x/(i+1)、さらに反復できるように組み合わせるか、定数a_n / n！のルックアップテーブルを使用することをお勧めします。いくつかの用語。（sin / cosの場合は4または5項）。

結局のところ、ホーナーの法則は、等比数列を製品の形に変換する上であまり役割を果たしていませんでした。Sigma x^n指数を計算するには、他の強力な手法を適用する必要があります。通常、範囲の縮小と有理（Pade）、多項式（chebyshev）の近似などです。

Answer 2

コメントを回答に変換する：

最初のシリーズには、正確な同等性があることに注意してください。

1+x+x^2+x^3+...+x^n = (1-x^(n+1))/(1-x)

これを使用すると、はるかに高速に計算できます。

2つ目は、の収束級数です。e^x標準の数学ライブラリ関数を使用するpow(e, x)か、exp(x)代わりに使用することをお勧めします。

Answer 3

最初のシリーズのアプローチでは、1 + x（1+ x（1+ x（1 + x）....））を使用する方が良いアプローチだと思いませんか。同様のアプローチは、2番目のシリーズにも適用できます。したがって、1 + x / 1 （1+ x / 2（1 + x / 3 *（1 + x / 4（.....））））