Как найти конкретную последовательность в десятичных числах PI?

Question

Я хочу найти определенную последовательность цифр в десятичных числах ПИ, которая включает в себя первые вычисления ПИ до (вполне возможно) бесконечности. Проблема в том, что я не знаю, как сделать, чтобы переменная хранила столько цифр или как использовать только что вычисленную цифру, чтобы я мог сравнить ее с моей последовательностью.

Итак, как я могу рассчитать PI и сохранить только последнее десятичное число в виде целого числа?

Заранее спасибо.

Answer 1

Такую проблему можно решить очень элегантно, используя ленивую оценку, подобную той, что была найдена в Haskell. Или используя генераторы в Python, производя не более одного числа Pi за раз, и проверяя соответствующую позицию в целевом значении, которое ищется.

Преимущество любого из подходов заключается в том, что вам не нужно генерировать (потенциально) бесконечную последовательность чисел, а генерируйте столько, сколько необходимо, пока вы не найдете то, что ищете. Конечно, если конкретная последовательность действительно не появляется в числе Pi, алгоритм будет повторяться вечно, но, по крайней мере, на компьютере, выполняющем программу, не хватит памяти.

В качестве альтернативы: вы можете использовать формулу BBP или аналогичный алгоритм, который позволяет извлечь конкретную цифру в Pi.

Answer 2

Вы можете использовать итеративный алгоритм для вычисления Pi, например, алгоритм Гаусса – Лежандра.

Для его реализации вам понадобится библиотека, которая выполняет арифметику произвольной точности; одна такая библиотека - GMP.

Видимо, кто-то сделал большую часть работы за вас: http://gmplib.org/pi-with-gmp.html

Answer 3

Вот реализация на Python алгоритма потоковой передачи, описанного Джереми Гиббонсом в Unbounded Spigot Algorithms for the Digits of Pi (2004), Chaper 6:

def generate_digits_of_pi():
    q = 1
    r = 180
    t = 60
    i = 2
    while True:
        digit = ((i * 27 - 12) * q + r * 5) // (t * 5)
        yield digit
        u = i * 3
        u = (u + 1) * 3 * (u + 2)
        r = u * 10 * (q * (i * 5 - 2) + r - t * digit)
        q *= 10 * i * (i * 2 - 1)
        t *= u
        i += 1

# Demo
iter = generate_digits_of_pi()

from time import sleep
import sys

for i in range(1000):
    print (next(iter), end="")
    sys.stdout.flush()
    sleep(0.05)