Calcul des grandes valeurs de la fonction d'ackermann

Question

J'ai un peu de code :

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

Conçu pour calculer la fonction d'ackermann. Au-dessus d'un nombre assez faible de x et y, l'application provoque un débordement de la pile car elle récure trop profondément et aboutit à des nombres assez grands. Comment pourrais-je calculer lentement une solution ?

Answer 1

À titre d'information, si vous souhaitez simplement utiliser la forme fermée, les algorithmes pour m<4 sont simples. Si vous souhaitez étendre à la tétrade, je vous suggère d'écrire un algorithme de puissance rapide en utilisant probablement la méthode binaire, puis avec cette méthode, vous pouvez écrire une fonction de tétrade. Ce qui ressemblerait à quelque chose comme :

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

Ensuite, vous pouvez couvrir les cas jusqu'à n==4 et après cela, utiliser la définition récursive et les valeurs de A(5,n) débordent à une vitesse ridicule, donc ce n'est vraiment pas un problème. Certes, votre professeur ne sera probablement pas satisfait d'un tel algorithme, mais il s'exécutera beaucoup plus rapidement. Dans l'une de mes classes discrètes, lorsqu'on m'a demandé d'écrire un algorithme pour calculer les nombres de Fibonacci et ensuite trouver son O(n), j'ai écrit la forme fermée puis j'ai écrit O(1) et j'ai obtenu un crédit complet, certains professeurs apprécient les réponses intelligentes.

Ce qu'il est important de noter à propos de la fonction d'Ackerman, c'est qu'elle définit essentiellement l'hériarchie des fonctions additives sur les entiers, A(1,n) est l'addition, A(2,n) est la multiplication, A(3,n) est l'exponentiation, A(4,n) est la tétration et après 5, les fonctions croissent trop vite pour être applicables à grand chose.

Une autre façon de voir l'addition, la multiplication, etc :

Φ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

(Utilise la notation préfixe c'est-à-dire +(x,y)=x+y, (x,y)=x y.

Answer 2

IIRC, une propriété intéressante de la fonction d'Ackermann est que la profondeur maximale de la pile nécessaire pour l'évaluer (en niveaux d'appels) est la même que la réponse à la fonction. Cela signifie qu'il y aura des limites sévères sur le calcul réel qui peut être fait, imposées par les limites de la mémoire virtuelle de votre matériel. Il ne suffit pas d'avoir un paquet arithmétique multiprécision ; vous aurez rapidement besoin de plus de bits pour stocker les logarithmes des logarithmes des nombres qu'il n'y a de particules subatomiques dans l'univers.

Encore une fois, IIRC, vous pouvez dériver des formules fermées relativement simples pour A(1, N), A(2, N), et A(3, N), sur le modèle suivant (je crois me souvenir que 3 figure dans la réponse, mais les détails sont probablement incorrects) :

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

La formule pour A(4, N) implique une certaine manipulation et l'empilement des exposants à N niveaux. La formule pour A(5, N) implique ensuite d'empiler les formules pour A(4, N)... cela devient très vite très bizarre et coûteux.

Au fur et à mesure que les formules deviennent plus complexes, le calcul devient totalement ingérable.

---

L'article de Wikipedia sur le Fonction d'Ackermann comprend une section "Tableau des valeurs". Ma mémoire est rouillée (mais cela fait 20 ans que je n'ai pas regardé cela en détail), et elle donne les formules fermées :

• 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

Et A(4, N) = 2 ^ 2 ^ 2 ^ ... - 3 (où c'est 2 élevé à la puissance 2, N + 3 fois).

Answer 3

(On dirait une question de devoir, mais je vais quand même y répondre...)

Pour en savoir plus sur la fonction d'Ackermann. Par exemple, le Article de WikiPedia dit

"Sa valeur augmente rapidement, même pour les petits apports. Par exemple, A(4,2) est un nombre entier de 19 729 chiffres décimaux".

Je soupçonne que vos entiers 32 bits (ou 64 bits, selon votre architecture) débordent et que vous vous retrouvez dans des boucles infinies à cause de ces problèmes. Un simple débogage de type printf montrerait les débordements d'entiers. Si vous voulez réellement calculer la fonction d'Ackermann, vous devrez utiliser une bibliothèque de bignum à précision infinie, comme par exemple GNU MP .

Lisez aussi Récursion de la queue et comment l'optimiser.

Answer 4

Vous devez effectuer une pré-décrémentation, et non une post-décrémentation, sinon vous ne ferez que transmettre les mêmes valeurs de x et y à la fonction à chaque point. Vous pouvez également intégrer des sécurités pour vous assurer que vous n'avez pas de paramètres négatifs, car la fonction d'Ackerman n'est pas définie si x ou y est négatif.

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