0

I am trying to run the Ackermann function1 and I am having an issue. I am trying to run the program through my Command Prompt, on a Windows 10 machine, and a few seconds after reaching the value pair (4,0) the program stops. I am assuming because it has run out of available resources, but I am not sure at all. Is there a way to fix this issue? TIA.

I am using the MinGw G++ compiler [8.1.0].

Here is the code in question as well.

#include <iostream>
#include <ctime>

int ack(int m, int n)
{
    int ans;
    if (m == 0)
        ans = n + 1;

    else if (n == 0)
        ans = ack(m - 1, 1);

    else
        ans = ack(m - 1, ack(m, n - 1));

    return ans;
}

void runAck(time_t start) 
{
    int answer;
    double seconds;
    time_t now_t;

    for(int i = 0; i <= 6; i++)
    {
        for(int j = 0; j<= 6; j++)
        {
            answer = ack(i, j);
            time(&now_t);
            seconds = difftime(now_t, start);
            printf("Ackermann(%i, %i) is %i. Found in %.3f seconds.\n", i, j, answer, seconds);
        }
    }
}

int main()
{
    std::cout << "Testing of the Ackermann recursion." << std::endl;
    time_t start = time(NULL);
    runAck(start);
    
    return 0;
}

I initially thought it was because I was using VSCode to access the command prompt but when I use it directly there is no change. While writing this question, I just thought of trying out a different OS or Ubuntu to see if there is any difference.

My goal is just to get to (4,1) to see how much faster it is now to calculate.

1 The Ackermann Function is a recursion function that was developed as computer theory to create a function that can only be calculated recursively.

Edit 1 @MikeCAT helped me realize what I was truly asking and answered my question.

kemenike
  • 1
  • 1
  • Please run your code under a debugger. You'll see where it fails. – Kuba hasn't forgotten Monica Apr 26 '21 at 12:48
  • 1
    It looks like you have to increase the stack size. What is your compiler? – MikeCAT Apr 26 '21 at 12:48
  • 4
    Ackermann function is designed to grow extremely quickly. If nothing else, it's going to overflow `int` even for very small arguments, whereupon your code exhibits undefined behavior. Why do you want to compute its values in the first place? It's of mostly theoretical interest. – Igor Tandetnik Apr 26 '21 at 12:48
  • for g++: [How to increase stack size when compiling a C++ program using MinGW compiler - Stack Overflow](https://stackoverflow.com/questions/54821412/how-to-increase-stack-size-when-compiling-a-c-program-using-mingw-compiler) – MikeCAT Apr 26 '21 at 12:49
  • Visual Studio: [visual studio - Increase stack size in c++ - Stack Overflow](https://stackoverflow.com/questions/40157847/increase-stack-size-in-c) – MikeCAT Apr 26 '21 at 12:50
  • 2
    For the proposed reasons being offered, would there not have been an error message? It wouldn't "just stop," right? – sweenish Apr 26 '21 at 12:50
  • 1
    according to [wikipedia](https://en.wikipedia.org/wiki/Ackermann_function) `ack(4,0)` is `2^(2^65536) - 3` (while `ack(3,0)` is only `61`). You wont reach `ack(6,6)` with any common integer type – 463035818_is_not_an_ai Apr 26 '21 at 12:54
  • @largest_prime_is_463035818 It looks like `ack(4, 3)` and `ack(3,3)`, not `ack(4, 0)` and `ack(3, 0)`. – MikeCAT Apr 26 '21 at 12:55
  • Why do you think that the program stopped? Describe what happens. – eerorika Apr 26 '21 at 12:56
  • oh, my bad again. I completely misread the table. `ack(4,0)` is only `13`. Nevertheless `ack(6,6)` is out of reach with `int` – 463035818_is_not_an_ai Apr 26 '21 at 12:57
  • Either increase your stack, or rewrite it to run non-recursively. – Devolus Apr 26 '21 at 13:00
  • 2
    [The Value of A(4, 2)](https://web.archive.org/web/20100120134707/http://kosara.net/thoughts/ackermann42.html) - "_This number has 19,729 digits._" - Sounds pretty discouraging – Ted Lyngmo Apr 26 '21 at 13:07
  • the actual question is "Why does it stop?". If running the executable crashes without error message thats a little strange, but a debugger will tell you – 463035818_is_not_an_ai Apr 26 '21 at 13:22
  • 1
    On my machine `ack(4,2)` crashed at a recursion depth of 174631 with clang++ and 392594 with g++ when it tried to recurse down yet another level. – Ted Lyngmo Apr 26 '21 at 13:49
  • @MikeCAT Thank you very much. Increasing the stack size is what I needed. _Maybe I shouldn't be programming at 3 in the morning._ – kemenike Apr 26 '21 at 16:54
  • @kemenike Do you mean that it was able to calculate `ack(4,2)` after you increased the stack size? I doubt it. What was the answer you got? – Ted Lyngmo Apr 27 '21 at 05:28
  • @TedLyngmo I used an unsigned long long int, but I didn't make it to the end. I forgot to turn off automatic windows updates and it restarted my computer during runtime. :( That being said though, I was not planning on making it to ack(4,2) I just wanted to see the time difference between my ack(4,1) and the ack(4,1) from the video. – kemenike May 05 '21 at 09:12

0 Answers0