Essays/Memo

A demonstration of the efficacy of memoization.

comb0 is the classical doubly recursion definition found in Gilman and Rose; combm is the same thing with M. applied; comb is from the for. page of the dictionary and has been worked on for more than 30 years by myself and others.

comb0=: 4 : 0   NB. All size x combinations of i.y
 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb0&.<: y),1+x comb0 y-1 end.
)

combm=: 4 : 0 M.
 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combm&.<: y),1+x combm y-1 end.
)

comb=: 4 : 0
 k=. i.>:d=.y-x
 z=. (d$<i.0 0),<i.1 0
 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
 ; z
)

The benchmark is 10 comb 20 .

	time	space
comb0	4.04831	25169088
combm	0.16492	44554944
comb	0.159853	24965312

Thus, combm is a straightforward definition which is competitive in time and space with the highly polished comb .

combm1 is like combm but captures the arguments in cases where the body of the verb is evaluated with arguments.  combm1 can be called multiple times with some of these arguments, but all but the first call is intercepted by the M. mechanism and the result computed by table look-up.

foo=: 0 2$0

combm1=: 4 : 0 M.
 foo=: foo,x,y
 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combm1&.<: y),1+x combm1 y-1 end.
)

   $ 10 combm1 20
184756 10

   $ foo
123 2

   _20 <\ ": foo
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│10 20│ 5  5│ 9 12│ 9 14│ 1  6│ 2 10│ 2 12│
│10 19│ 4  5│ 8 11│ 8 13│ 1  7│ 1  9│ 1 11│
│10 18│ 4  4│ 7 10│ 7 12│ 0  6│ 0  8│ 0 10│
│10 17│ 3  4│ 6  9│ 6 11│ 9 16│ 9 18│     │
│10 16│ 3  3│ 5  8│ 5 10│ 8 15│ 8 17│     │
│10 15│ 2  3│ 4  7│ 4  9│ 7 14│ 7 16│     │
│10 14│ 2  2│ 3  6│ 3  8│ 6 13│ 6 15│     │
│10 13│ 1  2│ 2  5│ 2  7│ 5 12│ 5 14│     │
│10 12│ 1  1│ 1  4│ 1  6│ 4 11│ 4 13│     │
│10 11│ 0  1│ 0  3│ 0  5│ 3 10│ 3 12│     │
│10 10│ 9 11│ 9 13│ 9 15│ 2  9│ 2 11│     │
│ 9 10│ 8 10│ 8 12│ 8 14│ 1  8│ 1 10│     │
│ 9  9│ 7  9│ 7 11│ 7 13│ 0  7│ 0  9│     │
│ 8  9│ 6  8│ 6 10│ 6 12│ 9 17│ 9 19│     │
│ 8  8│ 5  7│ 5  9│ 5 11│ 8 16│ 8 18│     │
│ 7  8│ 4  6│ 4  8│ 4 10│ 7 15│ 7 17│     │
│ 7  7│ 3  5│ 3  7│ 3  9│ 6 14│ 6 16│     │
│ 6  7│ 2  4│ 2  6│ 2  8│ 5 13│ 5 15│     │
│ 6  6│ 1  3│ 1  5│ 2  7│ 4 12│ 4 14│     │
│ 5  6│ 0  2│ 0  4│ 2  6│ 3 11│ 3 13│     │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┘

---

Contributed by Roger Hui.