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:29) From: Markus Mottl Subject: Re: help an o'caml beginner
```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.

Here a collection of three fibonacci algorithms. The first one is the
"simple-minded" one, the second uses tail-recursion, which removes some
redundant computations, too. The third one - well, try it out ;-)

---------------------------------------------------------------------------
let rec fib1 = function
| n when n <= 1 -> 1
| n -> fib1 (n-1) + fib1 (n-2)

let fib2 n =
let rec fib2_aux n2 n1 = function
| m when m = n -> n1
| m -> fib2_aux n1 (n2+n1) (m+1) in
if n <= 1 then 1 else fib2_aux 1 2 2

let rec fib3_aux = function
| 0 -> 1, 0
| 1 -> 0, 1
| n ->
let k = n/2 in
let a, b = fib3_aux k in
let aa = a*a and bb = b*b and ab2 = 2*a*b in
let ab2bb = ab2 + bb in
if 2*k = n then aa + bb, ab2bb
else ab2bb, ab2bb + aa + bb

let fib3 n =
if n <= 1 then 1
else
let k = n/2 in
let a, b = fib3_aux k in
let ab = a + b in
if 2*k = n then ab*ab + b*b
else ab*ab + 2*b*ab

let _ = Printf.printf "%d\n" (fib3 1000000)
---------------------------------------------------------------------------

Btw., algorithms 2 + 3 can both be generated by automatic program

@Article{Pettorossi-Proietti96,
key =          "Pettorossi \& Proietti",
author =       "Alberto Pettorossi and Maurizio Proietti",
title =        "Rules and Strategies for Transforming Functional and
Logic Programs",
journal =      "ACMCS",
volume =       "28",
number =       "2",
pages =        "360--414",
month =        jun,
year =         "1996",
annote =       "Many references.",
}

Best regards,
Markus Mottl

--
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

```