Problem14(2) -BigInt-

Ocaml 30分プログラム

30分プログラム、その279。Problem14 3n+1問題の続き。
昨日のプログラムにPrintfをしこんで追いかけてみると、一部でオーバーフローが発生しているため値が収束しなくなっていた。
そこで、OCamlの任意精度整数ライブラリ、BigIntモジュールを使ってみた。ただ、BigIntは

# (big_int_of_int 0) = (big_int_of_int 0);;
Exception: Invalid_argument "equal: abstract value".

のように=で比較できないので、Hashtblに突っこむことができない。そこでファンクターを使って、BigInt専用のハッシュテーブルを作った。

こんなにがんばったのに、BigIntじゃ遅すぎて解けなかった。やっぱりintの範囲を越えたときだけBigIntを使うようにする、みたいな仕組みが必要なんだろうな。OCamlをやめてPythonとかにすれば解決する問題な気もする。

使い方

$ ocamlopt nums.cmxa problem14-bigint.ml -o p14
$ ./p14
...

ソースコード

open Big_int

(* util *)
let ($) f g x = f (g x)
let (@@) f g = f g


(* big-int syntax sugar *)
let (/@)   x y = div_big_int x y
let ( *@ ) x y = mult_int_big_int x y
let (%@)   x y = mod_big_int x y
let (=@)   x y = eq_big_int x y
let (+@)   x y = add_int_big_int y x

(* sub function *)
let even n = (n %@ (big_int_of_int 2)) =@ (big_int_of_int 0)

(* BigInt Hash *)
module BigIntHash : Hashtbl.HashedType with type t = big_int = struct
  type t = big_int
  let equal x y =x =@ y
  let hash x = Hashtbl.hash x
end

module Hash = (Hashtbl.Make(BigIntHash) : Hashtbl.S with type key = big_int)

let table = Hash.create 10

(* collatz *)
let collatz n = 
  let rec loop n r =
    if Hash.mem table n then begin
      (Hash.find table n) + r
    end else if n =@ (big_int_of_int 1) then
      1+r
    else if even n then
      loop (n /@ (big_int_of_int 2)) @@ 1+r
    else
      loop (3 *@ n +@ 1) @@ 1+r
  in 
  let _ = Printf.printf "call %d\n" n in
  let _ = flush stdout in
  let n' = big_int_of_int n in
  let r = loop n' 0 in
    Hash.replace table n' r;
    r

let range a b =
  let rec f r a b = 
    if a = b 
      then r
      else f (a::r) (a+1) b
  in
    f [] a b

let solve _ =
  let f ((_,count) as x) m = 
    let count' = collatz m in
      if count < count' then
	(m,count')
      else
	x
  in
    List.fold_left f (0,0) @@ range 1 1_000_000;;

let _ = 
  let (x,y) =  solve () in
    Printf.printf "%d,%d\n" x y

参考