PI π Calculation loading system

Question

thank you for taking time to read and (hopefully) answer my question! I have recently taken a interest in Pi (π not the edible type, i already love those!) and was intrigued in the calculation of such a number, i can fluently type in moderately advanced python and am a advanced Linux user so i set up a "cluster" of old(ish) computers. after some digging i found a python program that calculates pi, i edited it and made it output to a file,i ran it on one of the computers and it works amazingly, it is currently on about 2 million digits of pi (tiny compared to the world record of 22.7 trillion!) and is using 100% of both cores and 94% of ram, my only issue is that i cannot cancel the process or i ave to start all over, i am trying to understand the algorithm so i can code in a load function. the load function should open the file and continue calculating pi from there onwards. i can understand the algorithm slightly and have figured out it uses the already calculated pi digits to figure out the digits (which explains the speed decay) and so loading in pre calculated data is possible. The code is as followed:

import sys


def calcPi():
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4*q+r-t < n*t:
            yield n
            nr = 10*(r-n*t)
            n  = ((10*(3*q+r))//t)-10*n
            q  *= 10
            r  = nr
        else:
            nr = (2*q+r)*l
            nn = (q*(7*k)+2+(r*l))//(t*l)
            q  *= k
            t  *= l
            l  += 2
            k += 1
            n  = nn
            r  = nr

pi_digits = calcPi()
i = 0
for d in pi_digits:
    sys.stdout =open("piDigits.txt", "a")
    sys.stdout.write(str(d))
    i += 1
    if i == 50:
        print("")
        i = 0

If anybody could help me find a way to load in the pre-calculated digits of pi and continue calculating from there or explain the algorithm/code to me i would i would be extremely grateful! Thanks in advance. -Leo Cornelius

Answer 1

What you need is to dump and restore the whole state of the calcPi generator. Luckily for you all the state is specified explicitly in the first line. Here is a prototype to show you the idea:

import sys
import os.path


def calcPi(state=None):
    if state is None:
        q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
        skip_first = False
    else:
        q, r, t, k, n, l = state
        skip_first = True
    while True:
        if 4 * q + r - t < n * t:
            # have to skip the first yield in the "restore state" scenario because
            # this is the same we returned the last time from this state
            if not skip_first:
                state = q, r, t, k, n, l
                yield n, state
            else:
                skip_first = False
            nr = 10 * (r - n * t)
            n = ((10 * (3 * q + r)) // t) - 10 * n
            q *= 10
            r = nr
        else:
            nr = (2 * q + r) * l
            nn = (q * (7 * k) + 2 + (r * l)) // (t * l)
            q *= k
            t *= l
            l += 2
            k += 1
            n = nn
            r = nr


initial_state = None
total_digit_cnt = 0
buf_digit_cnt = 0
state_file_name = "piState.txt"
if os.path.isfile(state_file_name):
    with open(state_file_name, "r+") as stateF:
        lines = stateF.readlines()
        if len(lines) > 0:
            last_line = lines[-1]
            # truncate the old state and save only the few last last lines
            stateF.seek(0)
            stateF.truncate(0)
            stateF.write(lines[-3])
            stateF.write(lines[-2])
            stateF.write(last_line)
            initial_state = map(long, last_line.replace('(', '').replace(')', '').split(','))
            total_digit_cnt = initial_state[-1]
            initial_state = initial_state[:-1]

if initial_state is not None:
    print str((total_digit_cnt, initial_state))

pi_digits = calcPi(initial_state)
buf = ""
state_cnt = 0
with open("piDigits.txt", "a") as outF:
    with open(state_file_name, "a+") as stateF:
        for digit, state in pi_digits:
            buf += str(digit)
            buf_digit_cnt += 1
            total_digit_cnt += 1

            if buf_digit_cnt == 500:
                print "Start dumping state %d" % state_cnt
                buf_digit_cnt = 0
                outF.write(buf)
                buf = ""
                outF.write("\n")
                outF.flush()
                # as states take much more space, clear old states
                state_cnt += 1
                if state_cnt % 50 == 0:
                    stateF.seek(0)
                    stateF.truncate(0)
                stateF.write(str((state, total_digit_cnt)) + "\n")
                stateF.flush()
                print "End dumping state %d" % state_cnt

The idea is to return not only next digit but also the whole state from the generator and periodically dump it into another file. This is only a prototype. In the real code to handle millions of digits you probably want to dump the state by time elapsed since the last dump rather than by count as the calculation of the each next digit will probably become slower and slower. However this complicates the restoration code to track more details (for example, how many digits have actually been written in the last line?) so I didn't put it into the PoC.

Answer 2

The code you're using has a generator in it. This is a function with a 'yield' statement. What these do is yield a value when called and then wait until they're called again, usually in a loop, before calculating the next value and then yielding that. Because you're calculating an infinite number in an infinite loop, the program will run until you kill it, and then you will lose the state. So you need a way to persist state.

I would recommend that you implement an iterator to replace the generator. An iterator is like a generator but instead of being a function it is an object. So it has state. I.e., you can store the current value of all those variables (nr, nn, q etc) as 'instance' variables. Then, when you want to terminate, you can persist the current state of the class using the 'pickle' library. Then, to continue the script where it left off, you load the pickle file to rebuild the object exactly as it was before the program terminated.