[Edited to reflect the comments so far, and my further reading.]
Question: I'm confused why the following three versions of the eta function,all written in python, are all about the same speed, namely linear in "bound", and with similar constants.
As a bit of background: I needed a reasonably fast version of the eta function for a computation. The definition of the eta function can be found here. Before giving the three functions, we need a simple helper function.
def chi(n): # Dirichlet character
n = n%12
if n == 1 or n == 11:
return 1
if n == 5 or n == 7:
return -1
return 0
Now the three versions that are puzzling me. First we have the obvious one-liner, direct from a definition of eta in terms of Jacobi theta functions.
def eta_Dedekind_theta(tau, bound = 50):
assert tau.imag > 0
r = Exp(Pi*I*tau/12)
# sum_1^infty chi(n) r^(n^2)
return sum([chi(n)*r**(n**2) for n in range(1,bound+1)])
Second we have the obvious modification of the one-liner: replace the list comprehension with a generator expression.
def eta_Dedekind_theta_round(tau, bound = 50):
assert tau.imag > 0
r = Exp(Pi*I*tau/12)
# sum_1^infty chi(n) r^(n^2)
return sum((chi(n)*r**(n**2) for n in range(1,bound+1)))
But this version is ever so slightly slower - why does replacing the list comprehension with a generator slow things down? Finally, here is the version I coded first. I thought this was very clever, as it avoids exponentiation with quadratically large exponent.
def eta_Dedekind_theta_clever(tau, bound = 50):
assert tau.imag > 0
r = Exp(Pi*I*tau/12)
r2 = r**2
lin = 1
quad = r
sum = 0
# sum_1^infty chi(n) r^(n^2)
for n in range(1, bound+1):
sum = sum + chi(n)*quad # n^2
lin = lin*r2 # 2n
quad = quad*lin*r # n^2 + 2n + 1 = (n+1)^2
return sum
Indeed, this version is ever so slightly faster than both of the previous. But I thought that this would be linear while the one-liners would be very slow due to the cost of exponentiation. But that is not the case: timings show that all of them are linear in "bound" with roughly similar constants. I guess I don't understand the cost of operations in python.