Forums Register Login

Ackermann function

+Pie Number of slices to send: Send
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.




+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.
(1 cow)
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.
We can walk to school together. And we can both read this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 2731 times.
Similar Threads
BigInteger Power/Exponent BigInteger
Card Shuffle Problem
Error states: This method must return a result of type int
Finding primitive polynomials
Fibonacci Algorithms and their different manifestations. Which is the best?
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 09:59:36.