今回は前回のプログラムを改善します. プログラムは下手にいじると余計な問題を引き起こします. 特にバグが入り込んで正しかったプログラムがおかしくなりかねません.
既に正しく動いているプログラムを改善するには理由が必要です. ここでは大量に計算・実験するための高速化を理由・目的にします. そもそも何故高速化しなければいけないかを簡単に確認します.
既に動いているプログラムを直すとき, 正しく動いているプログラムがあるのなら, いつでも元に戻せるように必ずそのプログラムをバックアップしておきましょう. 具体的にはコピーして退避させておけば十分です.
もちろんあなたが一定以上プログラミングに詳しいなら, Gitなどのバージョン管理ツールを使うべきです. ここではバージョン管理, 特にGitの解説は目的ではないので省略します. Gitもいろいろな本もあれば資料もネット上に大量にあります. 興味があれば調べてみてください. プログラミングと同じく慣れれば本当に便利です.
一言で言えば大きな数を計算したり, 人力では処理しきれないほどに膨大な計算をさせたいからです. 計算が速ければ速いほどコンピューターが処理できる計算も増えます. 工学的な計算ではスパコンが必要なほどで凄まじい計算量が必要なのはイメージしやすいでしょう. 数学に関してもちょっとした計算ですぐに膨大な時間がかかるようになります. 素数判定がまさにその例なのです.
私の他のコンテンツでも紹介していますし, このコンテンツでもあとで紹介するように, 素数判定の応用として素因数分解があり, 素因数分解を基礎にした暗号理論があります.
例えば暗号理論では巨大な素数が出てきます.
どのくらい大きいかというと1000桁に及ぶレベルの素数です.
コンピューターを使って計算するのが大変な事情を使って暗号の強度を保証しているため,
もちろん簡単に計算しきれる対象ではありません.
改善の前にどのくらい時間がかかるのが実体験してみましょう.
高速化にもいろいろあります. そしてここでもいくつかの高速化法・視点を紹介します. まずは合成数の判定処理を高速化し, そのあとに素数の判定処理を高速化します.
解説はあとにして次の関数を考えます.
def is_prime_ver2(n):
b = True
i = 2
while i < n:
if n%i == 0:
b = False
break
i = i+1
return b
前回と違って直接素数か判定する関数です.
そしてくり返しはforではなくwhileで表しています.
書き換えたので簡単に挙動を確認しましょう.
for n in range(2, 40):
if is_prime_ver2(n):
print(f"{n}: This is prime!")
2: This is prime! 3: This is prime! 5: This is prime! 7: This is prime! 11: This is prime! 13: This is prime! 17: This is prime! 19: This is prime! 23: This is prime! 29: This is prime! 31: This is prime! 37: This is prime!
素数だけ結果を出力するようにしました.
解説する前にまずは高速化されているか確認しましょう.
実は素数かどうか判定する部分は高速化されておらず, 合成数かどうかの判定が速くなっています.
かんじんの「素数」の判定が速くなっていなくては意味がないのでは?
あなたはこう思っているかもしれません.
しかし, 実際上で確認用のfor文を書いたように,
同じ関数で合成数判定をさせる機会もあります.
合成数だけの高速化でも嬉しい状況はよくあります.
def is_prime_ver1(n):
b = False
for i in range(2, n):
b = (n % i == 0) or b
return not b
余計な確認用出力は消した上,
最後にnotで真偽を判定させて直接的に素数判定するように変えています.
for n in range(2, 40):
if is_prime_ver1(n):
print(f"{n}: This is prime!")
2: This is prime! 3: This is prime! 5: This is prime! 7: This is prime! 11: This is prime! 13: This is prime! 17: This is prime! 19: This is prime! 23: This is prime! 29: This is prime! 31: This is prime! 37: This is prime!
もう一つ, ver1とver2で同じ結果が得られるかも直接確認します.
for n in range(2, 40):
if is_prime_ver1(n) == is_prime_ver2(n):
print(f"{n}: The result is same!")
else:
print(f"{n}: The result is different!")
2: The result is same! 3: The result is same! 4: The result is same! 5: The result is same! 6: The result is same! 7: The result is same! 8: The result is same! 9: The result is same! 10: The result is same! 11: The result is same! 12: The result is same! 13: The result is same! 14: The result is same! 15: The result is same! 16: The result is same! 17: The result is same! 18: The result is same! 19: The result is same! 20: The result is same! 21: The result is same! 22: The result is same! 23: The result is same! 24: The result is same! 25: The result is same! 26: The result is same! 27: The result is same! 28: The result is same! 29: The result is same! 30: The result is same! 31: The result is same! 32: The result is same! 33: The result is same! 34: The result is same! 35: The result is same! 36: The result is same! 37: The result is same! 38: The result is same! 39: The result is same!
どうやら結果は一致しているようです.
39までしか確認していないので完全一致まで確認していない点には注意してください.
実際に速度比較してみましょう. 大きい数でないとわかりにくいため, 意図的に大きな数を選んでいます. そして統計的なゆらぎを消すために複数回の平均や偏差を調べるべき部分もさぼっています. 興味があればぜひご自分でいろいろ調べてみてください. 性能テストから簡単な統計学入門するのも楽しいかもしれません.
%%time
is_prime_ver1(1000000)
CPU times: total: 234 ms Wall time: 232 ms
False
%%timeはipythonの時間測定補助コマンドで便利です.
必要に応じて%%timeitも使ってみてください.
実行時間は環境に依存します.
私が手元のマシンで実験したときは250msかかっていました.
%%time
is_prime_ver2(1000000)
CPU times: total: 0 ns Wall time: 0 ns
False
新しいバージョンは0nsと出ました.
まさに一瞬で終わっています.
後で説明するようにいつでもそうとは限らないものの,
ここで見たサンプルに関しては合成数判定に関しては猛烈な高速化が実現できています.
素数でどうなるか確認します. 結論から言えば変わりません. 合成数判定と同じく, 同じ数で確認します.
%%time
print(is_prime_ver1(100003))
True CPU times: total: 15.6 ms Wall time: 17 ms
%%time
print(is_prime_ver2(100003))
True CPU times: total: 15.6 ms Wall time: 21 ms
統計的なばらつきをおさえていないため, 古い関数の方が速く出る場合もあります. 理論上はどちらも同程度の速度しか出ません.
ここでは数学的な事情を使って合成数判定を高速化しました. まずは関数を再掲します.
def is_prime_ver1(n):
b = False
for i in range(2, n):
b = n % i == 0 or b
return not b
def is_prime_ver2(n):
b = True
i = 2
while i < n:
if n%i == 0:
b = False
break
i = i+1
return b
見かけに惑わされず処理の内容を確認すると,
ver2ではくり返し処理の中でn%i == 0を満たしたときにwhileをbreakしています.
このbreakは本来の終了タイミングの前にくり返しを強制的に終わらせる文(符丁)です.
そしてn%i == 0が正しいのは素数判定したいnがiで割り切れたとき,
つまりnはiを因数に持つ合成数であるときです.
一度合成数だとわかったならそれ以上素数判定処理を続ける必要はないので,
処理を打ち切ったのがifの中のbreak文です.
上の例でver1より圧倒的に高速化されたのは確認したnが偶数で,
i=2の最初で合成数判定が終わったからです.
こう考えると必ずしもver2が何万倍も速いとは限らないときもわかります.
小さい因数を持っていれば速い時点で処理を打ち切れるため速くなります.
しかし因数が大きいとそこまで処理を続ける必要があって時間が伸びます.
定義によって自分より小さい数を全て確認しなければならないため,
素数かどうかの確認時間は変わりません.
合成数の場合は判定処理が途中で打ち切れます.
この数学的事情をプログラムに組み込んだのがis_prime_ver2()です.
今回の範囲では合成数の場合しか高速化できていません.
もちろん素数判定自体をもっと高速化する方法があります. 次回も純粋に数学的な事情による高速化を検討します.