Skip to main content
edited tags; edited title
Link
200_success
  • 144.2k
  • 22
  • 188
  • 473

Syracuse conjecture, optimize in OCaml code

Source Link
RUser4512
  • 1.1k
  • 6
  • 21

Syracuse conjecture, optimize OCaml code

I am wondering how to optimize the following OCaml simple code.

#load "unix.cma";;
open Unix;;

let time f x =
    let start = Unix.gettimeofday ()
    in let res = f x
    in let stop = Unix.gettimeofday ()
    in let () = Printf.printf "Execution time: %fs\n%!" (stop -. start)
    in res ;;


let syracuse x =
    let rec aux x t =
        match x with
          1 -> t
          |x -> if x mod 2 = 0 then aux (x / 2) (t + 1) else aux (3 * x + 1) (t+1) in
     aux x 0 ;;

let syracuse2 x =
    let rec aux x t =
        if x = 1 then
            t
        else
            if x mod 2 = 0 then aux (x / 2) (t + 1) else aux (3 * x + 1) (t+1)
        in
     aux x 0 ;;


let rec iterate_over n f l  =
     if n = 0 then l else iterate_over (n-1) f ((f n)::l);;

let syracuses n = iterate_over n syracuse [];;
let syracuses2 n = iterate_over n syracuse2 [];;


(time syracuses 100000);;
(time syracuses2 100000);;

I made a first attempt replacing the match with with ifs but it slightly reduced the performance.

Execution time: 1.880309s
Execution time: 1.920133s

I tried to replace the t+1s by succ t but it did not bring anything. I think that there are some redundancies in the operations performed when calling mod 2 and dividing by 2 but I don't know how it can help.