掛け算の実装

multi.ml

open Pervasives

(*
 例えば、掛け算は、「足し算をn回繰りかえす」と定義できる
 *)
let rec mul1 x n =
  if n == 1
  then x
  else x + (mul1 x (n - 1))

(*
 「ロシア農民のアルゴリズム」という考え方を持ちいれば、
  例えば、4x = (x + x) + (x + x) = 2x + 2x
  という考え方ができる。つまり、それぞれを
  半分に分割する。

  このとき、ビットシフトを利用すれば、半分にする
  ことが用意に簡単である。
 *)

let is_odd x = (x land 1 == 1)
let rec mul_lusia x n =
  if n == 1 then x
  else
    (mul_lusia x (n lsr 1))
    + (mul_lusia x (n lsr 1))
    + (if is_odd n then x else 0)

  (* 末尾最適化する *)

let mul n a =
  let rec mul_tailcall r n a =
    let if_odd_n =
      if is_odd n then r + a else r in
    if n == 1 then r + a
    else
      mul_tailcall if_odd_n (n lsr 1) (a + a)
  in
  if a == 1 then n
  else
    mul_tailcall n (if is_odd a then a - 1 else a) n

  (* これらは同様に乗の場合でも考えることができる。
     逐次平方という考え方はこれを参考にしている。

     逐次平方のアルゴリズムはx_nのとき

     (x_{n / 2})_2             if n is even
     x * (x_{n - 1})           if n is odd

     として記述される。

     例えば、7の5乗の場合

     (7 * (7 ))
   *)
let rec pow x n =
  if n == 0 then 1
  else if n == 1 then x
  else if n == 2 then mul x x
  else if is_odd n then mul (pow x (n - 1)) x
  else pow (pow x (n lsr 1)) 2

multi_test.ml

open OUnit2;;
open Multi;;

let test_mul1 test_ctxt =
  assert_equal 3 (mul 3 1);;
let test_mul test_ctxt =
  assert_equal 6 (mul 2 3);;
let test_pow0 test_ctxt =
  assert_equal 1 (pow 3 0);;
let test_pow1 test_ctxt =
  assert_equal 3 (pow 3 1);;
let test_pow72 test_ctxt =
  assert_equal 49 (pow 7 2);;
let test_pow75 test_ctxt =
  assert_equal 16807 (pow 7 5);;

let suite = "掛け算と逐次平方の実装" >:::
              ["1回だけかける" >:: test_mul1;
               "複数回かける" >:: test_mul;
               "xの0乗は1" >:: test_pow0;
               "xの1乗はx" >:: test_pow1;
               "7の2乗は49" >:: test_pow72;
               "7の5乗は16807" >:: test_pow75
               ];;

let () = run_test_tt_main suite;;