(* $Date: 2005/11/09 20:34:44 $ *)

(* The stupid way of computing the Fibonnaci numbers *)
(* ------------------------------------------------- *)

fun fibS n = if n<=1 then 1 else (fibS (n-1))+(fibS (n-2));

(* The naive way of computing the Fibonacci numbers *)
(* ------------------------------------------------ *)
(* ...and the best for all practical purposes       *)

fun fibAux n a b = if n=0 then b else fibAux (n-1) b (a+b);
fun fibN   n     = if n<=1 then 1 else fibAux (n-1) 1 1;

(* The linear Algebra way of computing the Fibonacci numbers *)
(* --------------------------------------------------------- *)

(* we only have 2x2 Matrices, so do it more hands on *)

fun product ((a,b),(c,d)) ((e,f),(g,h)) = ((a*e+b*g,a*g+b*h),(c*e+d*g,c*f+d*h));
fun square A = product A A;
fun even n = (n mod 2 = 0);
fun power A n =  if n = 1 then A else 
                 if even n then square (power A (n div 2)) 
                 else product (power A (n-1)) A;

val A = ((0,1),(1,1));

fun fibLAaux ((a,b),(_,_)) = a*1+b*1;

fun fibLA n = fibLAaux (power A n);