MLton 使ってみる (2)

やっつけ記事の二回目です。

前回、

  • 素数を列挙するコードを書く
  • 判定にミラー・ラビン法を使う
  • ミラー・ラビン法の実装は SICP がわかりやすかった

という話をしました。


ではコードを書いていきましょう。

コード

ミラー・ラビン法は大雑把にいうと、n が素数かどうか判定するときに、

  1. [2, n - 1] から自然数を一つランダムに選ぶ。選んだ数を a とする
  2. 選んだ a についてa^{n - 1} \equiv 1\pmod{n}が成り立つか計算する
  3. 成り立たなければ n は素数ではない。ここで終了
  4. 成り立てば 1. に戻る

というのを適当な回数繰り返すという手順になります*1


なので、まずa^{n - 1} \equiv 1 \pmod{n} を計算する関数から書いていきます。
こんな感じになりました。

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 は k^{q} \pmod{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 でライブラリをインポートするのが面倒くさかった、
という話を書きます。

*1:ミラー・ラビン法の詳細について、実はよくわかってないです。フェルマの小定理の式を変形したものから導けるらしい、ということ、一回の計算では決められないこと、何回か計算して信頼度を上げていく手法であること、くらいしかわかっていません