Improving a mental math stack algorithm

In the previous post I showed the conversion from Celsius to Fahrenheit as a stack-based algorithm:

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

[113]

Unfortunately, hiding in this algorithm are some operations that can be difficult to do mentally, namely 45 times 9 and 405 divided by 5. Let's rewrite the algorithm to be easier, even at the expense of making it longer.

The mental math way to multiply by 9 is to multiply by 10 and subtract the current value from the result, e.g. (45 × 10) - 45 = 450 - 45 = 405. To do the same in stack-based programming, we need a couple new stack operations, which means we need to redefine ->operations from the last post to distinguish between our new stack operations and basic clojure.core functions that need to be dyadified:

(defn ->operations [ops]
  (for [op ops]
    (cond
      (:stack-op (meta op)) op
      (fn? op)              (dyad op)
      (number? op)          (push op)
      (vector? op)          (push op))))

Notice I've also added support for pushing vectors onto the stack. We'll see why below.

The first operation we need is one that duplicates the value at the top of the stack:

(def dup
  ^:stack-op
  (fn [stack]
    (conj stack (peek stack))))

(I've split defn into def and fn because we need to put the :stack-op metadata on the value, not on the var, as (defn ^:stack-op dup ...) would do.)

We also need an operation that manipulates the stack beneath the top value. This is why we needed to push vectors onto the stack, so we can push a list of operations to execute before putting the top value back on the stack.

(def dip
  ^:stack-op
  (fn [stack]
    (let [ops (peek stack)
          top (peek (pop stack))
          stack (pop (pop stack))]
      (conj (execute stack ops) top))))

Now we can see the stack after each operation:

(executions [45] [dup [10 *] dip -])

([45] [45 45] [45 45 [10 #function[clojure.core/*]]] [450 45] [405])

The whole Celsius to Fahrenheit conversion is now:

(executions [45] [dup [10 *] dip - 5 / 32 +])

([45]
 [45 45]
 [45 45 [10 #function[clojure.core/*]]]
 [450 45]
 [405]
 [405 5]
 [81]
 [81 32]
 [113])

Let's make that division by 5 more mental math-friendly by replacing it with division by 10 and multiplication by 2:

(executions [45] [dup [10 *] dip - 10 / 2 * 32 +])

([45]
 [45 45]
 [45 45 [10 #function[clojure.core/*]]]
 [450 45]
 [405]
 [405 10]
 [40.5]
 [40.5 2]
 [81]
 [81 32]
 [113])

The stack algorithm is somewhat long and unweildy now, but notice that we're multiplying a value by 10 only to later divide by 10. In standard math notation, where x is the value on the top of the stack, this algorithm does the following:

Which is equivalent to

In math lingo, we can distribute division over subtraction, which in stack notation becomes this:

(executions [45] [dup 10 / - 2 * 32 +])

([45] [45 45] [45 45 10] [45 4.5] [40.5] [40.5 2] [81] [81 32] [113])

This algorithm is much easier to remember than the one before it, and much easier to execute mentally than the original. All that's needed to convert from Celsius to Fahrenheit is subtracting a tenth, doubling, and adding 32.

In the next post we'll detect and apply these kinds of substitutions programatically.