Re: help an o'caml beginner

[Jean-Christophe Filliatre <filliatr@csl.sri.com>]

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