kineticcat_
kineticcat_

Reputation: 167

Pi spigot algorithm occasionally gives wrong values

I have made a script to implement the algorithm described by this, and it works for the vast majority of digits, but every so often it gets a couple digits wrong.

It usually seems to have a pattern of getting a digit or two 1 too low, then the next digit is 10 instead of 0, before continuing on correctly until it does it again.

This table shows a couple instances of it happening:

mine actual index
4 5 32
10 0 33
7 8 85
10 0 86
6 7 167
10 0 168
def denom(n): return 2*n+1
def nume(n): return n

count = 10000

array = [2]*count
carry = [0]*count
carried = [0]*count
remainder = [0]*count
quotient = [0]*count

pi = "<1000 digits of pi have been excluded>"

idx = 0

while True:
    array = list(map(lambda x:10*x, array))
    for i in range(count):
        i = count-1-i
        
        carried[i] = array[i] + carry[i]
        
        if i == 0:
            remainder[i] = carried[i] % 10
            break
        else:
            remainder[i] = carried[i] % denom(i)
        quotient[i] = carried[i] // denom(i)
        carry[i-1] = quotient[i] * nume(i)
    if not int(pi[idx]) == carried[i] // 10:
    # if True:
        print(carried[i] // 10, end="  ")
        print(pi[idx], end="  ")
        print(idx+1)
    if idx == 610:
        break
    array = remainder
    carry = [0]*count
    carried = [0]*count
    remainder = [0]*count
    quotient = [0]*count
    


    idx += 1

It looks like the "10"s are the code trying to carry into the previous digit, but while that makes sense, I thought the whole point of a spigot algorithm was that you could compute any digit on its own, whereas here I would have to compute more digits after to watch for carries?

Upvotes: 2

Views: 56

Answers (0)

Related Questions