Bounded spigot algorithms for e and pi in Python

Question

I've written bounded spigot algorithms(Spigot Algorithm) for e and pi. I would like to understand if there is anything I can do to make this more efficient. I've done things already like move the carry over check to the very end, precompute values etc.

You run the functions and pass it the number of digits you want i.e. print(pispig(1000))`

The spigot algorithm for computing functions you can apply a Horner schema to is one of the coolest things I have ever learned.

def espig(n):
    estr = '2.'
    (multq, asum, carover) = (0, 0, 0)
    prec = 10 ** n
    (remainders, tsum) = ([], [])
    b = [x for x in range(2, n + 1)]
    init = [1 for x in range(2, n + 1)]
    x10 = [prec * x for x in init]
    while True:
        for (x, y) in zip(reversed(b), x10):
            asum = carover + y
            remainders.insert(0, asum % x)
            tsum.insert(0, asum)
            multq = asum // x
            carover = multq
        estr += str(int(tsum[0] // 2))
        x10 = [prec * x for x in list(reversed(remainders))]
        (carover, asum) = (0, 0)
        (remainders, tsum) = ([], [])
        if len(estr) > n:
            break
    return estr


def pispig(n):
    e = n
    xfact = 10 ** e
    n = int(round(3.4 * n))
    prec = n // 3.4
    (pilist, remainders, tsum) = ([], [], [])
    (multq, asum, carover, counter) = (0, 0, 0, 0)
    a = [x for x in range(n)]
    b = [2 * x + 1 for x in range(n)]
    init = [2 for x in range(1, n + 1)]
    x10 = [xfact * x for x in init]
    while True:
        for (A, B, R) in zip(reversed(a), reversed(b), reversed(x10)):
            asum = carover + R
            remainders.insert(0, asum % B)
            tsum.insert(0, asum)
            multq = asum // B
            carover = multq * A
        pilist.append(tsum[0] // 10)
        remainders[0] = tsum[0] % xfact
        x10 = [10 * x for x in list(remainders)]
        (carover, asum) = (0, 0)
        (remainders, tsum) = ([], [])
        if len(''.join([str(x) for x in pilist])) > prec:
            break
    for D in reversed(pilist):
        counter = 0
        if D >= xfact:
            pilist[pilist.index(D) - 1] += 1
            pilist[pilist.index(D)] = pilist[pilist.index(D)] % xfact
            counter += 1
    return str('3.' + ''.join(str(x) for x in pilist[1:]))

I do realize I have an inert counter in pispig now, but Ill leave unedited in spirit of code review. — FodderOverflow
– FodderOverflow, Commented Nov 16, 2020 at 16:11

Eman Yalpsid · Accepted Answer · 2020-11-16 23:17:37Z

About the first function. If you are so inclined, apply these ideas to the second one too.

Generally I'd love to see more descriptive variable names, comments, a docstring. I tried to stick to your algorithm/implementation as much as possible, i.e. I'm just playing the role of a linter here.

That being said.

Why

while True:
  ....
  if len(estr) > n:
     break

instead of

while len(estr) <= n:
  ....

?

Why

        asum = carover + y
        remainders.insert(0, asum % x)
        tsum.insert(0, asum)
        multq = asum // x
        carover = multq

instead of

        asum = carover + y
        tsum.insert(0, asum)
        divx, modx = divmod(asum, x)
        remainders.insert(0, modx)
        carover = divx

?

Why not move

    (carover, asum) = (0, 0)
    (remainders, tsum) = ([], [])

to the start of the loop, so that you can remove these from before the loop.

Why not write e.g.

carover, asum = 0, 0

instead, and lose the parens?

Why build an inner list in

x10 = [prec * x for x in list(reversed(remainders))]

instead of just using the iterator

x10 = [prec * x for x in reversed(remainders)]

?

Why cast to int after integer division? You shouldn't need the int in the following:

int(tsum[0] // 2)

Why reverse b, remainders? Why not construct them so that they are "reversed" by default:

b = list(range(n, 1, -1))

remainders.append(asum % x)

To maintain symmetry, let us do the same to tsum:

estr += str(tsum[-1] // 2)

tsum.append(asum)

Why do we need multq = 0? Why do we need multq at all?

You don't use tsum, only its first value. I don't think there's a need to build b either.

OK, so far we have something like the following:

def espig(n):
    estr = '2.'
    prec = 10 ** n
    ys = [1 for _ in range(2, n + 1)]
    
    while len(estr) <= n:
        carover, asum, remainders = 0, 0, []
        
        for x, y in zip(range(n, 1, -1), ys):
            asum = carover + prec * y
            carover, remainder = divmod(asum, x)
            remainders.append(remainder)
        
        ys = remainders
        estr += str(asum // 2)

    return estr

Stack Exchange Network

Bounded spigot algorithms for e and pi in Python

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Bounded spigot algorithms for e and pi in Python

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions