**Abstract**

Some functions are simply stated and easily understood as multiply-recursive functions. For example, the Fibonacci numbers are `{1≥⍵:⍵ ⋄ (∇ ⍵-2)+∇ ⍵-1}`

. A drawback of multiple recursion is abysmal performance even for moderate-sized arguments, consequently motivating resorts to circumlocutions. The memo operator addresses the performance problem and restores multiple recursion to the toolkit of thought. We present a memo operator modelled as a 6-line d-operator.

`⎕io←0`

throughout.

*The Man Who Knew Infinity*

Jay sent out an e-mail asking who would be interested to go see the film *The Man Who Knew Infinity*. Fiona’s response: “Ah, Mr. 1729; I’m in.” John was game, and so was I.

**The Number of Partitions**

Nick found an essay by Stephen Wolfram on Ramanujan written on occasion of the film, wherein Wolfram said:

A notable paper [Ramanujan] wrote with Hardy concerns the partition function (`PartitionsP`

in the Wolfram Language) that counts the number of ways an integer can be written as a sum of positive integers. …

In Ramanujan’s day, computing the exact value of `PartitionsP[200]`

was a big deal — and the climax of his paper. But now, thanks to Ramanujan’s method, it’s instantaneous:

```
In[1]:= PartitionsP[200]
Out[1]= 3 972 999 029 388
```

A *partition* of a non-negative integer `n`

is a vector `v`

of positive integers such that `n = +/v`

, where the order in `v`

is not significant. For example, the partitions of the first seven non-negative integers are:

```
┌┐
││
└┘
┌─┐
│1│
└─┘
┌─┬───┐
│2│1 1│
└─┴───┘
┌─┬───┬─────┐
│3│2 1│1 1 1│
└─┴───┴─────┘
┌─┬───┬───┬─────┬───────┐
│4│3 1│2 2│2 1 1│1 1 1 1│
└─┴───┴───┴─────┴───────┘
┌─┬───┬───┬─────┬─────┬───────┬─────────┐
│5│4 1│3 2│3 1 1│2 2 1│2 1 1 1│1 1 1 1 1│
└─┴───┴───┴─────┴─────┴───────┴─────────┘
┌─┬───┬───┬─────┬───┬─────┬───────┬─────┬───────┬─────────┬───────────┐
│6│5 1│4 2│4 1 1│3 3│3 2 1│3 1 1 1│2 2 2│2 2 1 1│2 1 1 1 1│1 1 1 1 1 1│
└─┴───┴───┴─────┴───┴─────┴───────┴─────┴───────┴─────────┴───────────┘
```

Can we compute the partition counting function “instantaneously” in APL?

We will use a recurrence relation derived from the pentagonal number theorem, proved by Euler more than 160 years before Hardy and Ramanujan:

equation (11) in http://mathworld.wolfram.com/PartitionFunctionP.html. In APL:

```
pn ← {0≥⍵:0=⍵ ⋄ -/+⌿∇¨rec ⍵}
rec ← {⍵ - (÷∘2 (×⍤1) ¯1 1 ∘.+ 3∘×) 1+⍳⌈0.5*⍨⍵×2÷3}
pn¨0 1 2 3 4 5 6
1 1 2 3 5 7 11
pn 30
5604
```

Warning: don’t try `pn 200`

because that would take a while! Why? `pn 200`

would engender `pn`

being applied to each element of `rec 200`

and:

```
rec 200
199 195 188 178 165 149 130 108 83 55 24 ¯10
198 193 185 174 160 143 123 100 74 45 13 ¯22
```

Each of the non-negative values would itself engender further recursive applications.

**A Memo Operator**

I recalled from J the *memo* adverb (monadic operator) `M`

. Paraphrasing the J dictionary: `f M`

is the same as `f`

but may keep a record of the arguments and results for reuse. It is commonly used for multiply-recursive functions. Sounds like just the ticket!

The functionistas had previously implemented a (dyadic) memo operator. The version here is more restrictive but simpler. The restrictions are as follows:

- The cache is constructed “on the fly” and is discarded once the operand finishes execution.
- The operand is a dfn
`{condition:basis ⋄ expression}`

where none of`condition`

,`base`

and`expression`

