• Post Reply Bookmark Topic Watch Topic
  • New Topic

Ackermann function  RSS feed

 
David Freed
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello my friends,
for the function Ackermann, i wrote this function in this way,actually it should work on natural numbers,means 0 oder greader. for the input numbers 2,3 it works, but for example when you enter 5,0 then
we will have stackoverflow, i don't know why, it doesn't work for all the numbers, for most of them i get stackoverflow, but just for some of them it works well.

thank you advance.




 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The Ackermann recursion grows super-exponentially. If memory serves, for m > 3 it will not terminate using a standard computer/algorithm due to the recursion depth. Its Wikipedia page has a table of values that illustrates that.
 
David Freed
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks,
how can i change the dedicated the memory dedicated? I searched to find a way to change the dedicated memory in eclipse,but i coudnt find anything.
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Allocating more memory will not help. At best it will allow you to calculate A(5,0) and A(4,1), but nothing beyond that for m > 3.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David Freed wrote:how can i change the dedicated the memory dedicated? I searched to find a way to change the dedicated memory in eclipse,but i coudnt find anything.

As Ulf says, it won't help you, since recursion depth also increases exponentially (possibly even by stacked powers). Your only real solution therefore is not to use recursion at all - and BigInteger's, not longs - and even then, you're likely to be able to blow BigInteger's size limit with relatively small values - that is, if you're willing to wait.

Ackermann was discovered as proof that not all computable functions are primitive recursible, so it stands to reason that you're unlikely to be able to use POR (plain old recursion) to get it done. And the numbers involved (stacked powers of 2, if memory serves) quickly get beyond the point of comprehension, let alone storage. A BigInteger can store a Googol, but not a Googolplex; and Ackermann will quickly take you beyond that.

Perhaps something more grounded in reality might be better; or alternatively, write a program that prints out what it will need to do (or at least the first few "stacks") to calculate the value.

HIH

Winston
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you're interested in playing around with how fast recursion slows down computation, maybe start with Fibonacci numbers. The recursive implementation "only" grows exponentially, so it doesn't go out of bounds quite so quickly. But it does slow down noticeably.
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The naïve version of Fibonacci runs in O(1.608ⁿ) time, so it is easy to follow with a watch. There are other versions which run in linear time and Kaldewaaij has a recursive version which runs in logarithmic complexity.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!