exupero's blog

Stack-based mental math

Proficiency in mental math relies on different skills than we're taught for math in elementary school. Elementary school math usually depends on paper-based algorithms, which are memory hungry to improve calculation speed, while mental math algorithms tend to choose the alternative and reduce the amount of memory needed even at the cost of slower calculation.

Realizing this, I began to think of mental math algorithms as reducing a list of operations over a small set of data. The small set of data fits in human working memory, while the list of operations, which doesn't change, is stored in long-term memory.

For example, converting 45 degrees Celsius to Fahrenheit can be done as a reduction of three functions:

``````(reduce
(fn [data f]
(f data))
45
[#(* % 9)
#(/ % 5)
#(+ % 32)])``````
``````113
``````

This is, in essence, stack-based programming. Here's the same algorithm but using a stack of values rather than a single value:

``````(reduce
(fn [stack op]
(op stack))
[45]
[(fn [stack]
(conj (pop stack)
(* (peek stack) 9)))
(fn [stack]
(conj (pop stack)
(/ (peek stack) 5)))
(fn [stack]
(conj (pop stack)
(+ (peek stack) 32)))])``````
``````[113]
``````

More properly, we should move the 9, 5, and 32 onto the stack rather than embedding them within the operations:

``````(reduce
(fn [stack op]
(op stack))
[45]
[#(conj % 9)
(fn [stack]
(let [a (peek (pop stack))
b (peek stack)]
(conj (pop (pop stack))
(* a b))))
#(conj % 5)
(fn [stack]
(let [a (peek (pop stack))
b (peek stack)]
(conj (pop (pop stack))
(/ a b))))
#(conj % 32)
(fn [stack]
(let [a (peek (pop stack))
b (peek stack)]
(conj (pop (pop stack))
(+ a b))))])``````
``````[113]
``````

Some helper functions clean this up:

``````(defn push [x]
#(conj % x))``````
``````(defn dyad [f]
(fn [stack]
(let [a (peek (pop stack))
b (peek stack)
value (f a b)]
(conj (pop (pop stack))
(if (== value (int value))
(int value)
(float value))))))``````
``````(reduce
(fn [stack op]
(op stack))
[45]
[(push 9)
(push 5)
(push 32)
``````[113]
``````

We can encapsulate the implementation into a DSL with two more helpers:

``````(defn ->operations [ops]
(for [op ops]
(cond
(number? op) (push op))))``````
``````(defn execute [stack ops]
(reduce
(fn [stack op]
(op stack))
stack
(->operations ops)))``````

Now all we have to write is

``(execute [45] [9 * 5 / 32 +])``
``````[113]
``````

To see the stack at each operation use `reductions`:

``````(defn executions [stack ops]
(reductions
(fn [stack op]
(op stack))
stack
(->operations ops)))``````
``(executions [45] [9 * 5 / 32 +])``
``````([45] [45 9] [405] [405 5] [81] [81 32] [113])
``````

The stack, as a stand-in for working memory, never has to hold more than two values at a time, while the six-operation algorithm can be memorized and stored in long-term memory.

It is a bit of a cheat, however, to say the stack never needs to hold more than two values, since unless you know what 45 times 9 is, you'll probably have to hold 40 times 9 alongside 5 times 9 so you can add them together (or, protip, 45 times 10 alongside 45 so you can subtract). We'll explore this more in the next post.