From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA08287 for caml-red; Thu, 27 Jul 2000 23:29:45 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA05783 for <caml-list@pauillac.inria.fr>; Thu, 27 Jul 2000 20:56:38 +0200 (MET DST)
Received: from miss.wu-wien.ac.at (miss.wu-wien.ac.at [137.208.107.17])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6RIub521383
	for <caml-list@inria.fr>; Thu, 27 Jul 2000 20:56:38 +0200 (MET DST)
Received: (from mottl@localhost)
	by miss.wu-wien.ac.at (8.9.0/8.9.0) id UAA28119;
	Thu, 27 Jul 2000 20:56:27 +0200 (MET DST)
Date: Thu, 27 Jul 2000 20:56:27 +0200
From: Markus Mottl <mottl@miss.wu-wien.ac.at>
To: John BEPPU <beppu@lineo.com>
Cc: caml-list@inria.fr
Subject: Re: help an o'caml beginner
Message-ID: <20000727205627.B21080@miss.wu-wien.ac.at>
References: <20000726115152.A6102@yukari.lineo.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2i
In-Reply-To: <20000726115152.A6102@yukari.lineo.com>; from beppu@lineo.com on Wed, Jul 26, 2000 at 11:51:52 -0600
Sender: weis@pauillac.inria.fr

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