Hidden in π

π notes

How we search 100 billion digits in a blink

The trick behind Hidden in π: we read every digit once, in advance, and wrote the answers in one enormous table. Here is how that table works.

· 5 min read

Type your birthday into the box on the home page and the answer comes back before you have finished blinking. That is a little strange, because the digits we search are a very long line of numbers: 100 billion of them. If you printed them in a normal book, with about 2,000 digits on each page, the book would have fifty million pages. Reading it out loud, one digit a second, would take more than three thousand years.

So how can a website find your number in it so fast? The honest answer is: it doesn't search at all. We did the searching once, long before you arrived, and wrote down every answer.

The slow way

Imagine you want to find your phone number in π the obvious way. You start at the beginning, 3.14159…, and check: does my number start here? No. Move one digit along. Does it start here? No. And so on.

A computer can do this very quickly, a few billion checks a second, but 100 billion digits is still a lot of checking. Worse, the digits do not fit in a computer's working memory, so it would have to keep reading them from a disk. A single search could take minutes, and if lots of people searched at once, the website would grind to a halt.

The clever way: a giant answer book

Here is the trick. A ten-digit number is one of exactly 10 billion possibilities, from 0000000000 to 9999999999. That is a big number, but it is a fixed number. So instead of asking "where is this one number?" over and over, we asked a different question just once: "where does every ten-digit number first appear?"

To answer it, the computer slid a little window along π, ten digits wide:

  • At decimal 1, the window shows 1415926535. Is that number new? Yes, so write "1" on its line in the answer book.
  • Slide one step. Now the window shows 4159265358. New again, so write "2" on its line.
  • Keep going, one step at a time, for all 100 billion digits.

If a number has already been written down, the computer leaves its line alone, because we only care where a number turns up first. When the window reaches the end, the answer book is finished.

One line for every number

The answer book is really a table with 10 billion lines, and the clever part is how the lines are arranged. Line 0 belongs to the number 0000000000, line 1 to 0000000001, and so on, all the way up. So the line for your number is simply your number itself.

Each line holds the position written in 5 bytes, which is enough to count past a trillion. That makes the whole table about 50 gigabytes, roughly what ten long films take up. To find the line for 0123456789, the computer does one small sum (123,456,789 × 5) to work out where that line starts, reads those 5 bytes, and there is the answer. No searching, no scanning: one read.

Some lines stay empty, because some ten-digit numbers simply don't appear in the first 100 billion digits. About 454,000 of them are missing, which is exactly what chance predicts. If your number is one of those, we tell you so, and then look for the longest piece of it that is there.

What about shorter numbers?

A 4-digit PIN or a 6-digit date gets its own, much smaller table, built the same way. Numbers of 7 to 9 digits use the big table in a sneaky way: every ten-digit number that starts with your seven digits sits on neighbouring lines, so we read that short run of lines and pick the earliest position. Still one read.

A word works too. On a phone keypad, every letter sits on a digit (A, B and C are on 2; T, U and V are on 8), so a name becomes a number and we look that up instead. You can watch a name turn into digits in a Name Fight.

Checking the homework

A table that size would be easy to get subtly wrong, so before it was used, a separate checking program, written without sharing any code with the builder, picked thousands of lines at random. For each one it went back to the digits, looked at the position written there, and made sure the number really does start at that spot. It also counted the empty lines and checked that the count matched what chance predicts.

So where does the time go?

The looking-up part is tiny. Most of the time between pressing the button and seeing your answer is the request travelling across the internet to our server and back, plus fetching the forty digits around your result so we can show them to you.

One more thing happens on the way: nothing. Your number travels inside the request, never in the address bar, and we don't log it or keep it. The position isn't stored either, because a position can give a number away just as easily as the number itself.

Try it yourself

Sources

Filed under how-it-workssearchtables

All π notes · Follow the notes by RSS

Change the board