This site is updated infrequently. For up-to-date information, please visit the new OCaml website at 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: -- (:) From: Remi VANICAT Subject: Re: help an o'caml beginner
```John BEPPU <beppu@lineo.com> writes:

> Hi.
>

[...]

> This was much faster than any of the recursive versions, because it
> doesn't have to recompute the same values over and over again.
>
> 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
> that's a lot of paper -- I wish the tutorial were available in HTML.
> I just may have to print it, though.)
>
>
> >>>
> 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.
> >>>
>

it easy : you have to use an auxiliary function :

let fib n =
let rec aux n n1 n2 =
if n <= 2 then (n1 + n2)
else aux (n - 1) (n1 + n2) n1 in
if (n < 3) then 1 else aux (n - 1) 1 1

(an exact translation of your c function would be :
let fib n =
if (n < 2) then n
else
let rec aux i val n1 n2 =
if i < n then val
else aux (i + 1) (n1 + n2) (n1 + n2) n1

the idea here is for each variable of the c function have an argument
to the recursive caml function, and, instead of changing the variable,
to call the aux function with the new value.

Then I've done some clean up and removal of unused arguments)

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat

```