指数はどのように計算されますか?

StackOverflow https://stackoverflow.com/questions/164964

  •  03-07-2019
  •  | 
  •  

質問

指数を使用するアルゴリズムの 1 つについて、漸近的な実行時間を決定しようとしていますが、指数がプログラムでどのように計算されるかがわかりません。

私は特に倍精度浮動小数点数に使用される pow() アルゴリズムを探しています。

役に立ちましたか？

解決

fdlibm の実装を見る機会がありました。コメントでは、使用されるアルゴリズムについて説明します。

 *                    n
 * Method:  Let x =  2   * (1+f)
 *      1. Compute and return log2(x) in two pieces:
 *              log2(x) = w1 + w2,
 *         where w1 has 53-24 = 29 bit trailing zeros.
 *      2. Perform y*log2(x) = n+y' by simulating muti-precision
 *         arithmetic, where |y'|<=0.5.
 *      3. Return x**y = 2**n*exp(y'*log2)

その後に、処理されたすべての特殊なケース (0、1、inf、nan) のリストが続きます。

特別なケースの処理をすべて終えた後のコードの最も重要なセクションには、 log2 そして 2** 計算。そして、どちらにもループはありません。したがって、浮動小数点プリミティブの複雑さにもかかわらず、それは漸近的に定数時間アルゴリズムのように見えます。

浮動小数点の専門家 (私は専門家ではありませんが) はコメントを歓迎します。:-)

他のヒント

彼らがより良い方法を見つけていない限り、三角関数、対数関数、指数関数の近似値（たとえば、指数関数の成長と減衰）は一般に算術規則とテイラーシリーズを展開して、要求された精度内で正確な近似結果を生成します。 （関数の累乗級数、テイラー級数、マクローリン級数展開の詳細については、Calculusの本を参照してください。）いずれかを行ってからしばらく経ち、たとえば正確な計算方法がわからないことに注意してください。含める必要があるシリーズの項の数は、倍精度計算で無視できるほど小さいエラーを保証します。

たとえば、e ^ xのTaylor / Maclaurinシリーズ展開は次のとおりです。

      +inf [ x^k ]           x^2    x^3      x^4        x^5
e^x = SUM  [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
      k=0  [  k! ]           2*1   3*2*1   4*3*2*1   5*4*3*2*1

すべての項（0から無限大までのk）を使用する場合、この展開は正確で完全です（エラーなし）。

ただし、すべての用語が無限になるわけではなく、5語または50語などで停止すると、実際のe ^とは異なる近似結果が生成されます計算がかなり簡単な剰余によるx関数値。

指数関数の良いニュースは、それがうまく収束し、その多項式展開の項が反復的にかなり簡単にコーディングできることです。そのため、 might （繰り返し、 MIGHT -覚えておいてくださいしばらく経ちました）各反復で寄与のサイズをテストし、ゼロに十分に近づいたときに停止できるため、エラーが精度未満であることを保証するために必要な用語の数を事前計算する必要さえありません。実際には、この戦略が実行可能かどうかはわかりません。試してみる必要があります。私がずっと忘れていた重要な詳細があります。次のようなもの：マシンの精度、マシンエラー、丸め誤差など

また、e ^ xを使用していないが、2 ^ xや10 ^ xのような別のベースで成長/減衰を行っている場合、近似多項式関数が変化することに注意してください。

整数指数の場合、aをbに上げる通常のアプローチは次のようになります。

result = 1
while b > 0
  if b is odd
    result *= a
    b -= 1
  b /= 2
  a = a * a

通常、指数のサイズは対数です。アルゴリズムは不変式「a ^ b * result = a0 ^ b0」に基づいています。ここで、a0とb0はaとbの初期値です。

負または非整数の指数の場合、対数と近似および数値解析が必要です。実行時間は、使用されるアルゴリズムとライブラリが調整される精度によって異なります。

編集：興味があるように思われるので、ここに余分な乗算のないバージョンがあります。

result = 1
while b > 0
  while b is even
    a = a * a
    b = b / 2
  result = result * a
  b = b - 1

Intelをターゲットとするpow関数を書いている場合、exp2（log2（x）* y）を返します。 Intelのlog2のマイクロコードは、初年度の計算と大学院の数値解析を覚えていたとしても、私がコーディングできるものよりも確実に高速です。

x n の計算にはexp（n * ln（x））を使用できます。 xとnは両方とも倍精度浮動小数点数にすることができます。自然対数と指数関数は、テイラー級数を使用して計算できます。ここで数式を見つけることができます： http://en.wikipedia.org/wiki/Taylor_series

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top