Instantly share code, notes, and snippets.

# deeplook/pi_digits.py

Created February 13, 2013 20:16
Show Gist options
• Save deeplook/4947835 to your computer and use it in GitHub Desktop.
Generate digits of Pi using a spigot algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ 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.

### deeplook commented Aug 14, 2022

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.

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

### Anderson-Cooper commented Jun 21, 2023

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.

### deeplook commented Jun 22, 2023

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.

### Anderson-Cooper commented Jun 23, 2023

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