c++recursionackermann

A double recursive function


I wanted to code a function (modified version of Ackermann's funciton) defined in A Tour Through Mathematical Logic by S. Wolf as follows:

A(0,n)=n+1 for every n

A(1,0)=2

A(2,0)=0

A(m+3,0)=1 for every m

A(m+1,n+1)=A(m,A(m+1,n)) for every m and n

To make a faster program, I used the fact that

Here's the code:

#include <iostream>
#include <cmath>

using namespace std;

long long A(long long m, long long n)
{
    if(m==0)
        return n+1;
    else if(m==1)
        return n+2;
    else if(m==2)
        return 2*n;
    else if(m==3)
        return pow(2,n);
    else if(m>=4 && n==0)
        return 1;
    else
        return A(m-1,A(m,n-1));
}

int main(void)
{
    long long m,n;
    cout << "m=";
    cin >> m;
    cout << "n=";
    cin >> n;
    cout << "A(m,n)=" << A(m,n) << endl;
    return 0;
}

It seemed to work fine: by hand, A(5,3)=2^16 and that's the result that I get. However, the program outputs A(5,4)=4 and A(5,5)=2^16, whereas the correct result is really huge. I couldn't spot the mistake in my code. Could you tell me what's wrong please? Thank you in advance.


Solution

  • As NeilButterworth said in the comments, the reason behind the wrong results is the overflow.

    As suggested RobertAndrzejuk in the comments, I used another library (GMP) to handle large numbers. Here's the new code:

    #include <iostream>
    #include <cmath>
    #include <gmpxx.h>
    
    using namespace std;
    
    mpz_class pow(int a,mpz_class b)
    {
        mpz_class res=1;
        for(int i=1;i<=b;++i)
            res*=a;
        return res;
    }
    
    mpz_class A(mpz_class m, mpz_class n)
    {
        if(m==0)
            return n+1;
        else if(m==1)
            return n+2;
        else if(m==2)
            return 2*n;
        else if(m==3)
            return pow(2,n);
        else if(m>=4 && n==0)
            return 1;
        else
            return A(m-1,A(m,n-1));
    }
    
    int main(void)
    {
        mpz_class m,n;
        cout << "m=";
        cin >> m;
        cout << "n=";
        cin >> n;
        cout << "A(m,n)=" << A(m,n) << endl;
        return 0;
    }
    

    The program was able to compute A(4,5), which had 19729 digits (I can't verify if the result is correct, but the exact number of digits of A(4,5) is indeed 19729 so I believe the result is correct). Then the program indicated segmentation fault when I asked it to compute A(5,4), which is really huge.