Warum gibt es einen Rundungsunterschied zwischen meinem Beispiel für normale Rekursion und Tail-Rekursion?

Question

Während mit einem Endrekursion Beispiel liebäugelt bemerkte ich eine kleine Diskrepanz zwischen den Ergebnissen eines normalen rekursive Aufruf und einem Schwanz rekursive Aufruf:

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 

Nur aus Neugier, kann mir bitte jemand erklären, warum oder wo die das Runden geschieht. Meine Vermutung ist, dass, weil der Scala-Compiler die rekursive Tail-Version in eine Schleife übersetzt, der Parameter acc bei jeder Iteration der Schleife zugewiesen wird, und dass der kleine Rundungsfehler dort hineinrutscht.

Answer 1

Das Ergebnis ist anders, weil die beiden Versionen die Multiplikationen in unterschiedlicher Reihenfolge durchführen, was zu unterschiedlichen Rundungen führt.

Der normale rekursive Aufruf führt zu einem Ausdruck n*([n-1]*([n-2]*(...))), weil Sie zuerst den Wert von fact (n-1) berechnen und dann mit n multiplizieren, während der rekursive Schwanz zu ((n*[n-1])*[n-2])*... führt, weil Sie zuerst mit n multiplizieren und dann Iteriere weiter zu n-1.

Versuchen Sie, eine der Versionen neu zu schreiben, so dass sie anders herum iteriert wird, und Sie sollten theoretisch die gleiche Antwort erhalten.

Answer 2

Ihre zwei Funktionen führen die Operationen nicht in der gleichen Reihenfolge durch.

In 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); 
} 

druckt:

2.6525285981219110e+32 2.6525285981219103e+32 

(ich eine Plattform verwendet, auf dem Gleitkommazahlen in C vorhersagbar arbeitet)

Eine Version Ihrer Funktion berechnet 30.*29*... und der andere berechnet 2.*3*.... Es ist normal, dass diese beiden Ergebnisse geringfügig abweichen: Gleitkommaoperationen sind nicht assoziativ. Aber bitte beachten Sie, dass die Ergebnisse nicht unergründlich sind. Eine Ihrer Funktionen berechnet genau die IEEE 754 doppelt genaue Ausdruck 30.*29*... und die andere genau berechnet2.*3*.... Beide funktionieren wie geplant.

Wenn ich raten müsste, würde ich erwarten, dass 2.*3*... genauer ist (näher an das Ergebnis mit reellen Zahlen erhalten), aber es spielt keine Rolle: die beiden Zahlen sind sehr nah und sehr nah an das reale Ergebnis.

Answer 3

Der Unterschied ist nicht über die Tatsache, dass Scala die Tail-Rekursion in eine Schleife verwandelt. Ohne diese Optimierung wäre das Ergebnis dasselbe. Auch die Rekursion verhält sich in Bezug auf Rundungsfehler nicht anders als Loops.

Der Unterschied ist die Reihenfolge, in der die Zahlen multipliziert werden. Ihre erste Lösung wird bis auf 1 zurückgespielt, bevor sie mit der Multiplikation der Zahlen beginnt. Also wird es am Ende n * ((n - 1) * (... * (2 * 1))) berechnen. Die rekursive Version des Tails beginnt sofort mit der Multiplikation, so dass sie n * (n-1) * ... * 2 * 1 berechnet.

Natürlich würden wir sagen, dass diese beiden die gleichen sind, weil die Multiplikation assoziativ ist, aber das gilt nicht für Fließkomma-Arithmetik. Die Verwendung von Gleitkommawerten (x * y) * z kann sehr wohl von x * (y * z) abweichen, da sich Rundungsfehler anders ausbreiten. Das erklärt dein Verhalten.

Beachten Sie, dass Sie den gleichen Unterschied sehen werden, wenn eine for-Schleife, die von 1 bis n im Vergleich zu einem zählt, die zu 1 von n zählen zu dem Fakultäts zu implementieren.