Ocaml sums the harmonic series  four ways, four benchmarks: floating point performance
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050113 (15:53) 
From:  Will M. Farr <farr@M...> 
Subject:  Ocaml sums the harmonic series  four ways, four benchmarks: floating point performance 
BEGIN PGP SIGNED MESSAGE Hash: SHA1 I've been looking at using ocaml to implement a gravitational nbody code, and therefore have quite a bit of interest in its floatingpoint performance. Also, I'm learning the language by playing around with simple programs. Here's an implementation (really 4) along with timing information of the "harmonic" benchmark (essentially summing the harmonic series), which can be found here: http://shootout.alioth.debian.org/sandbox/benchmark.php? test=harmonic&lang=all&sort=cpu After testing different ways of implementing the ocaml harmonic benchmark, I have settled on the following program. For sizes of 1 000 000 000 terms, it takes about 25% longer than the corresponding algorithm in c (note that I have replaced an int>float conversion for each term with a single floating point operation: ifloat := ifloat +. 1.0). Since int>float conversions are slow on my machine (PowerBook G4), this is a big win (about a factor of 2 in time for the C program). Alas, when the number of terms approaches 16 digits, this method will lose accuracy, since <~16digit number> +. 1.0 = <16digit number + difference in last bit of mantissa>. However, for sizes like the shootout seems to be using, this algorithm works fine (and the usual int type won't hold anything close to 16 digits anyway!). I'm ccing this to the caml list because there may be people there interested in the floating point performance of Caml Here's the code for the fastest implementation: let sum_harmonic4 n = let sum = ref 1.0 in let ifloat = ref 2.0 in for i = 2 to n do sum := !sum +. 1.0/.(!ifloat); ifloat := !ifloat +. 1.0 done; !sum;; let _ = let n = int_of_string (Sys.argv.(1)) in Printf.printf "%g\n" (sum_harmonic4 n);; And here's all the implementations I tried (for those interested in such things with ocaml): let sum_harmonic n = let rec loop i sum = if i <= n then loop (i + 1) (sum +. 1.0/.(float_of_int i)) else sum in loop 2 1.0;; let sum_harmonic2 n = let sum = ref 1.0 in for i = 2 to n do sum := !sum +. 1.0/.(float_of_int i) done; !sum;; let sum_harmonic3 n = let rec loop i ifloat sum = if i <= n then loop (i + 1) (ifloat +. 1.0) (sum +. 1.0/.ifloat) else sum in loop 2 2.0 1.0;; let sum_harmonic4 n = let sum = ref 1.0 in let ifloat = ref 2.0 in for i = 2 to n do sum := !sum +. 1.0/.(!ifloat); ifloat := !ifloat +. 1.0 done; !sum;; let _ = let n = int_of_string (Sys.argv.(1)) in Printf.printf "%g\n" (sum_harmonic4 n);; The timings for my machine (PowerBook G4, 800 Mhz) are as follows: time ./harmonic 1000000000: harmonic: user 2m1.590s sys 0m0.790s harmonic2: user 2m0.340s sys 0m0.440s harmonic3: user 1m44.350s sys 0m0.740s harmonic4: user 1m12.680s sys 0m0.430s Each invocation was compiled with "ocamlopt unsafe noassert o harmonic harmonic.ml". It looks like using references and loops is *by far* the fastest (and also that my PowerBook is pretty slow to convert int>float, but I don't think this is related to ocaml, since the C version does the same thing). Hope you all find this interesting. Will BEGIN PGP SIGNATURE Version: GnuPG v1.4.0 (Darwin) iD8DBQFB5pl3jFCrhUweU3MRApDzAJ9Ysln/KTQcq4WzxT9060GcDAgKQwCfTsb0 mDm4UyyghIz7m7r4ZpGcI3o= =dLDI END PGP SIGNATURE