On Wed, 26 Jul 2000, John BEPPU wrote:

> >>>
> 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.
> >>>

(I guess there will be many answers ..)

Here is a solution:

let fibo n =
  let rec aux last x i =    (* x is u_i; last is u_{i-1} *)
     if (i = n) then x
     else aux x (x + last) (i + 1)
  in
  if (n = 0) then 1 else
  aux 1 1 1


> I wrote a recursive Perl version that doesn't make redundant
> calculations, and I'd be interested to see how different in
> structure an O'Caml version would be.
> 
>     sub fib_pair {
>         my $n = shift;
>         my @seq;
>         if ($n < 2) {
>             @seq = (1, 1);
>         } else {
>             @seq = fib_pair($n - 1);
>             @seq = ($seq[1], $seq[0] + $seq[1]);
>         }
>         return @seq;
>     }

Well, this function is not tail-recursive (the recursive call
can't be implemented as a jump). I didn't try it, but I am pretty sure
the OCaml version will be more efficient.

-- 
Alain Frisch