I know, the title itself seems like an oxymoron. But we do it all the time. Think π ≃ 22 / 7 = 3.1428... Not bad for government work, as my father used to say. But we can do better, much better, and Dirichlet suggests a clever way based on the pigeonhole principle. In his book Shape, Jordan Ellenberg explains the Dirichlet algorithm in detail (pp. 272-274). Let's dissect this scheme, starting with the pigeonhole principle.

The pigeonhole principle is almost too simple to have to explain, but it is used frequently in mathematics. It says that when there are more things to place (pigeons) than there are places (pigeonholes) to put them, at least one hole is going to have more than one thing in it. Dirichlet's idea is to multiply the number we are trying to appoximate in order by the integers, starting with one and up to 1001. That gives us 1001 numbers to work with. But we are only to going supply 1000 places to put them in a very special way that I will now explain.

Dirichlet didn't have access to a computer or even a calculator, but we do. So let's imagine creating an array of 1000 elements numbered from 0 to 999, each containing the sentinel, -1. Without lack of generality let's use the golden ratio, Φ = (1 + √ 5) / 2 = 1.61803... And here is the trick. We are only going to keep the first three digits after the decimal point, in this case 618. There are exactly 1000 possible three digit combinations, running from 000 to 999, but we are going to create 1001 (unique) multiples of Φ, ensuring a doubling up in at least one of our holes. We store the Φ multiplier in the element number given by the three digits we decided to keep, in the case of 1 × Φ that would be element 618, replacing the -1 that was there. Let's continue with 2 × Φ = 2.3607... Now we store the multiplier, 2, in element 360, again replacing the -1 we put there originally. Skipping ahead. we are going to find our first collision at 611 × Φ = 988.61877...

Oops! We already filled element 618 with 1 and now we have to put 611 that normally would go in the same place. That's OK because it appears we are done. If 1 × Φ and 611 × Φ have the same three numbers after the decimal point, their difference will have 000 or 999 after the point, depending on the roundoff. That difference is 610 × Φ = 987.00073... Now we can approximate Φ by 987 / 610 = 1.618, accurate to at least three digits. Done. The pigeonhole principle bailed us out. Or did it? Let's look into things a bit more.

If we call the first multiplier we store, the 1, m, and the second multiplier, 611, we tried to store in the same element, n, then we know two things. n is is greater than m because it occurs later in our increasing sequence of multipliers and therefore n − m > 0. But all the multipliers smaller than n, including n − m, have already been calculated, so we will already have seen the difference (stored in element 0 or 999) before we get to the collision, no pigeonhole principle needed. It's just an artifact of the way the successive products get calculated and stored.

The algorithm is now even simpler than Dirichlet's original one. Just keep multiplying the irrational number we are trying to approximate by successive integers until the first three digits following the decimal point are 000 or 999. Done, now. And here is Python code for the modified Dirichlet algorithm.

Try it for π. You'll get 355 / 113 = 3.14159... And |355 / 113 - π| < 3 × 10 ^-7. Pretty good, I'd say.