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
Post by:Junilu Lacar
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.
Post by:Daniel Andres
, Ranch Hand
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.
Post by:Stephan van Hulst
, Saloon Keeper
(3 likes, 2 cows)
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:
Post by:Daniel Andres
, Ranch Hand
(0 likes, 1 cow)
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.
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 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.
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 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...