Ackermann function

For finished programs
Post Reply
User avatar
Dutchman
Posts: 151
Joined: Tue Aug 06, 2019 4:47 pm
Location: Netherlands

Ackermann function

Post by Dutchman » Wed Sep 11, 2019 1:25 pm

The Ackermann function is a well-known function for implementing and testing recursive processing.
The function is discussed in detail in https://en.wikipedia.org/wiki/Ackermann_function
and in https://bit.ly/2lJNSaQ
An animation of memory usage can be seen on http://www.gfredericks.com/sandbox/arith/ackermann

Code: Select all

'Ackermann function
'by "Dutchman" Ton Nillesen, september 2019
'See https://en.wikipedia.org/wiki/Ackermann_function
'    and https://bit.ly/2lJNSaQ
'animated: http://www.gfredericks.com/sandbox/arith/ackermann
'
'----Function parameters
m=3 ' static parameter
n=0 ' start value dynamic parameter
'
'--- Run
OPTION TAB 13,10
TIMER SET
PRINT "Ackermann function"
PRINT "  Run time","Function"," Depth"
Do
  Amn=A(m,n) ' result is equal to the depth
  PRINT Time1$(TIMER GET, 13)\
       ," A("+(STRTEXT m)+","+(STRTEXT n)+")=",Amn
n+=1
REDO
END
'
'=========== Functions ===========
DEF A(m,n)'Ackermann-function
REM m and n should be >=0
IF m=0 THEN RETURN n+1
IF n=0 THEN RETURN A(m-1,1) 
RETURN A(m-1,A(m,n-1))
END DEF
'
DEF Time1$(seconds,width)
'returns time string with hours, minutes, seconds
'in format h:mm'ss"
'width determines minimum width of string
'width has only effect if >10
IF width>10 THEN F$=STRREP "?",width-10 ELSE F$=""
hours=INT(seconds/3600)
mins=INT((seconds-hours*3600)/60)
secs=seconds-hours*3600-mins*60
T$=STRTEXT(hours f$+"0:")+STRTEXT(mins "00'")+STRTEXT(secs "00""")
RETURN t$
END DEF
A run over several hours gave the following output.
It is clear that BestBASIC has no trouble with a recursion depth of more than 260K.
During the aborted calculation of A (3.16), the amount of memory was viewed with the Activity app.
It clearly shows that BestBASIC can handle hundreds of megabytes of memory.
.
Ackermann function output and memory usage.PNG
Ackermann function output and memory usage.PNG (108.84 KiB) Viewed 584 times
It is still a long way to go

Post Reply