読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Project Euler Problem 14

Project Euler

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

http://projecteuler.net/problem=14

 

100万以下の数の中で最長のCollatz数列を見つける問題。

今回は時間を計測するためにtimeモジュールを使う。

----

import time
def collatz(x):
    count = 0
    while x != 1:
        if x % 2 == 1:
            x = x*3 + 1
        else:
            x /= 2
        count += 1
    return count


start = time.clock()
length = 0
ans = 0
for x in xrange(1,10**6):
    if collatz(x) > length:
        length = collatz(x)
        ans = x
end =time.clock()
print ans
print "Time:",end-start

----

これでも十分動くが、遅いのである。

Pythonで動かすと私の環境では約90秒かかってしまう。

ちなみに環境は

CPU:Intel Core 2 Duo 1.06GHz

メモリ:2.00GB

OS:Windows Vista

言語:Python

である。

 

Project Eulerの問題は60秒以内で解けるように設定されているのでアルゴリズムに問題がある可能性が高い。が、ひとまず棚上げして小手先な対策を考える。

1.ビット演算を行う

上記のソースのcollatz函数の部分を以下のように変える:

----

def collatz(x):
    count = 0
    while x != 1:
        if x & 1:
            x = x*3 + 1
        else:
            x >>= 1
        count += 1
    return count
----

偶奇判定と2で割るという操作をビットシフトで実装する。

これならどうか。計測してみると約77秒。効果はあったがもう少し早くしたい。

 

2.PyPyを使う。

PyPyはPythonによるPythonの実装である(実はあまり分かっていない)。

Pythonよりも高速で動作し、PyPyを使うと約10秒で計算できてしまう。

 

3.ビット演算+PyPy

なんと3秒で計算できてしまう。素晴らしい。

素晴らしいが、PyPyが何故早いのかをそれなりに理解してから喜ぶべきである。

Just - In - Timeコンパイラがポイントらしいがよくわからない。

 

ビット演算というとモンゴメリ法が浮かぶ。講義で習ったがよくわからなかった。