[Edu-sig] digits of pi

[John Zelle]

Here's a generator I coded up based on a paper by Gibbons:
   http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf

It's simple to code, but I think you have to read the paper to figure out what 
it's doing. (I just translated some code, so I really can't tell you :-) In 
the paper, this was done in a lazy functional language. I was mostly 
interested to see how it would translate to a Python generator.

# pi.py -- imlementation of Gibbons' spigot algorithm for pi
#  John Zelle 4-5-06

def pi_digits():
    """generator for digits of pi"""
    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)

Here it is in action:

>>> import pi
>>> digits = pi.pidigits()
>>> for i in range(30): print digits.next(),
...
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7
>>>     

Since this uses long ints, it slows down considerably after a few thousand 
digits. You might want to use psyco when generating really "deep" digits.

--John


 The 
On Thursday 27 July 2006 8:27 pm, Tim Peters wrote:
> [Michel Paul]
>
> > When a student first sees Long integer capabilities a question often is
> > "How many digits of pi can it show?"  There's a slight disappointment
> > when they find out that though there's a Long integer, there is no Long
> > decimal.
>
> The newish `decimal` module has user-settable precision, although it's
> more educational to use integers.  See the pi() function at:
>
>     http://docs.python.org/dev/lib/decimal-recipes.html
>
> > I would like to be able to show them a good way to compute a list of an
> > arbitrary number of digits in the decimal expansion of of pi.  I think
> > they might find that interesting.
>
> See the very old Demo/scripts/pi.py in a Python distribution -- it's
> one of the first things Guido coded in Python.  Although I'm
> considered a numerical expert, I still have no idea how it works :-)
>
> An enormous number of ways you /could/ proceed:
>
>     http://mathworld.wolfram.com/PiFormulas.html
> _______________________________________________
> Edu-sig mailing list
> Edu-sig at python.org
> http://mail.python.org/mailman/listinfo/edu-sig

-- 
John M. Zelle, Ph.D.             Wartburg College
Professor of Computer Science    Waverly, IA     
john.zelle at wartburg.edu          (319) 352-8360