Ackermann function revised

[Arnold]

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.htm

uses console

int c,s,d
sub init_counts()
   c=0 : s=0 : d=1
end 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 - 1
end function

init_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 '1021
init_counts() : printl "A(3,12) = " : print A(3,12) tab " calls: " c " depth: " d '32765; A(3,13) -> stack overflow
init_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 < 4
function 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 function

printl
init_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 '1021
init_counts() : printl "A(3,12) = " : print A(3,12) tab " calls: " c " depth: " d '32765; A(3,13) -> stack overflow
init_counts() : printl "A(4, 0) = " : print A(4,0)  tab " calls: " c " depth: " d '13; A(4,1) -> stack overflow
printl
init_counts() : printl "A(3,20) = " : print A(3,20) tab " calls: " c " depth: " d '8388605
init_counts() : printl "A(3,30) = " : print A(3,30) tab " calls: " c " depth: " d '858934589
init_counts() : printl "A(4, 1) = " : print A(4, 1) tab tab " calls: " c " depth: " d '65533; A(4,2) too much -> 19729 digits
init_counts() : printl "A(5, 0) = " : print A(4, 1) tab tab " calls: " c " depth: " d '65533; A(5,1) wrong result


printl "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]

% UseSystemConsole
uses Console
uses LispishUtil

string 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 src

printl "Enter"
waitkey


[Arnold]

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]

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_function

uses console

function 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 select
end function

int x, r, c
string line = string(64, "-")

cls
print "Ackermann function A(m,n)" + cr + cr
print  "   n|   "
printl "m   |   "
for x = 0 to 5 : print x tab : next : print x
printl line
for 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
   next
next

printl
printl "Enter ..."
waitkey


[jack]

interesting links Arnold, as I understand, the Ackermann function was concocted to stress-test recursion, right?

[Arnold]

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]

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