This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

ocaml and int64
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2008-04-02 (01:59) From: Jon Harrop Subject: Re: [Caml-list] ocaml and int64
```On Wednesday 02 April 2008 01:54:54 Ludovic Coquelle wrote:
> Hi,
>
> I wrote a direct translation of a simple algo from F# to ocaml.
> (details can be found here:
> http://khigia.wordpress.com/2008/03/30/ocaml-vs-f-for-big-integer-surprisin
>g-performance-test/ )
>
> The compile F# program (12s) is much faster than Ocaml (30s), probably
> because the algo do integer arithmetic with Int64 module (thanks to David
> for this info).
>
> Have someone here face this kind of problem (optimizing a code doing
> arithmetic on big integer)?
> Any advice to improve the Ocaml code (without changing the algo)?

Get a 64-bit machine. ;-)

There are some performance pitfalls in your code (which takes 21s on my
machine):

. OCaml makes no attempt to optimize integer div and mod so avoid these at all
costs. In this case, use bitwise ANDs and shifts.

. Int64 is boxed by default and your use of recursion is likely to worsen this
effect.

Optimizing for these, the following code takes only 4.6s, which is 4.6x faster

let int = Int64.to_int
let int64 = Int64.of_int
let ( +: ) = Int64.add
let ( -: ) = Int64.sub
let ( *: ) = Int64.mul
let ( >>> ) = Int64.shift_right

let rec seq_length x n =
match x with
| 0L -> n +: 1L
| 1L -> seq_length 0L (n +: 1L)
| x when int x land 1 = 0 -> seq_length (x >>> 1) (n +: 1L)
| _ -> seq_length (3L *: x +: 1L) (n +: 1L)

let rec loop i imax n =
let n' = seq_length i 0L in
let imax, n = if n' > n then (i, n') else (imax, n) in
if i < 1000000L then loop (i +: 1L) imax n else imax

let _ = print_string (Int64.to_string (loop 1L 0L 0L))

Using 63-bit ints on a 64-bit machine, the time drops to only 2s:

let rec seq_length x n =
match x with
| 0 -> n + 1
| 1 -> seq_length 0 (n + 1)
| x when x land 1 = 0 -> seq_length (x lsr 1) (n + 1)
| _ -> seq_length (3*x + 1) (n + 1)

let rec loop i imax n =
let n' = seq_length i 0 in
let imax, n = if n' > n then (i, n') else (imax, n) in
if i < 1000000 then loop (i+1) imax n else imax

let _ = print_string (string_of_int (loop 1 0 0))

As you have allured to, algorithmic optimizations buy you even more. The
following implementation is several times faster again, taking only 0.6s to
complete:

let int = Int64.to_int
let int64 = Int64.of_int
let ( +: ) = Int64.add
let ( -: ) = Int64.sub
let ( *: ) = Int64.mul

let rec inside a n =
if n<=1L then 0 else
if a.(int n)>0 then a.(int n) else
let p =
if int n land 1 = 0 then inside a (Int64.shift_right n 1) else
let n = 3L *: n +: 1L in
if n < int64(Array.length a) then inside a n else outside a n in
a.(int n) <- 1 + p;
1 + p
and outside a n =
let n = if int n land 1 = 0 then Int64.shift_right n 1 else 3L *: n +: 1L in
1 + if n < int64(Array.length a) then inside a n else outside a n

let euler14 n =
let a = Array.create (n+1) 0 in
let longest_n = ref 0 and longest_len = ref 0 in
for n=1 to n do
let len = inside a (int64 n) in
if len > !longest_len then begin
longest_n := n;
longest_len := len
end
done;
!longest_n, !longest_len

let () =
let n, len = euler14 1000000 in
Printf.printf "%d: %d\n%!" n len

Converting this to use native ints on my 64-bit machine the time drops to only
0.2s, which is over 100x faster than your original!

However, this benchmark really plays to F#'s strengths and you will probably
never beat F# here. My best F# is 3x faster than anything I can write in
OCaml, not least because it is trivial to parallelize efficiently but also
because F# and .NET automate many relevant optimizations.

HTH.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

```