### Author Topic: Ackermann function revised  (Read 1141 times)

0 Members and 1 Guest are viewing this topic.

#### Arnold

• Hero Member
•     • Posts: 977 ##### Ackermann function revised
« on: February 19, 2020, 08:12:25 am »
Hi Charles,

I found some interesting implementations of the Ackermann function. Creating the function with 3 recursive calls seems to be very exhaustive to the stack, direct computing for m<4 seems to save resources and calculates higher values:

ackermann2.o2bas:
Code: [Select]
`' http://largeint.sourceforge.net/Ackerman.htmuses consoleint c,s,dsub init_counts()   c=0 : s=0 : d=1end sub' Naive implementation with three recursive calls:function A (int m, n) as int   c = c + 1   s = s + 1   if s > d then d = s   if m = 0 then      function = n + 1   elseif n = 0 then      function = A(m - 1, 1)   else      function = A(m - 1, A(m, n - 1))   end if   s = s - 1end functioninit_counts() : printl "Ackermann function A(m,n) - three recursive calls"init_counts() : printl "A(3, 7) = " : print A(3,7)  tab " calls: " c " depth: " d '1021init_counts() : printl "A(3,12) = " : print A(3,12) tab " calls: " c " depth: " d '32765; A(3,13) -> stack overflowinit_counts() : printl "A(4, 0) = " : print A(4,0)  tab " calls: " c " depth: " d '13; A(4,1) -> stack overflow' Cheat - direct computation for m < 4function A (int m, n) as quad   c++   s++   if s > d then d = s      select case m      case 0         function = n + 1      case 1         function = n + 2      case 2         function = 2 * n + 3      case 3         function = 2 ^ (n + 3) - 3      case else         if n = 0 then            function = A(m - 1, 1)         else            function = A(m - 1, A(m, n - 1))         end if      end select   s--end functionprintlinit_counts() : printl "Ackermann function A(m,n) - direct computation for m < 4 "init_counts() : printl "A(3, 7) = " : print A(3,7)  tab " calls: " c " depth: " d '1021init_counts() : printl "A(3,12) = " : print A(3,12) tab " calls: " c " depth: " d '32765; A(3,13) -> stack overflowinit_counts() : printl "A(4, 0) = " : print A(4,0)  tab " calls: " c " depth: " d '13; A(4,1) -> stack overflowprintlinit_counts() : printl "A(3,20) = " : print A(3,20) tab " calls: " c " depth: " d '8388605init_counts() : printl "A(3,30) = " : print A(3,30) tab " calls: " c " depth: " d '858934589init_counts() : printl "A(4, 1) = " : print A(4, 1) tab tab " calls: " c " depth: " d '65533; A(4,2) too much -> 19729 digitsinit_counts() : printl "A(5, 0) = " : print A(4, 1) tab tab " calls: " c " depth: " d '65533; A(5,1) wrong resultprintl "Enter ..."waitkey`
How would you code the second approach in Leanlisp? I noticed that you already have done the first approach in examples/math/Ackermann.o2bas, but somehow print (ack 3 7) does not work for me. What did I do wrong?

Roland

ackerLean.o2bas:
Code: [Select]
`% UseSystemConsoleuses Consoleuses LispishUtilstring src=quote """( let ack " m n  (if (> m 0 )    (if (> n 0)      (eval        (decr m)        (decr n)        (let t (ack n 1))        (ack m t)      )      ;else n=0      (eval        (decr m)        (ack m 1)      )    )    ;else m=0    (+ n 1)  ) ;end if m>0")print (ack 3 7)"""string s=lisp srcprintl "Enter"waitkey`
« Last Edit: February 20, 2020, 08:45:17 am by Arnold »

#### Arnold

• Hero Member
•     • Posts: 977 ##### Re: Ackermann function revised
« Reply #1 on: February 20, 2020, 08:48:19 am »
There was a small bug in ackermann2.o2bas. I forgot to initialize the auxiliary values for c, s, d before calling the Ackermann function. I have replaced the code of ackermann2.o2bas above.

#### Arnold

• Hero Member
•     • Posts: 977 ##### Re: Ackermann function revised
« Reply #2 on: February 21, 2020, 12:57:36 am »
This is the table of values for the Ackermann function. I found it interesting to see many recursive implementations of this function which will exceed the capacities of at least the home computers very quickly.

Ackermann3.o2bas:
Code: [Select]
`' http://largeint.sourceforge.net/Ackerman.htm' https://en.wikipedia.org/wiki/Ackermann_functionuses consolefunction A (int m, n) as quad      select case m      case 0         function = n + 1      case 1         function = n + 2      case 2         function = 2 * n + 3      case 3         function = 2 ^ (n + 3) - 3      case else         if n = 0 then            function = A(m - 1, 1)         else            function = A(m - 1, A(m, n - 1))         end if      end selectend functionint x, r, cstring line = string(64, "-")clsprint "Ackermann function A(m,n)" + cr + crprint  "   n|   "printl "m   |   "for x = 0 to 5 : print x tab : next : print xprintl linefor r = 0 to 5   printl r "   |   "   for c = 0 to 6      if r=4 and c=2 then print "too big" : exit for      if r=5 and c=1 then print "too big" : exit for        print A(r,c) tab   nextnextprintlprintl "Enter ..."waitkey`

#### jack

• Full Member
•   • Posts: 160 ##### Re: Ackermann function revised
« Reply #3 on: February 21, 2020, 06:37:51 am »
interesting links Arnold, as I understand, the Ackermann function was concocted to stress-test recursion, right?

#### Arnold

• Hero Member
•     • Posts: 977 ##### Re: Ackermann function revised
« Reply #4 on: February 21, 2020, 12:45:24 pm »
Hi Jack,

yes it is a very stressy test, in particular if using three recursive calls. It demonstrated that my computer runs out of air very quickly, no matter which language I use, even with 8 GB of RAM.

#### Charles Pegge

• Admin Support Member
•     • Posts: 4486 ##### Re: Ackermann function revised
« Reply #5 on: February 22, 2020, 03:30:21 am »
Thanks Roland,

I will include the Ackermanns in examples/Math.

I have forgotten how to use LeanLisp but I will add cond to emulate if ... elseif ... else