From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA08640 for caml-red; Thu, 27 Jul 2000 23:31:41 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA05804 for ; Thu, 27 Jul 2000 21:08:07 +0200 (MET DST) Received: from csla.csl.sri.com (csla.csl.sri.com [192.12.33.2]) by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6RJ86521783 for ; Thu, 27 Jul 2000 21:08:06 +0200 (MET DST) Received: from cylinder.csl.sri.com (IDENT:root@cylinder.csl.sri.com [130.107.15.112]) by csla.csl.sri.com (8.9.1/8.9.1) with ESMTP id MAA07440; Thu, 27 Jul 2000 12:08:04 -0700 (PDT) Received: (from filliatr@localhost) by cylinder.csl.sri.com (8.9.3/8.8.7) id MAA13004; Thu, 27 Jul 2000 12:08:03 -0700 X-Authentication-Warning: cylinder.csl.sri.com: filliatr set sender to filliatr@cylinder.csl.sri.com using -f From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <14720.34963.196911.385872@cylinder.csl.sri.com> Date: Thu, 27 Jul 2000 12:08:03 -0700 (PDT) To: John BEPPU Cc: caml-list@inria.fr Subject: Re: help an o'caml beginner In-Reply-To: <20000726115152.A6102@yukari.lineo.com> References: <20000726115152.A6102@yukari.lineo.com> X-Mailer: VM 6.62 under Emacs 20.7.1 Reply-To: filliatr@csl.sri.com (Jean-Christophe Filliatre) Sender: weis@pauillac.inria.fr In his message of Wed July 26, 2000, John BEPPU writes: > > Next, I wrote an iterative C version. > [...] > This was much faster than any of the recursive versions, because it > doesn't have to recompute the same values over and over again. > [...] > If anyone out there could implement an O'Caml fibonacci number > generator that doesn't make redundant calculations, I would really > appreciate it. I just need something to study. First, you can write it exactly as in C, since ocaml supports references and imperative programming constructs. But there is an even more direct way of writing it, in a functional way, which could be the following: ====================================================================== let rec fib_aux v1 v2 n = if n = 0 then v1 else fib_aux v2 (v1 + v2) (pred n) let fib n = fib_aux 0 1 n ====================================================================== (In a general way, a C loop becomes a recursive function with as many arguments as variables involved in the loop.) By the way, if you are interested in computing Fibonacci numbers, there are even more efficient ways to do that. Here is a pointer (code by Xavier Urbain, documentation in French): http://www.lri.fr/~filliatr/pub/lucas.ps -- Jean-Christophe Filliatre Computer Science Laboratory Phone (650) 859-5173 SRI International FAX (650) 859-2844 333 Ravenswood Ave. email filliatr@csl.sri.com Menlo Park, CA 94025, USA web http://www.csl.sri.com/~filliatr