I'm going to regret this. I know I'm going to regret this.
On Sun, 12 Dec 2010, Jon Harrop wrote:
Here?s the equivalent OCaml code:
let rec collatzLen(c, n) : int =
if n = 1L then c else
collatzLen (c+1, if Int64.rem n 2L = 0L then Int64.div n 2L else
Int64.add (Int64.mul 3L n) 1L);;
let rec loop(i, (nlen, n)) =
if i = 1L then n else
let ilen = collatzLen(1, i) in
let nlen, n = if ilen > nlen then ilen, i else nlen, n in
loop (Int64.sub i 1L, (nlen, n));;
Congratulations, Jon, you win today's Captain Obvious award. Using
Int64's, which are forced to be boxed, really slows things down. Also,
uncurrying all your arguments also slows things down. Running your
original code on my 64-bit laptop, it took 6.35s to run the 1M example.
The following alternate code only took 0.82s, for a speed up of almost
7.75x. Scaling your timings by a similar amount gives Ocaml a running
speed of 3.14s in your set up, or competitive with F#.
My code:
let rec collatzLen c n =
if n = 1 then c else
collatzLen (c+1)
(if (n land 1) == 0 then (n lsr 1) else ((n * 3) + 1))
;;
let rec loop i nlen n =
if i = 1 then n else
let ilen = collatzLen 1 i in
if (ilen > nlen) then
loop (i - 1) ilen i
else
loop (i - 1) nlen n
;;
loop 1000000 0 0
Here is where you insert a lecture about how Ocaml int's being on 63 (or
31) bits aren't "real" ints, and that therefor this isn't a valid
comparison at all.
Brian
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
