In part I of this two-part series we covered lookup tables and simple devices with at most a handful of moving parts. This time we’ll pick up in the 17th centuries, when computing devices started to became far more complex and the groundwork for later theoretical work began to be laid. Pascal We enter the era of mechanical calculators in 1642 when Pascal invented a machine, charmingly called the pascaline, which could perform addition and subtraction:

What is a computer, really? Where did it come from? When did we realize we could trick rocks into doing our math homework for us? In this two-part series, I’ll cover the origin and early history of computing and computer science, starting in prehistoric Africa and ending in Victorian-era England. Not exhaustively (because that would require an entire book) but selectively, highlighting the most interesting innovations and focusing on the untold (or at least less well known) stories.

I recently wrote an article which was ostensibly about the Fibonacci series but was really about optimization techniques. I wanted to follow up on its (extremely moderate) success by going in the exact opposite direction: by writing a Fibonacci function which is as slow as possible. This is not as easy as it sounds: any program can trivially be made slower, but this is boring. How can we make it slow in a fair and interesting way?

A common example of recursion is the function to calculate the \(n\)-th Fibonacci number: def naive_fib(n): if n < 2: return n else: return naive_fib(n-1) + naive_fib(n-2) This follows the mathematical definition very closely but it’s performance is terrible: roughly \(\mathcal{O}(2^n)\). This is commonly patched up with dynamic programming. Specifically, either the memoization: from functools import lru_cache @lru_cache(100) def memoized_fib(n): if n < 2: return n else: return memoized_fib(n-1) + memoized_fib(n-2) or tabulation: