Win a copy of Java Mock Exams (software) this week in the Programmer Certification (OCPJP) forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Computing Ackermann [4,1]

 
Daniel Andres
Ranch Hand
Posts: 92
3
AngularJS C++ Chrome Eclipse IDE Oracle Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Junilu Lacar
Marshal
Posts: 10379
123
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Daniel Andres
Ranch Hand
Posts: 92
3
AngularJS C++ Chrome Eclipse IDE Oracle Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
 
Daniel Andres
Ranch Hand
Posts: 92
3
AngularJS C++ Chrome Eclipse IDE Oracle Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.


 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That was a really cool video, have a cow!

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...
 
Stephan van Hulst
Bartender
Posts: 6646
90
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To test this yourself, here is the full program:
 
Campbell Ritchie
Marshal
Posts: 53112
124
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A cow ... and a move to another forum as too difficult for here.
 
Daniel Andres
Ranch Hand
Posts: 92
3
AngularJS C++ Chrome Eclipse IDE Oracle Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for posting your code @Stephan van Hulst. I will test it myself.

@Campbell I meant to post this under general java.
 
Campbell Ritchie
Marshal
Posts: 53112
124
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But the discussion has become more complicated since then.
 
Daniel Andres
Ranch Hand
Posts: 92
3
AngularJS C++ Chrome Eclipse IDE Oracle Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agree. I meant to say that instead of posting in beginners java it was supposed to be under general.
 
Happiness is not a goal ... it's a by-product of a life well lived - Eleanor Roosevelt. Tiny ad:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/Thread-Boost-feature
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!