コラッツ・角谷の問題
Posted feedbacks - OCaml
OCamlは64bit整数を扱いだすと色々とオーバーヘッドが大きくなるので、なるべくintで 計算を行うようにして、あるところでint64に切り替えるようにしてます。 また、キャッシュもint64モードでは持たないようにして、ハッシュではなく配列で アクセスの高速化を図っています。 PentiumM 1.7GHzで0.2秒強です。 % time ./dk120 f(837799)=524 real 0m0.227s user 0m0.220s sys 0m0.007s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 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
|
ところてん
#4969()
Rating2/2=1.00
see: コラッツの問題の成り立つ範囲
[ reply ]