Memoization 101: Fibonnaci

Dynamic programming is one of those things that is deceptively simple to the novice but ridiculously obvious to the well-trained, meaning what it solves for requires an understanding of execution context and runtime that is neither merely theoretical nor merely practical. Like so much in computer science, knowing what it is is different from knowing how to do it, which are both altogether different from being able to do it.

The point of dynamic programming is efficiency: improving runtime by discerning and solving subproblems of algorithmic repetition; that is, where and how does an algorithm repeat itself? This is especially relevant to recursive algorithms, where the computer is often having to do the same computation in multiple recursive branches. The classical example is the Fibonnaci sequence; below we have the standard recursive function and the memoized version side by side.

While JavaScript notoriously has difficulty with large numbers, we see at the rather small handleable-by-JS input of 25 a performance difference: 2-3ms for the non-memoized version and a blazing 0ms for the memoized version!

Two things to note: this kind of memoization is called “top-down” — for some it simply means what we mean by “memoization” — and a key functionality in JavaScript making it possible here is what is called “pass by reference”; that is, all objects are passed to functions by reference, meaning in every recursive call (two calls per one call) the same memo object is read and modified, making it a register of sorts we can use to see if we’ve already performed a certain computation. As stated earlier, this is the key to dynamic programming: improving algorithmic time complexity by omitting redundant steps.

Seeing in binary

Here’s some REPL code I just threw together that prints the binary representations of all numbers between 0 and num formatted such that every representation is left-padded with zeroes to the largest bit:

Binary is awesome!