¿Por qué hay una diferencia de redondeo entre mi recursión normal y el ejemplo de recursión de cola?

Question

Si bien jugando con un ejemplo de recursión de cola he notado una pequeña discrepancia entre los resultados de una llamada recursiva normal, y una cola llamada recursiva:

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 

Sólo por curiosidad, por favor alguien puede explicarme por qué o cuando el el redondeo está sucediendo. Mi suposición es que debido a que el compilador de Scala traduce la versión recursiva de la cola a un bucle, el parámetro acc se asigna en cada iteración del bucle, y que el pequeño error de redondeo se desliza allí.

Answer 1

El resultado es diferente porque las dos versiones hacen las multiplicaciones en orden diferente, lo que da lugar a diferentes redondeos.

La llamada recursiva normal lleva a una expresión n*([n-1]*([n-2]*(...))), porque primero calcula el valor de hecho (n-1) y luego lo multiplica con n, mientras que la cola recursiva lleva a ((n*[n-1])*[n-2])*... porque primero se multiplica por n y luego iterar a n-1.

Intente reescribir una de las versiones para que se repita en sentido contrario y, en teoría, debería obtener la misma respuesta.

Answer 2

Sus dos funciones no están haciendo las operaciones en el mismo orden.

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

impresiones:

2.6525285981219110e+32 2.6525285981219103e+32 

(He utilizado una plataforma en la que de punto flotante en C funciona previsiblemente)

Una versión de su función calcula 30.*29*... y el otro calcula 2.*3*.... Es normal que estos dos resultados sean ligeramente diferentes: las operaciones de coma flotante no son asociativas. Pero tenga en cuenta que no hay nada insondable en los resultados. Una de sus funciones calcula exactamente la expresión de doble precisión IEEE 754 30.*29*... y la otra calcula exactamente2.*3*.... Ambos trabajan según lo diseñado.

Si tuviera que adivinar, esperaría que 2.*3*... fuera más preciso (más cerca del resultado obtenido con números reales), pero no importa: los dos números están muy cerca y muy cerca del resultado real.

Answer 3

La diferencia no se trata del hecho de que Scala convierte la recursividad de cola en un bucle. El resultado sería el mismo sin esa optimización. Además, la recursividad no actúa de forma diferente con respecto a los errores de redondeo que los loops do.

La diferencia es el orden en que se multiplican los números. Su primera solución vuelve a bajar hasta 1 antes de comenzar a multiplicar los números. Entonces terminará calculando n * ((n - 1) * (... * (2 * 1))). La versión recursiva de cola comienza a multiplicarse de inmediato, por lo que termina calculando n * (n-1) * ... * 2 * 1.

Por supuesto, generalmente, diríamos que esos dos son iguales porque la multiplicación es asociativa, pero eso no es cierto para la aritmética de coma flotante. El uso de puntos flotantes (x * y) * z bien puede ser diferente de x * (y * z) porque los errores de redondeo se propagan de manera diferente. Entonces eso explica tu comportamiento.

Tenga en cuenta que verá la misma diferencia al usar un for-loop que cuenta de 1 a n frente a uno que cuenta de n a 1 para implementar el factorial.