A fast (but hard-to-read) implementation of Reciprocal fibonacci constant calculator in python. This was a UofT CSC373 assignment.

reciprocal_fib.py

import array

import sys
import cProfile

# input

OutputCount = int(sys.argv[1])

# object init

NextIndex = 0
Entry_D = []
Entry_R = []
Entry_I = array.array('i')
Entry_M = array.array('i')

# calculation init

MultiplyOrder = 100
Multiply = pow(10, MultiplyOrder)
Multiply2 = Multiply * Multiply
F1 = 1
F2 = 2
X1 = 3
X2 = 4
CurrentResult = -1
CurrentEx = 1
CurrentTotalEx = 1
LinkHead = -1
EntryCount = 0

Reverser = []

# Helper

def AddEntry(d, r):
    global Entry_R, Entry_D, Entry_M, Entry_I
    global X1, X2
    global NextIndex, EntryCount, LinkHead

    index = NextIndex
    NextIndex += 1
    EntryCount += 1
    if (index & 1) == 1 and index >= 3:
        oldIndex = (index - 3) // 2
        i = Entry_M[oldIndex]
        div = X2
        X2 += X1
        X1 = div
        Entry_R[i] = Entry_R[i] * div + r
        Entry_D[i] = d
        Entry_I[i] = index
        Entry_M.append(i)
    elif LinkHead != -1:
        nextHead = Entry_I[LinkHead]
        Entry_D[LinkHead] = d
        Entry_R[LinkHead] = r
        Entry_I[LinkHead] = index
        Entry_M.append(LinkHead)
        LinkHead = nextHead
    else:
        Entry_M.append(len(Entry_D))
        Entry_D.append(d)
        Entry_R.append(r)
        Entry_I.append(index)

def RemoveEntry(index):
    global Entry_D, Entry_I, LinkHead, EntryCount

    Entry_D[index] = 0
    Entry_I[index] = LinkHead
    LinkHead = index
    EntryCount -= 1

def StepEntry(index):
    global Entry_D, Entry_R
    global Multiply

    if Entry_D[index] == 0:
        return 0
    ret, Entry_R[index] = divmod(Entry_R[index] * Multiply, Entry_D[index])

    if Entry_R[index] == 0:
        RemoveEntry(index)
    return ret

def NextSegment():
    global MultiplyOrder, Multiply, Multiply2
    global CurrentTotalEx, CurrentEx, CurrentResult
    global F1, F2

    MultiplyOrder += 1
    Multiply *= 10
    Multiply2 *= 100

    lastTotalEx = CurrentTotalEx
    lastEx = CurrentEx
    CurrentTotalEx *= Multiply
    CurrentEx *= Multiply
    CurrentResult *= Multiply

    while F2 < CurrentTotalEx:
        AddEntry(F2, lastTotalEx)
        tmp = F1
        F1 = F2
        F2 += tmp

    for i in range(len(Entry_D)):
        CurrentResult += StepEntry(i)

    if CurrentEx - CurrentResult > Multiply2 * (EntryCount + 2):
        ret, CurrentResult = divmod(CurrentResult, lastEx)
        CurrentEx //= Multiply
        return True, ret
    return False, 0

# Main

def Main():
    global OutputCount
    global MultiplyOrder, Reverser

    while True:
        hasValue,val = NextSegment()
        if hasValue:
            for i in range(MultiplyOrder):
                val,r = divmod(val, 10)
                Reverser.append(r)
            for i in range(MultiplyOrder - 1, -1, -1):

                #sys.stdout.write(str(Reverser[i]))
                #print(Reverser[i])
                OutputCount -= 1
                if OutputCount == 0:
                    return
            sys.stdout.flush()
            Reverser.clear()

#Main()
cProfile.run('Main()')
#print("")