A double recursive function

Question

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

A(1,n)=n+2
A(2,n)=2n
A(3,n)=2^n

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.

Ackermann's function produces really large numbers - `long long` integers are not really large numbers, so you get overflow. Best bet is to use a language that does support very large numbers, such as Haskell or Scheme. — , Apr 15 '18 at 21:14
Saying "use another language" is not really a C++ answer - and someone might have a better C++ specific solution - there's usually something in Boost :-) — , Apr 15 '18 at 22:01
Maybe this will help to use big numbers: https://stackoverflow.com/questions/117429/handling-large-numbers-in-c — Robert Andrzejuk, Apr 15 '18 at 22:31
And from boost: https://www.boost.org/doc/libs/1_67_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html Example at the end. — Robert Andrzejuk, Apr 15 '18 at 22:38
@NeilButterworth Didn't know about Boost. Gonna keep it in mind. Thank you! — Scientifica, Apr 16 '18 at 09:42
@RobertAndrzejuk Thank you very much. I used GMP as proposed in your link. It allowed me to print A(4,5), which was really big (I got -9223372036854775808 with the previous program). Then I got segmentation fault when I asked to compute A(5,4), which is a good result (better show it's too huge rather than have an integer overflow and get wrong results). — Scientifica, Apr 16 '18 at 09:52

score 0 · Accepted Answer · answered Apr 16 '18 at 10:11

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.

A double recursive function

1 Answers1