Calculate pi without losing performance in C++ or Python

Question

I am looking for an algorithm to calculate pi and keep calculating without having to calculate everything over again. I'm trying to look for a number in pi. I made an algorithm in Python which does exactly that, but it slows down with the time (obviously):

def make_pi(lenght):
    q, r, t, k, m, x = 1, 0, 1, 1, 3, 3
    for j in range(lenght):
        if 4 * q + r - t < m * t:
            yield m
            q, r, t, k, m, x = 10*q, 10*(r-m*t), t, k, (10*(3*q+r))//t - 10*m, x
        else:
            q, r, t, k, m, x = q*k, (2*q+r)*x, t*x, k+1, (q*(7*k+2)+r*x)//(t*x), x+2

piArray = []

for i in make_pi(50):
    piArray.append(str(i))

piArray = piArray[:1] + ['.'] + piArray[1:]
piString = "".join(piArray)

lookingFor="9833673362"
found=False

current=10

while found==False:
    print(str(current))
    for i in make_pi(current):
        piArray.append(str(i))

    piArray = piArray[:1] + ['.'] + piArray[1:]
    piString = "".join(piArray)
    if piString[-len(lookingFor):] == lookingFor:
        found=True
        print("Found! Tries: " + str(current - 10))
    current+=1

I need a faster algorithm in Python or possibly even C++. (With faster I mean it shouldn't slow down)

That code is kinda ugly and hard to read. And you don't give enough information (e.g. what kind of performance-degradation you are observing. This is important to tell if this degradation is due to your code or due to the algorithm-complexity) Well... The [BBP-formula](https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula) looks like it's easy to implement and it's growing with O(n*log n). This should be asymptotically the best you can do. — sascha, Jun 02 '16 at 21:29
Sorry for that ugly code, I'm just testing around + I have no experience with calculating PI so I can't tell you what I need exactly. Thank you for the reply! — fabian0010, Jun 02 '16 at 21:35
Here's [Gauss-Legendre Algorithm to compute the digits of π in Python](http://stackoverflow.com/a/347749/4279). `decimal` module may be accelarated using C since Python 3.3. — jfs, Jun 03 '16 at 00:24

score 5 · Accepted Answer · answered Jun 02 '16 at 21:42

In this case I would use a spigot algorithm, which allows to calculate the n-th digit of pi with limited amount of memory, and not increasing with the index of the digit; in particular, the Bailey–Borwein–Plouffe variant.

This link is most probably what you are looking for, if I understand correctly your question:

The formula can directly calculate the value of any given digit of π without calculating the preceding digits

Calculate pi without losing performance in C++ or Python

1 Answers1