Perché c'è una differenza di arrotondamento tra la mia ricorsione normale e l'esempio di ricorsione della coda?

Question

Mentre giocando con un esempio di ricorsione in coda ho notato una piccola discrepanza tra i risultati di una normale chiamata ricorsiva e una coda chiamata ricorsiva:

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 

Solo per curiosità, qualcuno può spiegarmi perché o dove la l'arrotondamento sta accadendo. La mia ipotesi è che, poiché il compilatore Scala traduce la versione ricorsiva della coda in un ciclo, il parametro acc viene assegnato ad ogni iterazione del ciclo e che l'errore di arrotondamento piccolo si inserisce al suo interno.

Answer 1

Il risultato è diverso perché le due versioni eseguono le moltiplicazioni in ordine diverso, portando così a arrotondamenti diversi.

La chiamata ricorsiva normale porta ad un'espressione n*([n-1]*([n-2]*(...))), perché prima di calcolare il valore di fatto (n-1) e poi moltiplicarlo con n, mentre la coda ricorsiva porta a ((n*[n-1])*[n-2])*... perché prima moltiplicare per n e poi itera su n-1.

Provare a riscrivere una delle versioni in modo che iterini nell'altro modo e si dovrebbe, teoricamente, ottenere la stessa risposta.

Answer 2

Le tue due funzioni non eseguono le operazioni nello stesso ordine.

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

stampe:

2.6525285981219110e+32 2.6525285981219103e+32 

(io ho usato una piattaforma su cui virgola mobile in C funziona prevedibilmente)

Una versione della funzione calcola 30.*29*... e l'altro calcola 2.*3*.... È normale che questi due risultati siano leggermente diversi: le operazioni in virgola mobile non sono associative. Ma tieni presente che non c'è nulla di incomprensibile nei risultati. Una delle tue funzioni calcola lo esattamente l'espressione di precisione doppia IEEE 754 30.*29*... e gli altri calcoli esattamente2.*3*.... Entrambi funzionano come progettato.

Se dovessi indovinare, mi aspetto che 2.*3*... sia più preciso (più vicino al risultato ottenuto con numeri reali), ma non importa: i due numeri sono molto vicini e molto vicini al risultato reale.

Answer 3

La differenza non riguarda il fatto che Scala trasforma la ricorsione della coda in un loop. Il risultato sarebbe lo stesso senza quell'ottimizzazione. Anche la ricorsione non agisce diversamente per quanto riguarda gli errori di arrotondamento rispetto ai loop.

La differenza è l'ordine in cui i numeri vengono moltiplicati. La prima soluzione ricorre fino a 1 prima che inizi a moltiplicare i numeri. Quindi finirà per calcolare n * ((n - 1) * (... * (2 * 1))). La versione ricorsiva della coda inizia a moltiplicarsi subito, quindi finisce per calcolare n * (n-1) * ... * 2 * 1.

Naturalmente, di solito, diciamo che questi due sono gli stessi perché la moltiplicazione è associativa, ma non è vero per l'aritmetica in virgola mobile. L'utilizzo dei punti mobili (x * y) * z potrebbe essere molto diverso da x * (y * z) poiché gli errori di arrotondamento si propagano in modo diverso. Questo spiega il tuo comportamento.

Nota che vedrai la stessa differenza quando usi un ciclo for che conta da 1 a n contro uno che conta da n a 1 per implementare il fattoriale.