通常の再帰の例と末尾の再帰の例の間に丸めの違いがあるのはなぜですか？

Question

私は、通常の再帰呼び出しの結果と末尾再帰呼び出しの間に小さな食い違いに気づい末尾再帰の例をいじる中：

scala> def fact(n: Int): Double = if(n < 1) 1 else n * fact(n - 1) 
fact: (n: Int)Double 

scala> fact(30) 
res31: Double = 2.6525285981219103E32 

scala> @tailrec def fact(n: Int, acc: Double = 1): Double = if(n < 1) acc else fact(n - 1, n * acc) 
fact: (n: Int, acc: Double)Double 

scala> fact(30) 
res32: Double = 2.652528598121911E32 

ただ、好奇心から、なぜか、どこの誰かが私に説明してくださいすることができます丸めが発生しています。私の推測では、Scalaコンパイラはテールの再帰バージョンをループに変換するため、ループの各繰り返しでaccパラメータが割り当てられ、小さな丸め誤差がそこに入ることになります。

Answer 1

2つのバージョンが異なる順序で乗算を行うため、異なる丸めにつながるため、結果が異なります。

ファクト（n-1）の値を最初に計算してからnに乗算するので、通常の再帰呼び出しでは式n*([n-1]*([n-2]*(...)))が得られますが、尾部の再帰的な数値は最初にnで掛け算してから((n*[n-1])*[n-2])*...になります。 n-1に反復する。

他の方法を繰り返すようにバージョンを書き直してください。理論的には同じ回答が得られるはずです。

Answer 2

あなたの2つの機能は、同じ順序で操作を実行していません。 Cにおいて

：

int main(int c, char **v) 
{ 
    printf ("%.16e %.16e\n", 
     30.*29*28*27*26*25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2, 
     2.*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30); 
} 

プリント：

2.6525285981219110e+32 2.6525285981219103e+32 

（私はCで浮動小数点予想通りに動作するプラットフォームを使用）あなたの関数の

1つのバージョンは、30.*29*...を計算し他の計算は2.*3*...です。 これらの2つの結果がわずかに異なるのは正常です。浮動小数点演算は連想ではありません。しかし、結果については何も解明できないことに注意してください。あなたの関数の1つは、正確に IEEE 754倍精度式30.*29*...を計算し、もう1つは正確に2.*3*...と計算します。どちらも設計どおりに動作します。

もし私が推測しなければならないのは、2.*3*...がより正確であること（実数で得られた結果に近い）ですが、それは問題ではありません：2つの数値は非常に近く、実際の結果に非常に近いことです。

Answer 3

違いは、Scalaがテール再帰をループに変えるということではありません。その結果は、その最適化なしで同じになります。また、反復は、ループよりも丸め誤差に関して異なって動作しません。

数値が乗算される順序が異なります。あなたの最初の解決策は、数字の乗算を始める前に、1に至るまですべての過程を繰り返します。したがって、計算はn * ((n - 1) * (... * (2 * 1)))となります。テール再帰バージョンはすぐに乗算を開始するので、計算はn * (n-1) * ... * 2 * 1となります。

もちろん、通常は乗算は連想的であるため同じものですが、浮動小数点演算には当てはまりません。浮動小数点数を使用すると(x * y) * zはx * (y * z)と大きく異なる場合があります。これは、丸め誤差が異なる形で伝播するためです。それはあなたの行動を説明します。

1からnまでのforループと、nから1までのforループを使用して階乗を実装する場合、同じ違いがあることに注意してください。