From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 02C7CBB91 for ; Thu, 13 Jan 2005 16:53:39 +0100 (CET) Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j0DFrbRf002236 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 13 Jan 2005 16:53:38 +0100 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id j0DFrX4M028775; Thu, 13 Jan 2005 10:53:33 -0500 (EST) Received: from [192.168.1.104] (CSR-DYN-83.MIT.EDU [18.75.3.83]) (authenticated bits=0) (User authenticated as farr@ATHENA.MIT.EDU) by outgoing.mit.edu (8.12.4/8.12.4) with ESMTP id j0DFrTBO015257 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT); Thu, 13 Jan 2005 10:53:29 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v619) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <3D3A6BF5-657B-11D9-A551-000393A34E82@mit.edu> Content-Transfer-Encoding: 7bit Cc: caml-list@yquem.inria.fr From: "Will M. Farr" Subject: Ocaml sums the harmonic series -- four ways, four benchmarks: floating point performance Date: Thu, 13 Jan 2005 10:53:16 -0500 To: shootout-list@lists.alioth.debian.org X-Pgp-Agent: GPGMail 1.0.2 X-Mailer: Apple Mail (2.619) X-Scanned-By: MIMEDefang 2.42 X-Miltered: at nez-perce with ID 41E69981.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 hash:01 ocaml:01 sandbox:01 int-:01 int-:01 alas:01 argv:01 printf:01 printf:01 rec:01 rec:01 argv:01 timings:01 invocation:01 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.0 X-Spam-Level: -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I've been looking at using ocaml to implement a gravitational n-body code, and therefore have quite a bit of interest in its floating-point 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 <~16-digit number> +. 1.0 = <16-digit 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 cc-ing 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-----