From 136b9a5fe04b0dc7ca3b390c169cb933ab38188a Mon Sep 17 00:00:00 2001
From: Ramakrishnan Muthukrishnan <ram@rkrishnan.org>
Date: Mon, 22 Dec 2014 22:22:43 +0530
Subject: [PATCH] hw6: fib4 using Matrix operation

---
 hw6/Fibonacci.hs | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/hw6/Fibonacci.hs b/hw6/Fibonacci.hs
index 15b563b..39f3349 100644
--- a/hw6/Fibonacci.hs
+++ b/hw6/Fibonacci.hs
@@ -96,3 +96,18 @@ instance Fractional (Stream Integer) where
                                   r
 fibs3 :: Stream Integer
 fibs3 = x' / (streamRepeat 1 - x' - x' * x')
+
+-- exercise 7
+data Matrix = Matrix Integer Integer Integer Integer
+
+instance Num Matrix where
+  (*) :: Matrix -> Matrix -> Matrix
+  (*) (Matrix a1 b1 c1 d1) (Matrix a2 b2 c2 d2) =
+    Matrix (a1*a2 + b1*c2) (a1*b2 + b1*d2) (c1*a2 + d1*c2) (c1*b2 + d1*d2)
+
+fib4 :: Integer -> Integer
+fib4 0 = 0
+fib4 n = let f0 = (Matrix 1 1 1 0)
+             (Matrix _ b _ _) = f0 ^ n
+         in
+           b
-- 
2.45.2