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 PAA19950 for caml-red; Fri, 28 Jul 2000 15:19:14 +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 LAA17791 for <caml-list@pauillac.inria.fr>; Fri, 28 Jul 2000 11:40:43 +0200 (MET DST)
Received: from margaux.inria.fr (margaux.inria.fr [128.93.8.2])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6S9egL16405
	for <caml-list@pauillac.inria.fr>; Fri, 28 Jul 2000 11:40:42 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by margaux.inria.fr (8.7.6/8.7.3) with ESMTP id LAA01093 for <caml-list@margaux.inria.fr>; Fri, 28 Jul 2000 11:40:41 +0200 (MET DST)
Received: from camus.cybercable.fr (camus.cybercable.fr [212.198.0.200])
	by nez-perce.inria.fr (8.10.0/8.10.0) with SMTP id e6RLV7L25903
	for <caml-list@margaux.inria.fr>; Thu, 27 Jul 2000 23:31:07 +0200 (MET DST)
Message-Id: <200007272131.e6RLV7L25903@nez-perce.inria.fr>
Received: (qmail 3640873 invoked from network); 27 Jul 2000 21:31:07 -0000
Received: from r187m232.cybercable.tm.fr (HELO 195.132.187.232) ([195.132.187.232]) (envelope-sender <lcheno@cybercable.fr>)
          by camus.cybercable.fr (qmail-ldap-1.03) with SMTP
          for <beppu@lineo.com>; 27 Jul 2000 21:31:07 -0000
Date: Thu, 27 Jul 2000 23:31:12 +0200
From: Laurent =?iso-8859-1?Q?Ch=E9no?= <lcheno@cybercable.fr>
Subject: Re: help an o'caml beginner
To: John BEPPU <beppu@lineo.com>, Caml list <caml-list@margaux.inria.fr>
X-Priority: 3
In-Reply-To: <20000726115152.A6102@yukari.lineo.com>
MIME-Version: 1.0
Content-Type: text/plain; Charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mailsmith 1.1.4 (Bluto)
Sender: weis@pauillac.inria.fr

Le 26/07/00 à 11:51, beppu@lineo.com (John BEPPU) écrivait :

> Hi.

--- Please excuse my poor english --- 
> 
> Next, I wrote an iterative C version.
> 
>     #include <stdio.h>
> 
>     int fib(int n)
>     {
>         int val = 2;
>         int n1 = 2;
>         int n2 = 1;
>         int i;
>         if (n < 2)
>             return n;
> 
>         for (i = 2; i < n; i++) {
>             val = n2 + n1;
>             n2 = n1;
>             n1 = val;
>         }
>         return val;
>     }
> 
>     int main(char *argc, char **argv)
>     {
>         printf("%d\n", fib(atoi(argv[1])));
>         return 0;
>     }
> 
> This was much faster than any of the recursive versions, because it 
> doesn't have to recompute the same values over and over again.  
> 

the basic translation can be for example :

let fib n =
    let val = ref 2
    and n1  = ref 2
    and n2  = ref 1
    in
    if n < 2 then n
    else for i = 2 to n - 1 do
            val := !n1 + !n2 ;
            n2 := !n1 ;
            n1 := !val
         done ;
         !val ;;

But I prefer a recursive and efficient version like this :

let fib n =
    let rec fibaux n p q =
        if n = 0 then p
        else fibaux (n - 1) q (p + q)
    in
    fibaux n 0 1 ;;

this is a terminal recursion : try it !

-- 
Laurent Chéno                   Paris (France)
<http://pauillac.inria.fr/~cheno/>
--