blob: 78618eacae2d47e3bf5fc35cba352cc92379f86a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
|
