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

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Markus Mottl <mottl@m...> 
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 "simpleminded" one, the second uses tailrecursion, which removes some redundant computations, too. The third one  well, try it out ;)  let rec fib1 = function  n when n <= 1 > 1  n > fib1 (n1) + fib1 (n2) 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 transformation. If you want to learn more about this, read: @Article{PettorossiProietti96, 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 = "360414", month = jun, year = "1996", annote = "Many references.", } Best regards, Markus Mottl  Markus Mottl, mottl@miss.wuwien.ac.at, http://miss.wuwien.ac.at/~mottl