Pythonの応用3 〜数値計算の高速化〜

コンピュータによる数値計算は、手計算では解を求めることができないような複雑な問題であっても、 計算誤差の範囲内で近似的に解くことができる。 そのため現代の科学技術を支える非常に強力な手段である。 しかしながら、多くの場合すぐに計算量が膨大になり、現実的な時間内に計算が終わらなくなってしまう。 それを克服するためには、アルゴリズムを工夫して意味のない計算を省略するなどして、 計算時間を短くすることが必要である.

この章では素数の探索という簡単な例を用いて, 数値計算の高速化を体験する.

素数探索

素数とは1と自分以外に約数をもたない自然数のことである. ここでは, 計算機を用いて膨大な数の素数をいかに速く求めるかを目指す.

課題1

ある自然数\(n\)を与え, それを\(n-1\)までの自然数で割り算することにより, \(n\)が素数かどうかを判定する関数を作成せよ. （ヒント：余りを計算するためには%を用いる。例えば、5を3で割った時の余りは以下のようにして求めることができる。）

5 % 3

2

課題2

上記の関数を用いて、 10,000番目の素数の値を求めるプログラムを作成せよ.

実行速度の計測

次に、上で作成したプログラムの高速化に取り組む.

プログラムの高速化を行うためには、やみくもに試行錯誤を行なうのではなく、 どの計算に時間がかかっているか(ホットスポットと呼ばれる)を調べ、 多くの計算時間が費やしている部分を重点的に改善することが必要である。

プログラムの実行時間は, TimeパッケージのTime関数により得ることができる. 以下に, 計算時間を計測するプログラムの一例を示す.

import numpy as np
import time

# 計算実行前の時間を取得する。この関数の戻り値はある基準時間から何秒経ったかを返す。
before = time.time()

# sin(1.2) を1000回計算する
for i in range(1000):
    rslt = np.sin(1.2)

# 計算実行後の時間を取得する
after = time.time()
# 差を表示する。なお、`str()` 関数は、引数内の値を文字列に変換する関数である。
print('Calculation took ' + str(after - before) + ' s')

Calculation took 0.0008683204650878906 s

課題3

• 10,000 番目の素数を探索するのに必要な時間を計測するプログラムを作成せよ。
• \(i\)番目の素数の探索にかかった時間\(t(i)\)をグラフに描画し、その様子から素数探索にかかる時間の特徴を考察せよ。
• 上での考察を元にアルゴルズムを工夫し、10,000 番目の素数を探索する高速なプログラムを作成せよ。 もし10,000 番目の素数を1秒以内に見つけることができれば、100,000番目の素数探索にも挑戦せよ。