Ackermann

[Dutchman]

I have made a test- and demo-program for the Ackermaan-function.
That function is often used used as a benchmark of a compiler's ability to optimize recursion.
See also http://en.m.wikipedia.org/wiki/Ackermann_function
Due to the deep recursion, Smart Basic will crash for higher values.
E.g it crashes at calculating the values of A(3,10) and A(4,1) on iPad Air and iOS 8.3
The calculation of A(3,9) took 386 seconds after 1.11644E+07 function calls in recursion.
Incredibly deep! Well done Mr. K
The values are written to file until the app crashes.
Screenshots of the running program and the file "Ackkermann(3,n).txt" are attached.
In the editor in the section marked in red the value of m should be changed for generating different files.

Code: Select all

'Ackermann for Smart Basic
'Test and demo-program for Ackkermann-function
'by Dutchman, may 2015
/*
The Ackermann function is a classic example of a recursive function.
It grows very quickly in value, as does the size of its call tree.
Its arguments are never negative and it always terminates.
See also: http://en.m.wikipedia.org/wiki/Ackermann_function
The Ackermann function, due to its definition in terms of extremely deep recursion,
can be used as a benchmark of a compiler's ability to optimize recursion.
*/
SET UNDERGROUND ON ' keep calculating in background
TIME RESET
PRINT "Ackermann-function A(m,n)"
PRINT
'GOTO Crashrun 'decomment to skip first section
'------- make 4x7 (mxn) table
PRINT "The first 4x7 Ackermann's numbers:"
FOR m=0 TO 3
  FOR n=0 TO 6
    count=0
    t=TIME()
    PRINT "####":A(m,n); 
    t=TIME()-t
  NEXT n
PRINT
NEXT m
PRINT "Last number ";
GOSUB stats
PRINT
'
crashrun:
'r'--- calculate A(mfixed,n)
'----- and store result in file until crash
m=3 'value for which a series will be calculated
''
m$=STR$(m,"#")
n=0 'startvalue until crash
File$="Ackermann("&m$&",n).txt"
IF FILE_EXISTS(File$) THEN FILE File$ DELETE
FILE File$ PRINT "Function","Value","Runtime","Function calls"
DO
  n$=STR$(n,"#")
  count=0
  t=TIME()
  PRINT "A(";m$;",";n$;")";
  Amn=A(m,n)
  t=TIME()-t
  PRINT "=";Amn;
  GOSUB Stats
  GOSUB Store
  PRINT
  n+=1
UNTIL crash
END
'
'===== Functions and Subroutines =====
DEF A(m,n)'Ackermann-function
REM m and n should be positive integers
.count+=1 'comment this out for a bit higher speed
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
'
Store:
  FILE File$ PRINT "A("&m$&","&n$&")",Amn,F$:t,count
RETURN
'
Stats:
IF t>0.1 THEN ! F$="#.#" ! ELSE ! F$="#.###"
ENDIF
PRINT "in ";F$:t;"seconds";
'print count if it is not commented out
IF count>0 THEN 
  PRINT " and";count;"function calls."
ELSE
  PRINT "."
ENDIF
RETURN

Display during program run

Ackermann run.PNG (150.86 KiB) Viewed 1392 times

Content of output file with m=3 in crashrun

Ackermann(3,n).PNG (129.56 KiB) Viewed 1392 times

[Mr. Kibernetik]

Thank you very much, Ton, for a test!

This is the result of my testing on iPad Air 2:

IMG_0161.jpg (69.78 KiB) Viewed 1383 times

[Dutchman]

The number of function calls is not a measure for the depth of the recursive function calls.
Therefore I made the following code, which determines the depth of the recursion.

Code: Select all

'Ackermann depth
'by Dutchman, May 2015
'program for Smart Basic
'calculates depth of recursion
'r''change parameters for other runs
m=3 ! maxn=9
''
FOR n=0 TO maxn
  depth=1
  maxdepth=0
  A.in$=""
  Amn=A(m,n) 
  PRINT "#":Amn,"Depth=";"#":maxdepth
NEXT n
END
'
DEF A(m,n)'Ackermann-function
REM m and n should be positive integers
IF in$="" THEN
  in$="A("&m&","&n&")"
  PRINT in$;"=";
ENDIF
IF m=0 THEN
  .depth-=1
  RETURN n+1 'recursion depth is reduced
ENDIF
IF n=0 THEN RETURN A(m-1,1) 'call to A(m,0) is replaced by A(m-1,1)
'next the recursion depth is increased:
'extra function call 'A(m,n-1)' is added to depth
.depth+=1
.maxdepth=MAX(.depth,.maxdepth)
RETURN A(m-1,A(m,n-1))
END DEF

The following screenshot gives the result for A(3,0) to A(3,9)

Ackermann depth of recursion

Ackermann depth.PNG (121.96 KiB) Viewed 1359 times

Obviously the depth of recursion is equal to the output of the function minus 1.
In order to understand that, I made the following code which displays the nested functions during each function call in the execution.

Code: Select all

'Ackermann nesting
' by Dutchman May 2015
'program for Smart Basic
'displays successive nested function calls
OPTION BASE 1
PRINT A(2,2)
END

DEF A(m,n)'Ackermann-function
REM m and n should be positive integers
in$="A("&m&","&n&")"
IF .s$="" THEN .s$=in$
PRINT .s$
start=INSTR(.s$,in$,1)
IF m=0 THEN
  new$=n+1
  GOSUB Replace
  RETURN n+1
ENDIF
IF n=0 THEN
  new$="A("&(m-1)&","&(n+1)&")"
  GOSUB Replace
  RETURN A(m-1,1)
ENDIF
new$="A("&(m-1)&",A("&m&","&(n-1)&"))"
  GOSUB Replace
RETURN A(m-1,A(m,n-1))
Replace:
  .s$=MID$(.s$,start,LEN(in$),new$)
RETURN
END DEF

The output for the function A(2,2) is given in the following screenshot.

Ackermann function nesting during execution

Ackermann nesting.png (114.24 KiB) Viewed 1359 times

I have added (in red) some annotations which explain the direct relation between function result and depth of recursion.

Congratulations to Mr. K. that Smart Basic can handle recursion to more than 8000 nested function calls.

[Mr. Kibernetik]

Congratulations to Mr. K. that Smart Basic can handle recursion to more than 8000 nested function calls.

Thank you for the test!
If you want to check just function recursion depth then it is much deeper:

Code: Select all

1 n+=10000
TIME RESET
PRINT f(n),TIME()
GOTO 1

DEF f(n)
IF n=0 THEN RETURN 0
f=f(n-1)+1
ENDDEF