DouKaku? 5120 xsd: OCamlは64bit整数を扱いだすと色...(コラッツ・角谷の問題)

Comment detail

OCamlは64bit整数を扱いだすと色々とオーバーヘッドが大きくなるので、なるべくintで
計算を行うようにして、あるところでint64に切り替えるようにしてます。
また、キャッシュもint64モードでは持たないようにして、ハッシュではなく配列で
アクセスの高速化を図っています。

PentiumM 1.7GHzで0.2秒強です。

 % time ./dk120
 f(837799)=524
 
 real    0m0.227s
 user    0m0.220s
 sys     0m0.007s

open Int64

let maxN       = 1048576
let cacheN     = maxN
let cacheN64   = Int64.of_int (2 * cacheN)

let memo = Array.create (cacheN+1) 0

let rec colatz31 = function
    | 1 -> 0
    | n ->
        if memo.(n) <> 0 then memo.(n) else (
            let c = 1 +
                if n land 1 = 0 then colatz31 (n lsr 1)
                else (
                    let t = n * 3 + 1 in
                    if t <= cacheN then colatz31 t
                                   else colatz64 (of_int t)) in
            let _ = memo.(n) <- c in c)

and colatz64 n =
    let t = to_int n in
    if (t land 1) = 0 then (
        if n <= cacheN64 then 1 + colatz31 (t lsr 1)
                         else 1 + colatz64 (shift_right_logical n 1)
    ) else 1 + colatz64 (succ(mul n 3L))

let rec loop max1 max2 = function
    | n when n > maxN -> max1, max2
    | n -> let max = colatz31 n in
        if max > max2 then loop n max (n+1) else loop max1 max2 (n+1)

let _ =
    let a,b = loop 0 0 1 in
    Printf.printf "f(%d)=%d\n" a b

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq