from time import time

# Calcule 1500 digits de PI avec l'algorithme "spigot".
# Le benchmark valide le calcul avec un checksum pour ne pas mesurer
# l'assemblage d'une grande chaine de caracteres.

begin = time()

decimal_count = 1500

# On calcule 1 chiffre entier + les decimales demandees.
# On ajoute une iteration de marge car l'algorithme emet les chiffres avec retard.
iterations = decimal_count + 2
boxes = iterations * 10 // 3

remainders = [2] * (boxes + 1)
digits_out = [0] * (iterations + 2)
out_count = 0
predigit = 0
held_nines = 0

for _ in range(iterations):
    q = 0

    for i in range(boxes, 0, -1):
        x = 10 * remainders[i] + q * i
        denominator = 2 * i - 1

        remainders[i] = x % denominator
        q = x // denominator

    remainders[1] = q % 10
    q //= 10

    if q == 9:
        held_nines += 1
    elif q == 10:
        digits_out[out_count] = predigit + 1
        out_count += 1

        while held_nines > 0:
            digits_out[out_count] = 0
            out_count += 1
            held_nines -= 1

        predigit = 0
    else:
        digits_out[out_count] = predigit
        out_count += 1
        predigit = q

        while held_nines > 0:
            digits_out[out_count] = 9
            out_count += 1
            held_nines -= 1

digits_out[out_count] = predigit
out_count += 1

# Le premier chiffre produit est un zero technique.
checksum = 0
for i in range(1, decimal_count + 2):
    checksum += digits_out[i]

print(decimal_count + 1, "digits")
print("checksum =", checksum)

end = time()
print(f"Duration = {int((end - begin) * 1000)} ms")
