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