OCaml/SICP-1c

練習問題の概要と解答案 (1章)

正解かどうかの保証はしない。問題の解釈を間違えている可能性もある。

1.21

いまなら golf しそうな問題だ。(ここに書いているのは数ヶ月前に書いたストック品)

let isdivide a b = ((b mod a)=0)
let rec find_divisor n tdiv =
  if tdiv*tdiv > n then n
  else if isdivide tdiv n then tdiv
  else find_divisor n (tdiv + 1)
let smallest_divisor n = find_divisor n 2
let isprime n = (n = smallest_divisor n)

19999 は 7 で割れるよ。後は素数。

1.22

実行時間をはかる runtime (OCaml の場合は Unix.time 関数で得られるものに相当) を用いて、素数テスト手続きの実行時間を計測する。 実行時間は値の増加に対してどうなるか？ log オーダになるか確認せよ。

#load "unix.cma";;
open Unix
let runtime () = (times ()).tms_utime

let start_prime_test n starttime =
  let report_p elapsed =
    let _ = print_string " *** " in
      print_float elapsed in
  if isprime n then report_p ( (runtime ()) -. starttime )

let prime_test_t n =
  let _ = print_string "\n" in
  let _ = print_int n in 
    start_prime_test n (runtime ())

let rec search_for_prime n =
  if n mod 2 = 1 then 
    let _ = prime_test_t n in
      search_for_prime (n+2)
  else search_for_prime (n+1)

1.23

速度の確認が面倒なのでパス。

1.24

フェルマーテストに変えたらどれだけ早くなるか。また、log オーダーか、そうでなければその理由を説明できるか。

てか、カーマイケル数の問題があるからフェルマーテストじゃそもそもダメなんだよね。

• > 問題 1.27 参照。

パス。

1.25

掛け算のコストが猛烈に上がっていくから速くなるとは限らない。少なくとも空間コストは大きくなるな。

多倍長整数やさんは無意識的に除外するコースだ。

1.26

メモ化しないとトンでもないことになるのは分かるな。 expmod の評価回数が爆発する。

1.27

カーマイケル数出てきたな。パス。

1.28

ミラーラビン法による強擬素数判定ですな。普通は試し割りの後にこれをやって、強擬素数なら APRT-CL 判定に持ち込むのがパターン。

let miller_rabin n b = 
  let rec miller_rabin_sub_test n b s r = 
    if r >= s then false
    else 
      let eb = mod_num b n in
        if eb =/ (pred_num n) then true
        else miller_rabin_sub_test n (eb*/eb) s (r+1)
  in
  let rec miller_rabin_sub n t s b =  (* n = 2^s * t , in SPSP(b) *)
    if (mod_num t (num_of_int 2))=(num_of_int 0) then
      miller_rabin_sub n (t//(num_of_int 2)) (s+1) b
    else (* body of miller_rabin *)
      let expmb = calc_exp_modn b t n in
        if expmb =/ (num_of_int 1) then true (*SPSP*)
        else miller_rabin_sub_test n expmb s 0
  in
    miller_rabin_sub n (pred_num n) 1 b ;;

1.29

シンプソンの公式、は放物線近似だっけ。台形公式がすっとばされてる気がするがー。

let simpson f a b n =
  let h = (b -. a)/. float n in
  let rec simpson_o f i =
    if i<n   then 4. *. f(h*.float i+.a) +. (simpson_o f (i+2)) else 0. in
  let rec simpson_e f i =
    if i<n-1 then 2. *. f(h*.float i+.a) +. (simpson_e f (i+2)) else 0. in
    (f a +. f b +. (simpson_o f 1) +. (simpson_e f 2)) *. h /. 3.

末尾再帰になってないけど。

1.30

let sum term a next b =
  let rec iter a result =
    if a>b
    then result
    else iter (next a) (result + term a)
  in
    iter a 0