pi_digits.py

import sys


# Prints a list of digits to stdout
def emit(digits: list[int], newline:bool = False) -> None:
    for i in digits:
        print(i, end='')
    if newline:
        print()


# A Spigot Algorithm for the Digits of π
# Stanley Rabinowitz and Stan Wagon
# https://www.maa.org/sites/default/files/pdf/pubs/amm_supplements/Monthly_Reference_12.pdf
def generate(num_digits: int) -> None:
    # initialize the table
    # Since the algorithm is backwards-adjusting on previous values based on current values,
    # we need to calculate at least 1 additional predigit to adjust held predigits
    table_width = int((10*(num_digits+1))/3)
    # [seed value, Leibniz numerator, Leibniz denominator, carry value]
    # https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80
    table = [[2, i, (i*2)+1, 0] for i in range(0, table_width)]
    predigits = []

    # Generative loop for every desired digit
    for i in range(0, num_digits+1):
        # Walk the table backwards
        for j in reversed(range(0, table_width)):
            # Each entry is the seed multiplied by 10, plus any pre-calculated carry
            entry = (table[j][0] * 10) + table[j][3]
            # If we're in the middle of the table, calculate the values for the next move left
            if j > 0:
                q = entry // table[j][2]
                r = entry % table[j][2]
                c = q * table[j][1]
                table[j-1][3] = c  # left carry
            # If we're in the left edge of the table, prepare digit
            else:
                predigit = entry // 10

                # predigit 10 needs to modulo to 0 and increment and mod carry all held predigits
                if predigit == 10:
                    predigit = 0
                    predigits = [(n+1)%10 for n in predigits]

                # Unelss we have a 9, emit previously held predigits
                if predigit != 9:
                    emit(predigits, newline=False)
                    predigits = []

                # Hold the current predigit for the next iteration
                # Unless it's the +1 calculation
                if i < num_digits:
                    predigits.append(predigit)

                r = entry % 10
                
            # The remainder seeds the next iteration
            table[j][0] = r

    # Emit any remaining held predigits
    emit(predigits, newline=True)



def error_args():
    print('Bad arguments. Pass one argument as int.')


if __name__ == '__main__':
    args = sys.argv
    if len(args) == 2:
        try:
            num_digits = int(args[1])
            generate(num_digits)
        except ValueError:
            error_args()
    else:
        error_args()