MLton 使ってみる (2)
やっつけ記事の二回目です。
前回、
という話をしました。
ではコードを書いていきましょう。
コード
ミラー・ラビン法は大雑把にいうと、n が素数かどうか判定するときに、
というのを適当な回数繰り返すという手順になります*1。
なので、まず を計算する関数から書いていきます。
こんな感じになりました。
fun one_test a n = let fun expmod k 0 m = 1 mod m | expmod k 1 m = k mod m | expmod k q 1 = 0 | expmod k q m = if q mod 2 = 0 then let val half = expmod k (q div 2) m val square = (half * half) mod m in if square = 1 andalso half <> 1 andalso half <> (n - 1) then 0 else square end else (k * expmod k (q - 1) m) mod m in 1 = expmod a (n - 1) n end
one_test という名前がいいかどうかはさておいて。
expmod k q m は を計算する関数です。
one_test からしか使わないので、one_test の中に入れました。
one_test a n は expmod a (n - 1) n の値が 1 に等しければ true、
そうでなければ false を返します。
パターンマッチが使えると if 文が減って簡潔に書けていいです。
OCaml と違って再帰呼び出しする関数でもキーワードで明示しなくてもいいのですね。
let ... in 本体 のあとに end がいるのに気づかなくて地味にはまりました。
コードは Emacs で書いているのですが、M-x run-sml で REPL を起ち上げておいて、
C-c C-l で読み込ませて動作を確認しながら実装を進める、というのが
やりやすかったです。
ただ、MLton は REPL を持っていないので、REPL 用に別の Standard ML
処理系をインストールしておく必要があります。
今回は、homebrew から SML/NJ をインストールしておきました。
ちょっと確認してみます。
- one_test 3 5; val it = true : bool - one_test 3 4; val it = false : bool - one_test 6 7; val it = true : bool
よさそうです。
またね
といったところでお時間となってしまいました。長くなりましたしね。
(あと喫茶店のひとの視線がそろそろ怖くなってきたので)
次回はランダムに数を選んで、one_test を繰り返し評価する関数を書きます。
ついでに MLton でライブラリをインポートするのが面倒くさかった、
という話を書きます。