[Edu-sig] digits of pi
John Zelle
john.zelle at wartburg.edu
Fri Jul 28 21:39:23 CEST 2006
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
More information about the Edu-sig
mailing list