HN2new | past | comments | ask | show | jobs | submitlogin

Here is an implementation in OCaml. Time taken on a 1.3 GHz MacBook Air:

    :tmp $ time ./collatz.native 1000000
    start: 837799 length 329

    real	0m0.782s
    user	0m0.776s
    sys	0m0.004s

    exception Error of string

    let (@@) f x  = f x
    let error fmt = Printf.kprintf (fun msg -> raise (Error msg)) fmt

    let max (a, x) (b, y) = if x > y then (a, x) else (b, y)

    let length start =
        let rec loop len a = 
            let next = if a mod 2 = 0 then a/2 else (3*a+1)/2 in 
            if a != 1 then
                loop (len+1) next
            else
                len
        in
            loop 0 start
                
    let collatz limit =
        let rec loop start longest =
            if start >= limit 
            then longest 
            else loop (start+1) (max longest (start, length start)) 
        in
            loop 1 (1,0)

    let report (start, len) = Printf.printf "start: %d length %d\n" start len

    let main () =
        let argv        = List.tl @@ Array.to_list Sys.argv in
        match argv with
        | []    -> report @@ collatz 10000
        | [n]   -> report @@ collatz @@ int_of_string n
        | _     -> error "usage: collatz [n]"

    let () = main ()


As a big OCaml fan, this is pretty cool. The speeds aren't that bad either. I hope OCaml gets more competitive in terms of running time in the future.


The code probably could be made faster by avoiding passing tuples (start, length) around as these are allocated on the heap. However, I found it a little bit more abstract.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: