76 lines
1.3 KiB
Plaintext
76 lines
1.3 KiB
Plaintext
\ Ackermann function, illustrating use of "memoization".
|
|
|
|
\ Memoization is a technique whereby intermediate computed values are stored
|
|
\ away against later need. It is particularly valuable when calculating those
|
|
\ values is time or resource intensive, as with the Ackermann function.
|
|
|
|
\ make the stack much bigger so this can complete!
|
|
100000 stack-size
|
|
|
|
\ This is where memoized values are stored:
|
|
{} var, dict
|
|
|
|
\ Simple accessor words
|
|
: dict! \ "key" val --
|
|
dict @ -rot m:! drop ;
|
|
|
|
: dict@ \ "key" -- val
|
|
dict @ swap m:@ nip ;
|
|
|
|
defer: ack1
|
|
|
|
\ We just jam the string representation of the two numbers together for a key:
|
|
: makeKey \ m n -- m n key
|
|
2dup >s swap >s s:+ ;
|
|
|
|
: ack2 \ m n -- A
|
|
makeKey dup
|
|
dict@ null?
|
|
if \ can't find key in dict
|
|
\ m n key null
|
|
drop \ m n key
|
|
-rot \ key m n
|
|
ack1 \ key A
|
|
tuck \ A key A
|
|
dict! \ A
|
|
else \ found value
|
|
\ m n key value
|
|
>r drop 2drop r>
|
|
then ;
|
|
|
|
: ack \ m n -- A
|
|
over not
|
|
if
|
|
nip n:1+
|
|
else
|
|
dup not
|
|
if
|
|
drop n:1- 1 ack2
|
|
else
|
|
over swap n:1- ack2
|
|
swap n:1- swap ack2
|
|
then
|
|
then ;
|
|
|
|
' ack is ack1
|
|
|
|
: ackOf \ m n --
|
|
2dup
|
|
"Ack(" . swap . ", " . . ") = " . ack . cr ;
|
|
|
|
|
|
0 0 ackOf
|
|
0 4 ackOf
|
|
1 0 ackOf
|
|
1 1 ackOf
|
|
2 1 ackOf
|
|
2 2 ackOf
|
|
3 1 ackOf
|
|
3 3 ackOf
|
|
4 0 ackOf
|
|
|
|
\ this last requires a very large data stack. So start 8th with a parameter '-k 100000'
|
|
4 1 ackOf
|
|
|
|
bye
|