[  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.