MLton で素数判定 (3)

説明を丸投げしすぎて誰が読むのかわからなくなってきました。
あとタイトルを変えました。
第三回です。

前回挙げたミラー・ラビン法の手順をおさらいします(前回とはちょっと並び順を変えています)。
自然数 n を判定するとき、

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

前回は 2. の判定関数、one_test を書きました。
one_test を適当な回数評価する関数を書いていきます。

適当な回数とはどれくらいなんでしょう。いま決められないので、これを
引数に出します。この引数を k としましょう。
one_test が k 回すべて true を返せば n は素数だとほぼ決まりといっていいようです。
もし一度でも one_test が false を返したら、こちらは逆に n は素数でない
と言い切っていいようです。

リストの要素全てに関数を適用して、条件を満たすものが一個でもあれば true を返す
関数 List.exists が Standard ML の標準ライブラリにあるようです。
数をランダムに k 回選んで k 要素のリストにし、これに List.exists を適用したら
今回の関数は書けそうです。
型はドキュメントを見ればわかりますが、
一応 REPL で確認しておきます。

- List.exists;
val it = fn : ('a -> bool) -> 'a list -> bool

余談ですが、+ や mod などの演算子になっている関数も REPL で型を
確認できるようです。先頭に op をつけないといけないのが最初
わからなくてこれも地味にはまりました。

- op +;
val it = fn : int * int -> int
- op mod;
val it = fn : int * int -> int

でも andalso や orelse は op つけても確認できませんでした。

- op andalso;
= ;
= ;;
stdIn:39.4-40.2 Error: syntax error: deleting  ANDALSO SEMICOLON SEMICOLON
- andalso;;
= ;
stdIn:1.2-9.1 Error: syntax error: deleting  ANDALSO SEMICOLON SEMICOLON

では書いてみます。といきたいところですが、必要な処理を一つ
忘れていました。そうです。ランダムに数を選ぶ処理です。
[2, n - 1] を出力する乱数が必要です。

またね

といったところでお時間です。ここで切りますね。
なかなか実行するところまで進めません。