Compute Any Digit Of Pi Without Computing The Others

Added: 2026-05-09

[00:00:00]In 2010, a researcher at Yahoo named Tuis did something strange. He took a 1,000 machine cluster, ran it for 23 days, and computed exactly one number, just [music] one, the two quadrillionth binary digit of pi, 2 * 10 15th. He found that it was zero. Now, here's the thing. He did not compute the first digit of pi. [music] He did not compute the second digit. He did not compute any of the digits between the first and the two quadrillionth. Just that one specific digit by itself. Far out in the expansion.

[00:00:38]This shouldn't be possible. [music] We have been computing pi since Archimedes.

[00:00:43]Every algorithm we have for it works the same way. Start at the beginning, grind out digits one by one, get further and further. The Chudnowski algorithm is the fastest way we know to compute pi sequentially. [music] and it still has to compute all the digits up to the one you want. So, how did somebody jump straight to digit number two quadrillion? The answer is a formula that was discovered in the fall of 1995.

[00:01:08]It was found by accident by a computer and proven by hand only afterwards.

[00:01:13]Today, we're going to look at exactly what it is, why it works, and why nobody knew it could exist until a Canadian mathematician fed pi into the right algorithm. Take any number you can think of. The square root of two, Oiler's constant, pi itself. Most of these numbers are irrational. Their decimal expansions go on forever and never repeat. The standard [music] way to compute the nth digit of an irrational number is to compute the entire number to end digits of precision. There's no shortcut because every digit depends on the cumulative arithmetic that came before it. If you want to know what's in the millionth decimal place of pi, you need to do approximately a million digits of work. If you want the trillionth, you need a trillion [music] digits of work. If you want the quadrillionth, well, that's why you'd need a thousand machine cluster running for 23 days. This isn't a quirk of bad algorithms. It's a structural fact. Pi is built up by summing infinite series, and you have to add up enough terms to get the precision right. The Mardiva series, Newton's series, machines [music] formula, Rammanujian series, Chidnovski series, they all converge to pi at different speeds, but they all need full precision arithmetic to extract [music] any specific digit. So in 1995, when somebody announced you could compute the nth digit of pi without computing the previous n minus one digits, the natural reaction was disbelief. Here's a fact most people don't know. For rational numbers, fractions like 17th, you actually can extract any digit you want without computing the previous ones. Take 17th.

[00:02:54]Its decimal expansion is 0.142857, repeating forever. Suppose you want the millionth digit. Here's how you get it.

[00:03:05]Take 10 to the millionth power, divide by 7, take the fractional part, multiply by 10, take the floor. That's your digit. The whole computation reduces to one quantity, the remainder when 10^ the millionth power is divided by 7. And that remainder is fast to compute.

[00:03:24]There's an algorithm called modular exponentiation that lets you compute 10 the n modulo any number in roughly the logarithm of n basic operations. For n= a million, that's about 20 multiplications. For n= a trillion, it's 40. For any n at all, it's tiny. The trick is repeated squaring. You compute 10 squared, then 10 4th, then 10 8th, then 16th, all modulo 7. 20 steps gets you 10 million. Then you assemble these from the binary representation of n. So for rationals, digit extraction is essentially free. The hard case is irrationals [music] and that's where pi comes in. Simon Pluff was a Canadian mathematician working at Simon Fraser University in 1995.

[00:04:14]He was not a celebrity. He had no PhD.

[00:04:17]He had spent years building something called the inverse symbolic calculator, a tool that took numerical decimal expansions as input and tried to identify them as known mathematical constants. His colleagues at Simon Fraser, the Borwine brothers, had recently helped develop an algorithm called PSLQ created by Helerman Ferguson and David Bailey in 1992.

[00:04:41]PSLQ is an integer relation finder. You give it a list of real numbers and it tries to find a small integer linear combination of them that equals zero.

[00:04:52]It's a generalized version of the Uklitian algorithm extended to many dimensions. In the autumn of 1995, Pluff set up an experiment. He took pi computed to a few hundred digits of precision and asked PSLQ a question.

[00:05:07]Could pi be written as an integer combination of polygarithm style sums?

[00:05:12]Sums that look like 1 / 16 to the k divided by linear functions of k. PSLQ ran. [music] It returned a vector of integers, specifically 4 0 0 0 -2 - 1 -1 0 0. Pluff didn't know what to do with it at first. The bore wines did. That vector was a formula nobody had ever derived from theory. Here it is. Pi equals the sum from k = 0 to infinity of 1 16 to the k * a bracket inside the bracket 4 / 8k + 1 - [music] 2 / 8 k + 4 -1 / 8k + 5 -1 / 8k + 6. Let me check it. First term k= 0. The bracket is 4 over 1 - 2 over 4 - 1 over 5 - 1 / 6.

[00:06:09]That's 4 - 0.5 - 0.2 - 0.1 666 sum 3.133 already close to pi. Now the second term k= 1. The bracket is 4 over 9 - 22 - 1 over 13 - 1 [music] / 14. That's about 0.129.

[00:06:35]Divide by 16. About 0.8.

[00:06:40]Add to the first term 3.1414.

