-4
Я ищу алгоритм вычисления pi и продолжаю вычислять, не вычисляя все заново. Я пытаюсь найти номер в pi. Я сделал алгоритм в Python, который делает именно это, но это замедляет со временем (очевидно):Вычислить pi без потери производительности в C++ или Python
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
мне нужен быстрый алгоритм в Python или, возможно, даже C++. (С быстрым я имею в виду, что он не должен замедляться)
Этот код является довольно уродливым и трудночитаемым. И вы не даете достаточно информации (например, какую деградацию производительности вы наблюдаете. Это важно, чтобы определить, связано ли это ухудшение с вашим кодом или из-за сложности алгоритма) Ну ... [BBP-формула ] (https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula) выглядит так, что его легко реализовать, и он растет с помощью O (n * log n). Это должно быть асимптотически лучшим, что вы можете сделать. – sascha
Извините за этот уродливый код, я просто тестирую + У меня нет опыта вычисления PI, поэтому я не могу точно сказать вам, что мне нужно. Спасибо за ваш ответ! – fabian0010
Вот [Алгоритм Гаусса-Лежандра для вычисления чисел π в Python] (http://stackoverflow.com/a/347749/4279). 'decimal' модуль может быть ускорен с использованием C с Python 3.3. – jfs