Dear reader, this post has an interactive simulation! We encourage you to play with it as you read the article below. In our series of posts on cellular automata, we explored Conway’s classic Game of Life and discovered some interesting patterns therein.

Problem: Write a program that compares two sequences of differing lengths for similarity.

It’s often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey’s paper, “An Algorithm for the Machine Calculation of Complex Fourier Series.” They published a landmark algorithm which has since been called the Fast Fourier Transform algorithm, and has spawned countless variations.

Problem: Reduce the dimension of a data set, translating each data point into a representation that captures the “most important” features. Solution: in Python import numpy def principalComponents(matrix): # Columns of matrix correspond to data points, rows to dimensions.

So here we are. We have finally made it to a place where we can transition with confidence from the classical continuous Fourier transform to the discrete version, which is the foundation for applications of Fourier analysis to programming. Indeed, we are quite close to unfurling the might of the Fast Fourier Transform algorithm, which efficiently computes the discrete Fourier transform.

Problem: Compute a reasonable approximation to a “streaming median” of a potentially infinite sequence of integers. Solution: (in Python) def streamingMedian(seq): seq = iter(seq) m = 0 for nextElt in seq: if m > nextElt: m -= 1 elif m < nextElt: m += 1 yield m Discussion: Before we discuss the details of the Python implementation above, we should note a few things.

After a year of writing this blog, what have I learned about the nature of the relationship between computer programs and mathematics? Here are a few notes that sum up my thoughts, roughly in order of how strongly I agree with them. I’d love to hear your thoughts in the comments. Programming is absolutely great for exploring questions and automating tasks. Mathematics is absolutely great for distilling the soul of a problem.

Last time we investigated the naive (which I’ll henceforth call “classical”) notion of the Fourier transform and its inverse. While the development wasn’t quite rigorous, we nevertheless discovered elegant formulas and interesting properties that proved useful in at least solving differential equations. Of course, we wouldn’t be following this trail of mathematics if it didn’t result in some worthwhile applications to programming.

In our last primer we saw the Fourier series, which flushed out the notion that a periodic function can be represented as an infinite series of sines and cosines. While this is fine and dandy, and quite a powerful tool, it does not suffice for the real world. In the real world, very little is truly periodic, especially since human measurements can only record a finite period of time.

Problem: Derive the double angle identities $$\sin(2\theta) = 2\sin(\theta)\cos(\theta)\\\ \cos(2\theta) = \cos^2(\theta) – \sin^2(\theta)$$ Solution: Recall from linear algebra how one rotates a point in the plane. The matrix of rotation (derived by seeing where $ (1,0)$ and $ (0,1)$ go under a rotation by $ \theta$, and writing those coordinates in the columns) is $$A = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\\ \sin(\theta) &

Problem: Prove that $ 2 = 4$. Solution: Consider the value of the following infinitely iterated exponent: $$\displaystyle \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}}$$ Let $ a_n = \sqrt{2} \uparrow \uparrow n$, that is, the above power tower where we stop at the $ n$-th term.