Problem14(3) -64bit-

OCaml 30分プログラム

30分プログラム、その280。osiireさんのアドバイスを試してみる。

知ってるとは思うけど、64bitCPUならOCamlのintは63bitまで使えますよ。
bigint使わなくても解けたりしない？

iMac G5だから64ビットのはずなんだけどなぁ、と思いつつ調べてみると、コンパイル時にオプションを指定してやらないとダメらしい。

http://jijixi.azito.com/cgi-bin/diary/index.rb?date=20070518#p04

しょうがないので、ソースコードからビルドし直した。

$ ./configure -cc "gcc -arch ppc64" 
$ make world
$ make opt
$ make install

Sys.word_sizeもちゃんと64になっている。なぜかバージョン番号が表示されない。特に支障はないので放置でいいかな。

$ ocaml
        Objective Caml version

# Sys.word_size;;
- : int = 64

この64bit版OCamlで動かしたら、あっさり解けた。64ビットすごい。

使い方

$ ocamlopt problem14.ml -o p14
$ file p14
p14: Mach-O 64-bit executable ppc64
$ time ./p14
collatz(837799) = 525
./p14  8.10s user 0.30s system 82% cpu 10.198 total

ソースコード

前に書いたコードとほぼ同じ。

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

let even n = (n mod 2) = 0

let table = Hashtbl.create 10

let collatz n = 
  let rec loop n r =
    if Hashtbl.mem table n then begin
      flush stdout;
      (Hashtbl.find table n) + r
    end else if n = 1 then
      r+1
    else if n < 0 then
      failwith "overflow"
    else if even n then
      loop (n/2) (1+r)
    else
      loop (3*n+1) (1+r)
  in 
    let r = loop n 0 in
      Hashtbl.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 500_000 1_000_000;;

let _ = 
  if not !Sys.interactive then begin
    let (x,f) = solve () in
      Printf.printf "collatz(%d) = %d\n" x f
  end

参考