Accueil     À propos     Téléchargement     Ressources     Contactez-nous

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

help an o'caml beginner
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2000-07-27 (21:31) From: Jean-Christophe Filliatre Subject: Re: help an o'caml beginner
```
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

```