Oxygen Basic
Programming => Example Code => General => Topic started by: Arnold 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:
' 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:
% 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
-
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.
-
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:
' 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
-
interesting links Arnold, as I understand, the Ackermann function was concocted to stress-test recursion, right?
-
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.
-
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