March 14, 2010

Python Spigot

Here is (not to be confused with pypy), a short python implementation of Jeremy Gibbons's 2005 spigot generator for decimal digits of pi:

def pi_decimal_digits():
  q, r, t, j = 1, 180, 60, 2
  while True:
    u, y = 3*(3*j+1)*(3*j+2), (q*(27*j-12)+5*r)//(5*t)
    yield y
    q, r, t, j = 10*q*j*(2*j-1), 10*u*(q*(5*j-2)+r-y*t), t*u, j+1

The code to drive the algorithm is longer than the algorithm:

count, digits = 0, pi_decimal_digits()
while 1:
  print '%6d: %s' % (
    count, ''.join([str( for j in xrange(50)]))
  count += 50

This little script can be quite handy if, for example, you want to look up where in the digits of pi you can find the phone number for the Mass Audubon Society that is down the road from my house:

> ./ | grep --color 2599661
  3050: 56638937787083039069792077346722182562599661501421

Conveniently, their phone number starts at the very visible 3087th digit of pi after the decimal point. My home phone number is a little bit further into the private section the pi phone book, at the 6,301,261th digit. And, if you must, you can reach me at my cell at the 22,000,091th digit, although I should warn you that my reception is not very good out here in the boonies.

Happy pi day.

Posted by David at March 14, 2010 08:35 AM

A couple things to note.

Davidmay points out that because of line breaks, you can't actually find all subsequences just by grepping like this. If you want to really do exhaustive searches, you'd have to do a real search without discontinuities.

Also, this algorithm isn't really fast enough to let me compute the 22,000,091th digit in a reasonable amount of time on my laptop. I had to cheat and use a pi searching service, of which there are several different flavors online.

Posted by: David at March 14, 2010 02:10 PM
Post a comment

Remember personal info?