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 NAA24361 for caml-red; Wed, 2 Aug 2000 13:09:24 +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 SAA04693 for <caml-list@pauillac.inria.fr>; Sat, 29 Jul 2000 18:59:40 +0200 (MET DST)
Received: from yukari.lineo.com (yukari.lineo.com [207.179.37.69])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6TGxcj02709
	for <caml-list@inria.fr>; Sat, 29 Jul 2000 18:59:39 +0200 (MET DST)
Received: by yukari.lineo.com (Postfix, from userid 440)
	id 1332D9B020; Sat, 29 Jul 2000 11:03:33 -0600 (MDT)
Date: Sat, 29 Jul 2000 11:03:33 -0600
From: John BEPPU <beppu@lineo.com>
To: caml-list@inria.fr
Cc: Markus Mottl <mottl@miss.wu-wien.ac.at>
Subject: Re: help an o'caml beginner
Message-ID: <20000729110333.A657@yukari.lineo.com>
References: <20000726115152.A6102@yukari.lineo.com> <20000727205627.B21080@miss.wu-wien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2i
In-Reply-To: <20000727205627.B21080@miss.wu-wien.ac.at>; from mottl@miss.wu-wien.ac.at on Thu, Jul 27, 2000 at 08:56:27PM +0200
Sender: weis@pauillac.inria.fr

[  date  ] 2000/07/27 | Thursday | 08:56 PM
[ author ] Markus Mottl <mottl@miss.wu-wien.ac.at> 

> 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)

This one was faster than the C version I posted.
The others were pretty close, too.  I continue to
be impressed.  I have a hard time believing fib3
was created by a mechanical transformation...  it
doesn't look anything like the other implementations.
I mean, I believe you as a matter of good faith, but
I'm amazed.

<question type="stupid">
    What does the keyword "in" mean?
</question>

> Btw., algorithms 2 + 3 can both be generated by automatic program
> transformation. If you want to learn more about this, read:

[snipped the reference...]

Thanks for the article...  I'll hit up the local universities,
and see if I can't track it down.