Algorithms & math trivia
A fairly common theme on this blog are write-ups about computer algorithms and mathematical curiosities. Although these are covered in countless other placed on the internet, I try to do go above and beyond: instead of regurgitating formulas, I research the “why” and explain it in a way that should make it click even if you skipped that calculus class.
What follows is the highlight reel; for a complete list of articles, refer here.
Gödel's beavers, or the limits of knowledge
Are there numbers you're not allowed to know? Can a monkey beat a beaver in a fair fight? Discover this and other limits of algorithmic knowledge.
How has mathematics gotten so abstract?
Georg Cantor's turtles, Giuseppe Peano as a software engineer, and other tales of from the kingdom of the infinite.
0.9999... ≊ 1
I’ve been long fascinated by the endless online debates about whether the infinite decimal expansion 0.9999… is exactly equal to 1. The canonical answer is yes, and it's easy to throw around suspiciously-looking proofs. But there's more to it than meets the eye, and to understand the problem, we need to ponder the meaning of infinity.
Not so fast, Mr. Fourier!
The discrete Fourier transform (DFT) is one of the most important algorithms in modern computing. Curiously, it’s also among the worst-explained topics in computer science. Let's have a closer look.
Is the frequency domain a real place?
In the earlier article on the Fourier transform, I talked about the frequency domain — a wondrous mathematical place where complex signals are transmuted into the amplitudes and phases of sine waveforms. But how real is this place, anyway?
A 20-minute intro to complex numbers
Complex numbers are a fairly abstract construct that reeks of higher math, but they crop in software engineering, electronics, and beyond. Their basic structure is explained in many places on the internet; what's less clear is why they're constructed this particular way.
Complex numbers #2: a world in 3D
In the previous article, I talked about complex numbers. Can we extend that concept to three dimensions? Yes, sort of: with quaternions. Quaternions are usually presented as revealed truth - but it's not hard build them from scratch.
π = 4
In the earlier article, I discussed the perils of thinking about infinity as a number. In this followup, we have a look at a peculiar infinity-related "proof" that π = 4. The proof is actually more correct than it may seem!
Fractals #2: understanding Mandelbrot
Almost every computer nerd knows the Mandelbrot fractal. But where does its complex 2D structure really come from?
Sierpiński triangle? In my bitwise AND?
An unexpected visitor: how come that a familiar fractal crops up when you count in binary?
If you have suggestions or other feedback, you can reach me at lcamtuf@coredump.cx.