Support Forum / Форум поддержки

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

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

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

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