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:]))

• FodderOverflow: I do realize I have an inert counter in pispig now, but Ill leave unedited in spirit of code review.

Answer 1

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