1 files changed, 27 insertions, 0 deletions
diff --git a/3-kyu/the-millionth-fibonacci-kata.hs b/3-kyu/the-millionth-fibonacci-kata.hs
new file mode 100644
index 0000000..78618ea
--- /dev/null
+++ b/3-kyu/the-millionth-fibonacci-kata.hs
@@ -0,0 +1,27 @@
+-- https://www.codewars.com/kata/53d40c1e2f13e331fc000c26
+module Fibonacci (fib) where
+
+fib :: Integer -> Integer
+fib n = if n >= 0 then posFib n else negFib (-n)
+
+negFib :: Integer -> Integer
+negFib n = if n `mod` 2 == 0 then (- (posFib n)) else posFib n
+
+
+matMul :: [[Integer]] -> [[Integer]] -> [[Integer]]
+matMul [[a,b],[c,d]] [[x,y],[z,w]] = [[a*x+b*z, a*y+b*w], [c*x+d*z, c*y+d*w]]
+matMul _ _ = error "Error in matMul: ill formatted matrix"
+
+matExp :: [[Integer]] -> Integer -> [[Integer]]
+matExp m 1 = m
+matExp m n
+  | n < 1 = error "Error in matExp: n must > 0"
+  | n `mod` 2 == 0 =
+      let half = matExp m (n `div` 2) in
+        seq half $ matMul half half
+  | otherwise = matMul m (matExp m (n-1))
+
+posFib :: Integer -> Integer
+posFib 0 = 0
+posFib 1 = 1
+posFib n = (matExp [[1,1], [1,0]] (n-1)) !! 0 !! 0