cálculo de los valores más grandes de la función de Ackermann

Question

que tienen algo de código:

int CalculateAckermann(int x, int y) 
{ 
    if(!x) 
    { 
     return y++; 
    } 
    if(!y) 
    { 
     return CalculateAckermann(x--,1); 
    } 
    else 
    { 
     return CalculateAckermann(x--, CalculateAckermann(x, y--)); 
    } 
} 

Diseñado para calcular la función de Ackermann. Por encima de un número bastante bajo de xey, la aplicación provoca un desbordamiento de la pila porque recursivas demasiado profundamente y produce números bastante grandes. ¿Cómo haría para calcular lentamente una solución?

Answer 1

Como nota, si desea simplemente utilizar el formulario cerrado, entonces los algoritmos para m < 4 son sencillos. Si desea extender a la tetration, le sugiero que escriba un algoritmo de potencia rápida probablemente utilizando el método binario y luego con ese método puede escribir una función de tetration. ¿Qué sería algo como:

int Tetration(int number, int tetrate) 
{ 
    long int product=1; 
    if(tetrate==0) 
     return product; 
    product=number; 
    while(tetrate>1) 
    { 
     product=FastPower(number,product); 
     tetrate--; 
    } 
    return product; 
} 

A continuación, puede abarcar los casos hasta n == 4 y después de eso utilizar la definición recursiva y los valores de un desbordamiento (5, n) a una velocidad ridícula, así que es realmente de ninguna preocupación. Aunque su profesor probablemente no estará satisfecho con un algoritmo como este, pero se ejecutará mucho más rápido. En una de mis clases discretas cuando pedí escribir un algoritmo para calcular los números de Fibonacci y luego encontrar su O (n), escribí la forma cerrada y luego escribí O (1) y obtuve todo el crédito, algunos profesores aprecian las respuestas inteligentes.

Lo que es importante tener en cuenta acerca de la función Ackerman es que define esencialmente la heiraquía de las funciones aditivas en los enteros, A (1, n) es suma, A (2, n) es multiplicación, A (3, n) es exponenciación, A (4, n) es tetration y después de 5 las funciones crecen demasiado rápido para ser aplicables en gran medida.

Otra manera de mirar en suma, multiplicación, etc es:

Φ0 (x, y) = y + 1 
Φ1 (x, y) = +(x, y) 
Φ2 (x, y) = ×(x, y) 
Φ3 (x, y) = ↑ (x, y) 
Φ4 (x, y) = ↑↑ (x, y) 
      = Φ4 (x, 0) = 1 if y = 0 
      = Φ4 (x, y + 1) = Φ3 (x, Φ4 (x, y)) for y > 0 

(utiliza la notación de prefijo es decir + (x, y) = x + y, (x, y) = x y.

Answer 2

Necesita decremento previo, no decremento posterior, o simplemente está pasando los mismos valores de xey a la función en cada punto. Es posible que también desee incluir algunos dispositivos de seguridad para asegurarse de que no tiene parámetros negativos, ya que la función de Ackerman no está definida si x o y es negativo.

int CalculateAckermann(int x, int y) 
{ 
    if (x < 0 || y < 0) 
    { 
     abort(); 
    } 

    if(x == 0) 
    { 
     return y+1; 
    } 
    if(y == 0) 
    { 
     return CalculateAckermann(x-1,1); 
    } 
    else 
    { 
     return CalculateAckermann(x-1, CalculateAckermann(x, y-1)); 
    } 
} 

Answer 3

(Se siente como una pregunta tarea, pero voy a responder de todos modos ...)

Leer un poco más en la función de Ackermann. Por ejemplo, los grupos la WikiPedia article dice

"Su valor crece rápidamente, incluso para entradas pequeñas. Por ejemplo A (4,2) es un número entero de 19,729 dígitos decimales".

Sospecho que sus enteros de 32 bits (o 64 bits, según su arquitectura) se están desbordando y se está metiendo en bucles infinitos debido a esos problemas. La depuración simple de estilo de impresión mostraría los desbordamientos de enteros. Si desea calcular realmente la función de Ackermann, necesitará usar una biblioteca infinita de precisión bignum, como GNU MP.

Además, lea en Tail Recursion, y la forma de optimizarlo.

Answer 4

IIRC, una propiedad interesante de la función Ackermann es que la profundidad máxima de pila necesaria para evaluarlo (en niveles de llamadas) es la misma que la respuesta a la función. Esto significa que habrá límites severos en el cálculo real que se puede hacer, impuestos por los límites de la memoria virtual de su hardware. No es suficiente tener un paquete aritmético de precisión múltiple; rápidamente necesita más bits para almacenar los logaritmos de los logaritmos de los números que las partículas subatómicas en el universo.

De nuevo, IIRC, puede derivar fórmulas cerradas relativamente simples para A (1, N), A (2, N) y A (3, N), en la línea de lo siguiente (me parece recordar 3 que figuran en la respuesta, pero los detalles son probablemente incorrecta):

• a (1, N) = 3 + N
• a (2, N) = 3 * N
• a (3, N) = 3^N

La fórmula para A (4, N) implica agitar con la mano y apilar los exponentes N-profundo. La fórmula para A (5, N) implica el apilamiento de las fórmulas para A (4, N) ... se vuelve bastante raro y caro muy rápidamente.

A medida que las fórmulas se vuelven más complejas, el cálculo se vuelve completamente inmanejable.

---

El artículo de Wikipedia sobre el Ackermann function incluye una sección 'Tabla de Valores'.Mi memoria es oxidado (pero que era hace 20 años el pasado Miré a esto en detalle), y da las fórmulas cerradas:

• A (0, n) = N + 1
• A (1 , N) = 2 + (N + 3) - 3
• A (2, N) = 2 * (N + 3) - 3
• A (3, N) = 2^(N + 3) - 3

Y A (4, N) = 2^2^2^... - 3 (donde eso es 2 elevado a la potencia de 2, N + 3 veces).