contain a`⋄`

and recursion is denoted by`∇`

in`expression`

- The arguments are scalar integers.
- The operand function does not have
`¯1`

as a result. - A recursive call is on a smaller integer.

With these restrictions, our memo operator can be defined as follows:

```
M←{
f←⍺⍺
i←2+'⋄'⍳⍨t←3↓,⎕CR'f'
0=⎕NC'⍺':⍎' {T←(1+ ⍵)⍴¯1 ⋄ {',(i↑t),'¯1≢T[⍵] :⊃T[⍵] ⋄ ⊃T[⍵] ←⊂',(i↓t),'⍵}⍵'
⍎'⍺{T←(1+⍺,⍵)⍴¯1 ⋄ ⍺{',(i↑t),'¯1≢T[⍺;⍵]:⊃T[⍺;⍵] ⋄ ⊃T[⍺;⍵]←⊂',(i↓t),'⍵}⍵'
}
pn M 10
42
pn 10
42
```

Obviously, the `⍎`

lines in `M`

are crucial. When the operand is `pn`

, the expression which is executed is as follows; the characters inserted by `M`

are shown in red.

{T←(1+⍵)⍴¯1 ⋄ {0≥⍵:0=⍵ ⋄ ¯1≢T[⍵]:⊃T[⍵] ⋄ ⊃T[⍵]←⊂-/+⌿∇¨rec ⍵}⍵}⍵

The machinations produce a worthwhile performance improvement:

```
pn M 30
5604
cmpx 'pn M 30'
3.94E¯4
cmpx 'pn 30'
4.49E1
4.49e1 ÷ 3.94e¯4
113959
```

That is, `pn M 30`

is faster than `pn 30`

by a factor of 114 thousand.

Can APL compute `pn M 200`

“instantaneously”? Yes it can, for a suitable definition of “instantaneous”.

```
cmpx 'm←pn M 200'
4.47E¯3
m
3.973E12
0⍕m
3972999029388
```

`M`

also works on operands which are anonymous, dyadic, or have non-scalar results.

**Fibonacci Numbers**

```
fib←{1≥⍵:⍵ ⋄ (∇ ⍵-2)+∇ ⍵-1}
fib¨ ⍳15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
fib M¨ ⍳15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
cmpx 'fib 30'
1.45E0
cmpx 'fib M 30'
1.08E¯4
```

Anonymous function:

```
{1≥⍵:⍵ ⋄ (∇ ⍵-2)+∇ ⍵-1}M¨ ⍳15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
```

**Combinations**

`⍺ comb ⍵`

produces a matrix of all the size-`⍺`

combinations of `⍳⍵`

. The algorithm is from the venerable *APL: An Interactive Approach* by Gilman and Rose.

```
comb←{(⍺≥⍵)∨0=⍺:((⍺≤⍵),⍺)⍴⍳⍺ ⋄ (0,1+(⍺-1)∇ ⍵-1)⍪1+⍺ ∇ ⍵-1}
3 comb 5
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
3 (comb ≡ comb M) 5
1
cmpx '8 comb M 16' '8 comb 16'
8 comb M 16 → 1.00E¯3 | 0% ⎕
8 comb 16 → 3.63E¯2 | +3526% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

A faster `comb`

is possible without a memo operator, but it’s not easy. (See for example section 4.1 of my APL87 paper.) A memo operator addresses the performance problem with multiple recursion and restores it to the toolkit of thought.

*Presented at the BAA seminar at the Royal Society of Arts on 2016-05-20*

Nice article!

Users should, however, ensure that IO is set to zero. The function M also seems to have a typo that generates a SYNTAX ERROR; namely, the curly brace in the first occurrence of “{‘,(i take t),” should be omitted.

Thank you for presenting an efficient use of the memo operator!

Thank you for your comments.

⎕io←0 is assumed in the article. I myself use 0-origin as a matter of course and “forgot” to state the assumption in the article. I will rectify this soon.

The d-operator M is correct as stated in the article. There _are_ imbalances in { and } the text of the two ⍎ lines, but the variable t (3↓,⎕cr ‘f’) itself has one extra }. I pasted the definition of M from the article into an APL session and it runs as intended, without a syntax error.