[00:06:44]We've got four correct [music] decimal digits of pi from two terms of the series. By the fifth or sixth term, you [music] have six digits. By the 10th, you have 12 digits. The series converges fast about 1 and a4 decimal digits per term. But this is just an ordinary convergent series for pi. Many such series exist. What makes this one extraordinary is the 16 to the k denominator. That structure is the key to everything that follows. Here's the move. Suppose you want hex digit number n of pi. The way to get it, compute pi.

[00:07:21]Multiply by 16 ^ nus1. Take the fractional part. Multiply by 16. Take the floor. That's the digit at position n in base 16. So we need the fractional part of 16 n -1 *<unk>. Substitute the formula for pi. Each term of the series gets multiplied by 16 nus1. [music] The 16 to the k in the denominator combines with this. You get 16 nus1 minus k multiplied by the bracket. Now split the sum into two pieces. The terms where k is less than n [music] and the terms where k is greater than or equal to n. The second piece k greater [music] than n has 16 raised to a negative power. These terms decay [music] like 1/16th 1 over 256 1 over 4,000. After a couple dozen terms, the sum is precise [music] to many digits. Cheap. The first piece k less than n has 16 raised to a non-gative power. Each term is a positive integer divided by a small integer like 8k + 1. Take the fractional part. The integer divided by integer becomes its remainder divided by the small integer. So we need 16 the nus1 minus k modulo 8 k + j. And that's exactly what modular exponentiation gives us in O of log n operations per term with n terms total. The whole digit extraction takes about n log 2 n bit operations and the working memory is only log n bits. The space efficiency is what matters. You can compute the trillionth bit of pi without storing a trillion digits. The algorithm depends entirely on one fact. You can compute 16 to the M modulo q in roughly the logarithm of m operations. The technique is called square and multiply. Suppose m is 1 trillion. Write m in binary. It's about 40 bits long. Now compute in sequence 16^ the 1 q 16^ the 2 mod q 16 to the 4 mod q 16 to the 8 16 to the 16 all the way up to 16 to the 2 to the 40th power. Each step is just one squaring of the previous result. Then taking the remainder mod q, 40 squarings.

[00:09:42]After that, you assemble 16 to the m by multiplying together exactly the powers of two that appear in m's binary expansion. For m a trillion, that's about 40 multiplications.

[00:09:53]Each squaring or multiplication keeps the numbers bounded by q ^ 2, then reduces by q. Q in our case is at most 8 n + 6 a small number. So the arithmetic operates on tiny integers.

[00:10:08]The whole modular exponentiation is micro and the algorithm calls it n* once per term in the series. That's why the trillionth hex digit of pi takes about a few seconds on a laptop not 3 years. The formula gives pi in base 16. That's the 16 to the k structure. Equivalently, base 2, every hex digit unpacks into four bits. So, we can extract any binary digit of pi we want. Cheap and direct, but not base 10. The formula has no power of 10 in it. If you wanted the trillionth decimal digit, this approach gives you nothing. You'd have to extract enough hex digits to convert, and converting requires all the digits up to that point. That's the deep limitation.

[00:10:56]Could there be a similar formula for base 10? In 2004, three mathematicians, Jonathan Borwine, David Borwine, and William Gway, proved that no formula of this exact shape exists for pi in any non-binary base.

[00:11:12]Specifically, no degree 1 machine type formula. This doesn't rule out radically different digit extraction methods. In 2022, Plof himself published an alternative base 10 algorithm for pi, but it requires computing the previous decimal digits. It's not a true spot.

[00:11:31]So, the gap remains. Pi is spot friendly in base 2 and base 16 and nowhere else as far as anyone knows. There may be a deep reason, there may not. It's an open problem. Let's actually compute a digit.

[00:11:46]Suppose you want hex digit number 100.

[00:11:50]For each J in the set 1 4 5 6 sum from K= 0 to 99 the value 16^ 99 - K modulo 8 K + J / 8 K + J then add a small tail of about 20 more terms with negative powers of 16 form the combination 4 S1 - 2 S4 - S5 - S6 take the fractional part multiply by 16 floor. That integer is the 100th hex digit of pi. The whole algorithm runs in milliseconds. The memory used is a few hundred bytes. No infinite precision arithmetic, no big integers, no large internal state, just modular remainders and a final fixed point sum. You can run this for any n, million, billion, trillion, quadrillion.

[00:12:43]The cost grows almost linearly. The memory stays constant. In 1997, 2 years after the original formula, Fabris Bellard found an improved version. Same idea, different polylog combination, denominator 2 the 10th instead of 16, about 43% faster per digit. Bellad used his own formula to compute the billionth binary digit of pi on a workstation.

[00:13:10]Then came pi hex. Colin Persal organized a distributed computing project with hundreds of volunteers. across the world. By the end of 2000, they had computed the quadrillionth binary digit of pi. The answer is zero. In 2010, TeoC pushed it to the two quadrillionth bit on a th00and machine Yahoo cluster, also zero. In 2018, the 100 quadrillionth hex digit was computed on an Intel Xeon 5 cluster.

[00:13:42]The technique extends PSLQ the algorithm PLO used to find the formula in the first place has gone on to find closed form expressions for the reman zeta function at 3 and 5 for Catalan's constant for matalong sums for fineman diagram amplitudes PSLQ was named one of the top 10 algorithms of the 20th century a whole sub field opened up experimental mathematics using computers not just to verify proof proofs, but to discover the identities themselves.