$SPAD/src/input ackermann.input

Timothy Daly December 3, 2016

Abstract

Contents

2

— * —

)set break resume
)spool ackermann.output
)set message test on
)set message auto off
)clear all
)set message time on
--S 1 of 23
ackerslow(m:INT,n:INT):INT ==
  m = 0 => n+1
  (m>0 and n=0) => ackerslow(m-1,1)
  ackerslow(m-1,ackerslow(m,n-1))
--R
--R   Function declaration ackerslow : (Integer,Integer) -> Integer has
--R      been added to workspace.
--R                                                                   Type: Void
--I                                                                  Time: 0 sec
--E 1
--S 2 of 23
ackerslow(0,0)
--R
--R   Compiling function ackerslow with type (Integer,Integer) -> Integer
--R
--R   (2)  1
--R                                                        Type: PositiveInteger
--I                                                   Time: 0.01 (OT) = 0.01 sec
--E 2
--S 3 of 23
cache:Table(List Integer,Integer):=empty()
--R
--R
--R   (3)  table()
--R                                           Type: Table(List(Integer),Integer)
--I                                                   Time: 0.01 (OT) = 0.01 sec
--E 3
--S 4 of 23
ackermann(m:INT,n:INT):INT ==
  index?((m,n),cache) =>
    qelt(cache,(m,n))
  m = 0 =>
    qsetelt!(cache,(m,n),n+1)
    n+1
  (m>0 and n=0) =>

   result:INT:=ackermann(m-1,1)
   qsetelt!(cache,(m-1,1),result)
   result
  resultinner:INT:=ackermann(m,n-1)
  qsetelt!(cache,(m,n-1),resultinner)
  result:INT:=ackermann(m-1,resultinner)
  qsetelt!(cache,(m-1,resultinner),result)
--R
--R   Function declaration ackermann : (Integer,Integer) -> Integer has
--R      been added to workspace.
--R                                                                   Type: Void
--I                                                                  Time: 0 sec
--E 4
--S 5 of 23
ackermann(0,0)
--R
--R   Compiling function ackermann with type (Integer,Integer) -> Integer
--R
--R   (5)  1
--R                                                        Type: PositiveInteger
--I                                                   Time: 0.01 (OT) = 0.01 sec
--E 5
--S 6 of 23
[ackerslow(3,i) for i in 0..10]
--R
--R
--R   (6)  [5,13,29,61,125,253,509,1021,2045,4093,8189]
--R                                                          Type: List(Integer)
--I                                       Time: 7.03 (EV) + 0.28 (GC) = 7.31 sec
--E 6
--S 7 of 23
[ackerslow(3,i) for i in 0..10]
--R
--R
--R   (7)  [5,13,29,61,125,253,509,1021,2045,4093,8189]
--R                                                          Type: List(Integer)
--I                                       Time: 7.03 (EV) + 0.21 (GC) = 7.24 sec
--E 7
--S 8 of 23
[ackermann(3,i) for i in 0..10]
--R
--R
--R   (8)  [5,13,29,61,125,253,509,1021,2045,4093,8189]
--R                                                          Type: List(Integer)
--I                         Time: 0.11 (IN) + 15.32 (EV) + 0.03 (GC) = 15.46 sec
--E 8

--S 9 of 23
[ackermann(3,i) for i in 0..10]
--R
--R
--R   (9)  [5,13,29,61,125,253,509,1021,2045,4093,8189]
--R                                                          Type: List(Integer)
--I                                                   Time: 0.02 (EV) = 0.02 sec
--E 9
--S 10 of 23
)set function cache all
--R
--R   In general, interpreter functions will cache all values.
--E 10
--S 11 of 23
ackerslow(3,0)
--R
--R
--R   (10)  5
--R                                                        Type: PositiveInteger
--I                                                                  Time: 0 sec
--E 11
--S 12 of 23
ackerslow(3,1)
--R
--R
--R   (11)  13
--R                                                        Type: PositiveInteger
--I                                                                  Time: 0 sec
--E 12
--S 13 of 23
ackerslow(3,2)
--R
--R
--R   (12)  29
--R                                                        Type: PositiveInteger
--I                                                                  Time: 0 sec
--E 13
--S 14 of 23
ackerslow(3,3)
--R
--R
--R   (13)  61
--R                                                        Type: PositiveInteger
--I                                                                  Time: 0 sec

--E 14
--S 15 of 23
ackerslow(3,4)
--R
--R
--R   (14)  125
--R                                                        Type: PositiveInteger
--I                                                                  Time: 0 sec
--E 15
--S 16 of 23
ackerslow(3,5)
--R
--R
--R   (15)  253
--R                                                        Type: PositiveInteger
--I                                                   Time: 0.01 (EV) = 0.01 sec
--E 16
--S 17 of 23
ackerslow(3,6)
--R
--R
--R   (16)  509
--R                                                        Type: PositiveInteger
--I                                                   Time: 0.02 (EV) = 0.02 sec
--E 17
--S 18 of 23
ackerslow(3,7)
--R
--R
--R   (17)  1021
--R                                                        Type: PositiveInteger
--I                                                   Time: 0.07 (EV) = 0.07 sec
--E 18
--S 19 of 23
ackerslow(3,8)
--R
--R
--R   (18)  2045
--R                                                        Type: PositiveInteger
--I                                                   Time: 0.30 (EV) = 0.30 sec
--E 19
--S 20 of 23
ackerslow(3,9)
--R

--R
--R   (19)  4093
--R                                                        Type: PositiveInteger
--I                                       Time: 1.26 (EV) + 0.04 (GC) = 1.30 sec
--E 20
--S 21 of 23
ackerslow(3,10)
--R
--R
--R   (20)  8189
--R                                                        Type: PositiveInteger
--I                                       Time: 5.22 (EV) + 0.19 (GC) = 5.41 sec
--E 21
--S 22 of 23
[ackerslow(3,i) for i in 0..10]
--R
--R
--R   (21)  [5,13,29,61,125,253,509,1021,2045,4093,8189]
--R                                                          Type: List(Integer)
--I                                       Time: 7.01 (EV) + 0.26 (GC) = 7.27 sec
--E 22
--S 23 of 23
[ackerslow(3,i) for i in 0..10]
--R
--R
--R   (22)  [5,13,29,61,125,253,509,1021,2045,4093,8189]
--R                                                          Type: List(Integer)
--I                                       Time: 7.00 (EV) + 0.27 (GC) = 7.27 sec
--E 23
)spool
)lisp (bye)

———-

References^{[1] nothing}

8