Pythonで漸化式 - likr’s labo

第n番目の素数の近似値を求める漸化式は次のように与えられます．

$Q_{n+1} = Q_n + \frac{Q_nlogQ_n}{Q_n - {Q_n^{1/2}}/2 - {Q_n^{1/3}}/3}(Q_1=2)$

この漸化式の第n項を求めるために，Pythonで漸化式の第n項を高速に求める実装を考えてみました．まず初めに検討したことはreduceで書くべきなのか，通常のループ構文で書くべきかということです．Pythonはインタプリタ言語なので素直にループを書いても十分なパフォーマンスを引き出せない場合が多々あります．

#!/usr/bin/env python2.6
import math
import functools
    
def approximate_prime1(n):
    def rec(a, i):
        return q + q*math.log(q) / (q - q**0.5/2 - q**0.333333333333/3)
    return functools.reduce(rec, range(2, n+2)

def approximate_prime2(n):
    q = 2
    for i in range(n-1):
        q = q + q*math.log(q) / (q - q**0.5/2 - q**0.333333333333/3)
    return q

結果としては通常のループで実装したapproximate_prime2の方が若干高速でした．reduce本来の使い方とはずれている気がするのでこんなものでしょうか．

それでは，ループの実装をもう少しチューニングしてみましょう．ここで検討してみたことは次の2点です．

whileで書き換えるとどうなるか
xrangeを使うとどうなるか

コードの変更としてはささいなものなので掲載しません．結果として，速度は次の順番になりました．
for(xrange) > while > for(range)
Python2系ではrangeはリストを返すのに対して，xrangeはイテレータを返します．リストの実体を生成する必要がない分xrangeの方が高速なのでしょう．ちなみにPython3.0からはxrangeが廃止され，rangeがイテレータを返すようになります．

一応最終版のコードを掲載します．
なお，今回得られた結果はマイナーなバージョンの変化やプラットフォームの変化で左右する可能性がありますので注意してください．

#!/usr/bin/env python2.6
import math

def approximate_prime(n):
    q = 2
    for i in xrange(n-1):
        q = q + q*math.log(q) / (q - q**0.5/2 - q**0.333333333333/3)
    return q