[これまでのコメントを反映するように編集し、さらに読んでください。]
質問: 次の 3 つのバージョンの eta 関数 (すべて Python で記述) がほぼ同じ速度、つまり "bound" で線形であり、同様の定数を使用している理由がわかりません。
ちょっとした背景として: 計算用の eta 関数のかなり高速なバージョンが必要でした。eta 関数の定義は、ここにあります。3 つの関数を指定する前に、単純なヘルパー関数が必要です。
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
今、私を困惑させている3つのバージョン。最初に、ヤコビのシータ関数に関する eta の定義から直接、明白なワンライナーがあります。
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)])
次に、ワンライナーの明らかな変更があります。リスト内包表記をジェネレーター式に置き換えます。
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)))
しかし、このバージョンはこれまでになくわずかに遅くなります。リスト内包表記をジェネレーターに置き換えると、なぜ遅くなるのでしょうか? 最後に、最初にコーディングしたバージョンを示します。これは非常に賢いと思いました。これは、二次的に大きな指数による累乗を回避するためです。
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
実際、このバージョンは以前の両方よりもわずかに高速です。しかし、これは線形になると思いましたが、ワンライナーは累乗のコストのために非常に遅くなります。しかし、そうではありません。タイミングは、それらのすべてがほぼ同様の定数を持つ「境界」で線形であることを示しています。Pythonでの操作のコストを理解していないと思います。