32bitのintでは足りない時のBig_int

はじめに

OCamlでProject Eularを解き進めていますが、「50桁の整数」とか「1000の1000乗」とかいう値が平気で出てくるのです。もちろん、こういった数をまともに扱わなくても解けるような解法があるのですが、しかし扱わなければならない時もあります。でもOCamlのintは32bit（OCamlでは正の整数値なら30bit分だっけ？）なので全然足りません。こまったーと言っていたら id:camlspotter 先生からこんなリプライを戴きました。

@camlspotter : @ymotongpoo そこでビッグ(マグ)ナム黒岩先生の登場です!!

http://twitter.com/camlspotter/status/12496323293

そこでBig_intと言ったモジュールを使います。

参考

• The num library: arbitrary-precision rational arithmetic
  • Big_int

サンプル

エラトステネスの篩を書いてみました。

open Big_int

let nums limit =
  let rec nums accu = function
    | n when n = zero_big_int -> accu
    | n -> nums (n::accu) (pred_big_int n)
  in
  nums [] limit
;;

let primes limit =
  let sift n l = List.filter (fun x -> x mod n <> zero_big_int) l in
  let rec sieve accu ns =
    match accu, ns with
    | _, [] -> accu
    | r::rs, xs when (mult_big_int r r) > (bottom xs) -> List.rev_append accu ns
    | accu, x::xs -> sieve (x::accu) (sift x xs)
  in
  sieve [] (nums limit)
;;

コンパイルするときはこんな感じで。

$ ocamlopt nums.cmxa hoge.ml

OMake使ってるときは

FILES[] =
   hoge

PROGRAM = hoge
# OCAML_LIBS += nums
# OCAML_CLIBS +=
OCAML_OTHER_LIBS += nums
# OCAML_LIB_FLAGS +=

.DEFAULT: $(OCamlProgram $(PROGRAM), $(FILES))

clean:
  rm -f $(filter-proper-targets $(ls R, .))

疑問を持っています

パターンマッチがしょぼいです

さっきの篩の例だとこんな感じに書きました。

let nums limit =
  let rec nums accu = function
    | n when n = zero_big_int -> accu  <-- ここがなんとなく違和感
    | n -> nums (n::accu) (pred_big_int n)
  in
  nums [] limit
;;

でも普通のintであれば普通に値を入れればmatchできます。なんかwhenを使わない良い書き方があれば良いのですが。

let nums limit =
  let rec nums accu = function
    | 0 -> accu
    | n -> nums (n::accu) (pred n)
  in
  nums [] limit
;;

いちいち名前が長い

これはしょうがないことではあるのですが、mult_big_intとかunit_big_intとかいちいち書くのが面倒です。「わがままいってんじゃねえよ、ボウヤ」という方々の声が聞こえてきますが。僕はものぐさちゃんなので許してください。

let ( *~ ) = mult_big_int;;
let ( +~ ) = add_big_int;;
let ( /~ ) = div_big_int;;
let ( -~ ) = sub_big_int;;

など、勝手にbindし直してしまっています。しかしzero_big_intとunit_big_intは皆さんはどうしてますか？長くないですか？

追記 (2010.05.17)

id:kuenishiから「演算子変えれば？」と言われたので、「たしかに」と思って変えました。