Computing Ackermann [4,1]

How much RAM do we need to compute this one? I watched a video on youtube from computerphile where a professor explained how he used a very old computer and while it took him a long time to get the answer there was no overflow problems. If RAM plays a very important role, which I believe it does since we are abusing the heck out of the stack, someone please tell me how much so that I am able to run it on my computer

It would be nice if you could provide a link / links to background material that will shed light on what exactly you're talking about. You shouldn't presume that folks will go out and try to find that stuff for themselves.

I apologize. I wrongfully assumed everyone would know what Ackermann. I just got caught up in the moment that I did not even think of explaining what it is. I will post a link and more details about it after class.

Thanks

Thanks

It completely depends on how you write your application. You can write a naive implementation that just defines the function similar to it's mathematical definition:

This however quickly results in a`StackOverflowError`. Instead, let's do some analysis on paper first. This is what I got:

Adding special cases for`m <= 3` and memorizing results we've calculated before yields the following code:

This program finishes running almost instantly and if I comment out line 20 it prints the following results, which should give you an indication of the amount of memory it uses:

This however quickly results in a

Adding special cases for

This program finishes running almost instantly and if I comment out line 20 it prints the following results, which should give you an indication of the amount of memory it uses:

Wow, I can't really follow up. I am not familiar with Maps or many of those terms you have used. Now that I'm on spring break I'll read ahead on the chapter on Maps ADT. What do you mean by

`which should give you an indication of the amount of memory it uses`

When we get the final results for n, is that an indication of memory use? If you have already explained it throughout the code sorry for asking about it. We had to program Ackermann for my CSC class computing the value, doing tracing like you did and also doing table look-up that stores already found values in a 2D array that way before we go into the if statements first we see if the previous recursive call is in the table already. If it is, then we can return it thus optimizing the program. But I am not that advanced yet in Java which is why I am lost in the second code you posted.

Thanks for the amazing detailed explanation. I'll get back to it when I'm ready!

For those unfamiliar with Ackerman watch this video on YouTube; Professor Brailsford explains what it is. There were certain things in the computing world that were so big that just had to be done recursively. Some people argued that they can just be done with for loops instead. Ackermann, a research student of mathematician David Hilbert was apparently the first to realize this and wondered if there actually was a problem that could only be done recursively. Very insightful video.

When we get the final results for n, is that an indication of memory use? If you have already explained it throughout the code sorry for asking about it. We had to program Ackermann for my CSC class computing the value, doing tracing like you did and also doing table look-up that stores already found values in a 2D array that way before we go into the if statements first we see if the previous recursive call is in the table already. If it is, then we can return it thus optimizing the program. But I am not that advanced yet in Java which is why I am lost in the second code you posted.

Thanks for the amazing detailed explanation. I'll get back to it when I'm ready!

For those unfamiliar with Ackerman watch this video on YouTube; Professor Brailsford explains what it is. There were certain things in the computing world that were so big that just had to be done recursively. Some people argued that they can just be done with for loops instead. Ackermann, a research student of mathematician David Hilbert was apparently the first to realize this and wondered if there actually was a problem that could only be done recursively. Very insightful video.

That was a really cool video, have a cow!

That's exactly what my program does as well. An array is a data structure that takes an integer, and returns a value associated with that integer. A two-dimensional array takes two integers and returns a value associated with the Cartesian product of those two integers. A`Map` also takes one value, and returns a value associated with it. `Map<Integer, Map<Integer, Integer>>` is really the same as `int[][]`, and calling `memorizeResult(m, n, result)`, is the same as performing `array[m][n] = result`. I chose `Map` because the size of an array needs to be known ahead of time, while a `Map` can grow as needed.

Here's the same code, except in less concise form:

The results that my program print are ALL the calculations that it stored in the table in order to compute`A(4,1)` fast. It didn't store anything for `m <= 2`, because those values are calculated directly from the special cases that I added on lines 18 and 19 of the original code. If I disable those lines, the memory and time used become MUCH greater. This is not an indication of peak memory usage though, because it doesn't count stack frames. Indeed, the stack will blow up much sooner than the `Map`...

It's interesting that the professors in the video need so much time to calculate`A(4,1)`, because that would mean they're not using memoization, and they have a huge stack to be able to make the recursive calls.

If I replace all`Integers` in my program with `BigIntegers` and enable the special case for `(m == 3)`, my application is able to immediately calculate `A(4,2)`:

You can imagine that calculating`A(4,3)` or `A(5,1)` is not going to happen...

Daniel Andres wrote:doing table look-up that stores already found values in a 2D array

That's exactly what my program does as well. An array is a data structure that takes an integer, and returns a value associated with that integer. A two-dimensional array takes two integers and returns a value associated with the Cartesian product of those two integers. A

But I am not that advanced yet in Java which is why I am lost in the second code you posted.

Here's the same code, except in less concise form:

When we get the final results for n, is that an indication of memory use?

The results that my program print are ALL the calculations that it stored in the table in order to compute

It's interesting that the professors in the video need so much time to calculate

If I replace all

You can imagine that calculating

To test this yourself, here is the full program:

A cow ... and a move to another forum as too difficult for here.

Thank you for posting your code @Stephan van Hulst. I will test it myself.

@Campbell I meant to post this under general java.

@Campbell I meant to post this under general java.

But the discussion has become more complicated since then.

Agree. I meant to say that instead of posting in beginners java it was supposed to be under general.

This thread has been viewed 27853 times.

All times above are in ranch (not your local) time.

The current ranch time is

Nov 20, 2018 04:22:17.

The current ranch time is

Nov 20, 2018 04:22:17.