Skip to content

Instantly share code, notes, and snippets.

@deeplook
Created February 13, 2013 20:16
Show Gist options
  • Save deeplook/4947835 to your computer and use it in GitHub Desktop.
Save deeplook/4947835 to your computer and use it in GitHub Desktop.
Generate digits of Pi using a spigot algorithm.
"""
Run the algorithm below using CPython, Cython, PyPy and Numba and compare
their performance. (This is implementing a spigot algorithm by A. Sale,
D. Saada, S. Rabinowitz, mentioned on
http://mail.python.org/pipermail/edu-sig/2012-December/010721.html).
"""
def pi_digits(n):
"Generate n digits of Pi."
k, a, b, a1, b1 = 2, 4, 1, 12, 4
while n > 0:
p, q, k = k * k, 2 * k + 1, k + 1
a, b, a1, b1 = a1, b1, p * a + q * a1, p * b + q * b1
d, d1 = a / b, a1 / b1
while d == d1 and n > 0:
yield int(d)
n -= 1
a, a1 = 10 * (a % b), 10 * (a1 % b1)
d, d1 = a / b, a1 / b1
# >>> list(pi_digits(20))
# [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4]
@Anderson-Cooper
Copy link

I've been trying to wrap my head around changing this algorithm to return a specific digit but not have it use a list to read off of (if this makes sense of course). I would really appreciate any help that I can get.

You can replace the yield int(d) above with if n == 1: return int(d) to get the nth digit only (renaming it to pi_digit(i) would then be more appropriate, too):

>>> pi_digit(5)
5
>>> pi_digit(1)
3

If you want to follow Python's 0-based indexing giving the first digit for i=0 you'd also need to take care of that.

Thanks a lot man.
:)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment