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:
40 20 10 5 16 8 4 2 1It 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
言語：Python
である。
Project Eulerの問題は60秒以内で解けるように設定されているのでアルゴリズムに問題がある可能性が高い。が、ひとまず棚上げして小手先な対策を考える。
１．ビット演算を行う
上記のソースの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秒。効果はあったがもう少し早くしたい。
２．PyPyを使う。
PyPyはPythonによるPythonの実装である（実はあまり分かっていない）。
Pythonよりも高速で動作し、PyPyを使うと約10秒で計算できてしまう。
３．ビット演算＋PyPy
なんと3秒で計算できてしまう。素晴らしい。
素晴らしいが、PyPyが何故早いのかをそれなりに理解してから喜ぶべきである。
Just - In - Timeコンパイラがポイントらしいがよくわからない。
ビット演算というとモンゴメリ法が浮かぶ。講義で習ったがよくわからなかった。
