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
transformation. If you want to learn more about this, read:

@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