爲什麼我的正常遞歸和尾遞歸示例之間存在舍入差異？

雖然有尾遞歸例子玩弄我注意到一個正常的遞歸調用的結果和尾遞歸調用之間存在細微的差異：爲什麼我的正常遞歸和尾遞歸示例之間存在舍入差異？

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參數在循環的每次迭代中都被分配，並且小的舍入錯誤會在那裏出現。

來源

2012-08-06 Jack

在一個適當的編程語言，比如Scala是，分配一個'Double'結果到一個'Double'變量不引入的舍入誤差。 – 2012-08-06 13:53:19

結果是不同的，因爲兩個版本以不同的順序進行乘法運算，因此導致不同的舍入。因爲您首先計算fact（n-1）的值，然後將其與n相乘，而尾遞歸函數導致((n*[n-1])*[n-2])*...，因爲您先乘以n，然後再乘以n迭代到n-1。

嘗試重寫其中一個版本，以使其迭代另一種方式，理論上應該得到相同的答案。

來源

2012-08-06 13:52:09 Jan

你的兩個函數沒有按照相同的順序進行操作。

在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浮點作品可以預見的平臺）的功能

一個版本計算30.*29*...和另一個計算2.*3*...。這兩個結果略有不同：浮點運算不是關聯的。但是請注意，結果沒有什麼不可思議的。您的一個功能計算完全 IEEE 754雙精度表達式30.*29*...和其他計算完全2.*3*...。他們都按設計工作。

如果我不得不猜測，我認爲2.*3*...更準確（更接近實數所得到的結果），但這並不重要：這兩個數字非常接近並且非常接近實際結果。

來源

2012-08-06 13:51:04

+1。奇怪的事情，但我只是在C＃中嘗試相同。兩個實現都返回完全相同的結果 – 2012-08-06 13:53:24

感謝與C.的優秀對比，我向你提供了答案，但是由於他的代表少，並且也是正確的，所以將新人標記爲正確。希望沒關係。 – Jack 2012-08-06 14:09:49

@JacobusR好主意。爲了與C進行比較，真正的原因是我手邊沒有Scala編譯器，但如果它有助於消除浮點不可預測的神話，那麼更好:) – 2012-08-06 14:43:48

區別不在於Scala將尾遞歸轉換爲循環的事實。沒有這種優化，結果將是一樣的。對於舍入錯誤，循環的行爲與循環所做的不同。

區別在於數字相乘的順序。您的第一個解決方案在開始乘數之前遞歸遞減至1。所以它最終會計算n * ((n - 1) * (... * (2 * 1)))。尾遞歸版本馬上開始相乘，所以它最終計算n * (n-1) * ... * 2 * 1。

當然通常我們會說這兩個是相同的，因爲乘法是關聯的，但對於浮點算術來說並不是這樣。使用浮點數(x * y) * z可能與x * (y * z)有很大不同，因爲舍入誤差的傳播方式不同。這就解釋了你的行爲。

請注意，使用從1到n計數的for循環與從n計數到1來實現階乘的for循環會看到相同的差異。

來源

2012-08-06 13:52:45 sepp2k

爲什麼我的正常遞歸和尾遞歸示例之間存在舍入差異？

回答

相關問題