## The Digits of Pi

### February 20, 2009

A spigot algorithm spits out the digits of an irrational number, one at a time, like a leaky faucet. Jeremy Gibbons gives a spigot algorithm for pi at http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/spigot.pdf:

```(define (pi-spigot z)   (let loop ((z z) (ds '()) (q 1) (r 0) (t 1) (k 1) (n 3) (m 3))     (cond ((zero? z) (reverse ds))           ((< (+ q q q q r (- t)) (* n t))             (loop (- z 1) (cons n ds) (* 10 q) (* 10 (- r (* n t)))                   t k (- (quotient (* 10 (+ q q q r)) t) (* 10 n)) m))           (else (loop z ds (* q k) (* (+ q q r) m) (* t m) (+ k 1)                       (quotient (+ (* q (+ k k k k k k k 2)) (* r m))                       (* t m)) (+ m 2))))))```

```> (pi-spigot 1001) (3 1 4 1 5 9 ... 2 0 1 9 8 9)```

Just in case you’re curious, the one-millionth digit of pi is 1, and the one-billionth digit of pi is 9.

Pages: 1 2

### 8 Responses to “The Digits of Pi”

1. Matt Weaver said

My solution, written in C:

This version calculates the requested digit directly, based on the method described in “Computation of the nth decimal digit of pi with low memory”: http://numbers.computation.free.fr/Constants/Algorithms/nthdecimaldigit.pdf (and I must admit I also peeked a little at the implementation at http://numbers.computation.free.fr/Constants/Algorithms/nthdigit.html)

It lacks the conciseness and elegance of the spigot solution, but makes up for it in efficiency. The spigot version works well until it runs out of main memory and starts paging, at which point performance really hits a wall. On my computer that point is somewhere between the 20,000th digit (took 1:48) and the 50,000th (I killed it after 3.5 hours). For comparison, this solution returns the 50,000th digit in ~12 seconds.

2. programmingpraxis said

Alexander J. Yee & Shigeru Kondo recently computed five trillion digits of pi.

3. Graham said

I modified the fixed-point approach for arccot found
here
and used it with Wikipedia’s most efficient Machin-Like formula found
here
My submission

4. This seems like a really interesting exercise, however I cannot understand how this spigot algorithm works. I read the PDF, but I could not follow the maths in the diagram, is there an easier explanation for someone who doesn’t have a massive background in maths?

Cheers,
-Sam

5. It isn’t pretty but it works:

``` #!/usr/bin/perl```

``` \$| = 1; push(@B, 0); \$counter = 3; for(\$i = 0;\$i<=33223;\$i++){ push(@A,\$i); push(@remainder, 2); push(@B, \$counter); \$counter += 2; } for(\$x = 1; \$x=1;\$i--){ \$m10[\$i] = \$remainder[\$i] * 10; \$sum[\$i] = \$m10[\$i] + \$carried[\$i]; \$remainder[\$i] = \$sum[\$i] % \$B[\$i]; \$carried[\$i - 1] = ((\$sum[\$i] - \$remainder[\$i]) / \$B[\$i]) * \$A[\$i]; } \$m10 = \$remainder * 10; \$sum = \$m10 + \$carried; \$remainder = \$sum%10; \$predigit = int(\$sum/10); push(@predigits, \$predigit); if(\$predigit < 9){ for(\$i = 0; \$i<((scalar @predigits)-1); \$i++){ print \$predigits[\$i]; } undef @predigits; push(@predigits, \$predigit); } ```

``` if(\$predigit == 10){ for(\$i = 0; \$i<((scalar @predigits)-1); \$i++){ if(\$predigits[\$i] == 9) { print 0; } else { \$predigits[\$i] = \$predigits[\$i] + 1; print \$predigits[\$i]; } } undef @predigits; push(@predigits, 0); } } ```

6. David said

Python:

```def pi_spigot():
(q, r, t, k, n, l) = (1, 0, 1, 1, 3, 3)
while True:
if 4*q+r-t < n*t:
yield n
(q, r, t, k, n, l) = (10*q, 10*(r-n*t), t, k, (10*(3*q+r))//t-10*n, l)
else:
(q, r, t, k, n, l) = (q*k, (2*q+r)*l, t*l, k+1, (q*(7*k+2)+r*l)//(t*l), l+2)

def print_pi(n):
digits = pi_spigot()
print('pi =', str(next(digits)) + '.', end='')
while n > 0:
print(str(next(digits)), end='')
n -= 1

print()
```

Running:

```>>> print_pi(20)
pi = 3.14159265358979323846
>>> print_pi(1000)
pi = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989
```
7. David said

For the curious, all first 1000 digits (it ran off last post there…)

```>>> print_pi(1000)
pi = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328
230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378
678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789
259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188
575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766
940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212
902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334
468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185
77805321712268066130019278766111959092164201989
```