• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Ackermann function

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.




 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic