Generate digits of Pi using a spigot algorithm.

pi_digits.py

"""
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]

My curiosity would love to run this using numba @njit, to see how fast it calculates, however when I try to do that, this function only returns 0s for the digits, for me.. I'm kinda new to numba, so I'm not sure if I'm just forgetting something simple.

Hi! I've just checked on the mybinder on https://numba.pydata.org with numba 0.55.1 and see also zeros generated. Comparing again with the code in the referenced source I see only difference is the "and n >0" added in line 15. Removing this will eat the momory until the Jupyter kernel dies at 2 GB. I'm sory I don't remember if this worked with numba before, when I added this gist (quite a while ago). I guess it's worth and would recommend raising an issue on https://github.com/numpy/numpy/issues.

Hi! I've just checked on the mybinder on https://numba.pydata.org with numba 0.55.1 and see also zeros generated. Comparing again with the code in the referenced source I see only difference is the "and n >0" added in line 15. Removing this will eat the momory until the Jupyter kernel dies at 2 GB. I'm sory I don't remember if this worked with numba before, when I added this gist (quite a while ago). I guess it's worth and would recommend raising an issue on https://github.com/numpy/numpy/issues.

Thanks for the reply!
Actually, I asked around in the numba community about this, and a possible reason for this function not working with numba, may be that the formula's internal numbers become too large, and supposedly numba only supports integers up to 64 bits.. If so, oh well.
Tho on a related note, while trying to find alternative ways to speed this up, I happened across a significantly faster (albeit "unproven" beyond 1mil digits) spigot algorithm, if you're interested: https://gist.github.com/GavalasDev/d72f705629724db4f0e90ee8a57a8f20

Hello and apologies if this is a rather stupid question.

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.

Cheers.

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.

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.
:)