素数判定
ある自然数が素数かどうかを判定するにはシンプルな方法があります。2以外で2で割り切れるならばそれは偶数です。3以上で奇数で割り切れるならばそれは合成数です。素数ではありません。これをその自然数の平方根に達するまで調べます。この結果、割り切れないならばそれは素数です。Lispコードで表すなら下記の通りです。
(defun coprimep (n s e)
(cond ((> s e) t)
((= (mod n s) 0) nil)
(t (coprimep n (+ s 2) e))))
(defun primep (n)
(cond ((= n 2) t)
((= (mod n 2) 0) nil)
(t (coprimep n 3 (isqrt n)))))
並列計算
この素朴な方法は大量の計算を要します。並列でこの計算を分担すれば計算時間を短縮できるはずです。Easy-ISLispにおいてこれに挑戦しました。マルチプロセスバージョンのprognであるmp-exec という並列構文が用意されています。しかし、これだと全部の引数について計算をしてしまいます。
(mp-exec (foo1) (foo2) (foo 3) (foo 4) (foo 5))
素数判定において分割した計算のいずれかにおいて素数ではないことが判明したのならば残りの計算は必要がありません。それは合成数であることがわかっているのですから、計算を終了させないと時間の無駄です。そこでmp-partという並列構文を用意しました。partial-execution に由来しています。
(mp-part (foo1) (foo2) (foo 3) (foo 4) (foo 5))
シグナルを利用する
mp-partの実装にあたってはUnixのシグナルを使いました。親Lispは子Lispに分割した計算を依頼します。子Lispは計算が終わったものから順次計算結果を返すとともにシグナルを親Lispに送信します。親Lispはこのシグナルを受信して子Lispからの計算結果を得ます。
もし、この計算結果がnilであった場合には親Lispはまだ計算途中の子Lispに対してctrl+cシグナルを送信します。計算途中の子Lispはこれにより計算を停止します。
並列構文による素数判定
このmp-partを利用した素数判定のコードは下記のようになります。
(defun primep* (n)
(cond ((= n 2) t)
((= (mod n 2) 0) nil)
(t (let* ((limit (isqrt n))
(span (div limit 5)))
(mp-part (coprimep n 3 span)
(coprimep n (near-odd span) (* 2 span ))
(coprimep n (near-odd (* 2 span)) (* 3 span))
(coprimep n (near-odd (* 3 span)) (* 4 span))
(coprimep n (near-odd (* 4 span)) limit))))))
(defun near-odd (n)
(if (= (mod n 2) 0)
(- n 1)
n))
(defun coprimep (n s e)
(cond ((> s e) t)
((= (mod n s) 0) nil)
(t (coprimep n (+ s 2) e))))
Easy-ISlispはコンパイラにおいて末尾再帰最適化をしています。コンパイルして計算をさせてみます。AMDのRyzenを積んだ6コアのマシンです。
大きな素数の判定では並列の効果が表れています。おおよそ5分の1の実行時間に短縮できています。
並列の時代
インテル、AMDなどの現在のCPUはマルチコアです。安価なマシンでも6コアを搭載しています。ゲーム用の高価なマシンでは２０コアが使われるようになっています。この高性能なCPUを活かさない手はありません。Lispにおいても並列を積極的に利用した方がよろしいと私は思っています。
Easy-ISLispはオープンソースです。Githubにおいて公開しています。
https://github.com/sasagawa888/eisl