8

末尾再帰の例をいじっているときに、通常の再帰呼び出しと末尾再帰呼び出しの結果の間に小さな不一致があることに気づきました。

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パラメーターはループの各反復で割り当てられ、小さな丸め誤差がそこに滑り込みます。

4

3 に答える 3

15

2つのバージョンは異なる順序で乗算を実行するため、結果は異なります。したがって、異なる丸めが発生します。

通常の再帰呼び出しは、n*([n-1]*([n-2]*(...)))最初にfact（n-1）の値を計算し、次にnを乗算するため、式になります。一方、末尾再帰呼び出しは、最初((n*[n-1])*[n-2])*...にnを乗算し、次にn-1に反復するため、式になります。 。

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

于 2012-08-06T13:52:09.880 に答える
9

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*...し、もう1つのバージョンがを計算し2.*3*...ます。これらの2つの結果がわずかに異なるのは正常です。浮動小数点演算は結合法則ではありません。しかし、結果について計り知れないものは何もないことに注意してください。関数の1つはIEEE754倍精度式を正確に計算し、もう1つは正確30.*29*...にを計算します。どちらも設計どおりに機能します。 2.*3*...

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

于 2012-08-06T13:51:04.213 に答える
6

違いは、Scalaが末尾再帰をループに変えるという事実ではありません。その最適化を行わなくても、結果は同じになります。また、再帰は、丸め誤差に関してループと同じように動作します。

違いは、数字が掛けられる順序です。最初のソリューションは、数値の乗算を開始する前に、1まで繰り返します。したがって、計算することになりますn * ( (n - 1) * (... * (2 * 1)))。末尾再帰バージョンはすぐに乗算を開始するため、最終的にはを計算しますn * (n-1) * ... * 2 * 1。

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

階乗を実装するために1からnまでカウントするforループと、nから1までカウントするforループを使用する場合にも、同じ違いが見られることに注意してください。

于 2012-08-06T13:52:45.653 に答える