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 CAA10275 for caml-red; Fri, 28 Jul 2000 02:03:16 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA10712 for ; Fri, 28 Jul 2000 00:16:10 +0200 (MET DST) Received: from enst.enst.fr (enst.enst.fr [137.194.2.16]) by nez-perce.inria.fr (8.10.0/8.10.0) with ESMTP id e6RMG9L27303 for ; Fri, 28 Jul 2000 00:16:09 +0200 (MET DST) Received: from haguanauer.dijon.fr (cal-ppp17.ppp.enst.fr [137.194.3.17]) by enst.enst.fr (Postfix) with ESMTP id 3BB2F1C8DD for ; Fri, 28 Jul 2000 00:16:08 +0200 (MET DST) Received: from localhost (localhost [[UNIX: localhost]]) by haguanauer.dijon.fr (8.10.2/8.10.2) id e6S05QY27364 for caml-list@inria.fr; Fri, 28 Jul 2000 00:05:26 GMT From: Michel Quercia Reply-To: quercia@cal.enst.fr To: caml-list@inria.fr Subject: Re: help an o'caml beginner Date: Thu, 27 Jul 2000 23:47:42 +0000 X-Mailer: KMail [version 1.0.28] Content-Type: text/plain References: <20000726115152.A6102@yukari.lineo.com> In-Reply-To: <20000726115152.A6102@yukari.lineo.com> MIME-Version: 1.0 Message-Id: <0007280005260B.23279@haguenauer> Content-Transfer-Encoding: 8bit Sender: weis@pauillac.inria.fr Le Wed, 26 Jul 2000, John BEPPU a écrit : > I tried out the recursive fibonacci number program > ... > Next, I tried to fumble my way through making an O'Caml version of > this iterative algorithm, but I failed due to my lack of knowledge > about this language. Below are three translations of your iterative C code : ------------------------------------------------------------ (* iterative Caml code *) let fib(n) = let a = ref(1) and b = ref(1) in for i=2 to n do let x = !a + !b in a := !b; b := x done; !b ;; ------------------------------------------------------------- (* recursive Caml code, fib2(n) returns (fib(n-1),fib(n)) *) let rec fib2(n) = if n <= 1 then (n,1) else let (a,b) = fib2(n-1) in (b,a+b) ;; let fib(n) = let (_,x) = fib2(n) in x;; ------------------------------------------------------------- (* tail-recursive Caml code, fib3 a b n computes a*fib(n) + b*fib(n-1) *) let rec fib3 a b n = if n <= 1 then a + b*n else fib3 (a+b) a (n-1);; let fib(n) = fib3 1 0 n;; -------------------------------------------------------- Note that there are also divide-and-conquer algorithms for computing Fibonacci numbers that achieve logarithmic computing time with respect to the input. > I wish the tutorial were available in HTML. There is atutorial included in the html documentation. Regards, -- Michel Quercia 23 rue de Montchapet, 21000 Dijon http://pauillac.inria.fr/~quercia mailto:quercia@cal.enst.fr