{- |
Description: Fibonacci numbers with matrix exponentiation
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P30" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P30 (fibonacci') where

{- |
Computes the \(n\)th Fibonacci number with \(O(\log n)\) multiplications.
Takes advantage of matrix multiplication and exponentiation.
-}
fibonacci' :: Integral a => a -> a
fibonacci' :: forall a. Integral a => a -> a
fibonacci' a
1 = a
1
fibonacci' a
2 = a
1
fibonacci' a
n | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
2     = a
aa -> a -> a
forall a. Num a => a -> a -> a
+a
b
             | Bool
otherwise = a
forall a. HasCallStack => a
undefined
  where ((a
a,a
b), (a, a)
_) = ((a, a), (a, a)) -> a -> ((a, a), (a, a))
forall a. Integral a => Matrix a -> a -> Matrix a
power ((a
1,a
1),(a
1,a
0)) (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
2)

type Matrix a = ((a,a),
                 (a,a))

power :: Integral a => Matrix a -> a -> Matrix a
power :: forall a. Integral a => Matrix a -> a -> Matrix a
power Matrix a
base a
1 = Matrix a
base
power Matrix a
base a
n | a -> Bool
forall a. Integral a => a -> Bool
even a
n    = Matrix a -> Matrix a -> Matrix a
forall a. Integral a => Matrix a -> Matrix a -> Matrix a
multiply Matrix a
x Matrix a
x
             | Bool
otherwise = Matrix a -> Matrix a -> Matrix a
forall a. Integral a => Matrix a -> Matrix a -> Matrix a
multiply Matrix a
base (Matrix a -> Matrix a) -> Matrix a -> Matrix a
forall a b. (a -> b) -> a -> b
$ Matrix a -> a -> Matrix a
forall a. Integral a => Matrix a -> a -> Matrix a
power Matrix a
base (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1)
  where x :: Matrix a
x = Matrix a -> a -> Matrix a
forall a. Integral a => Matrix a -> a -> Matrix a
power Matrix a
base (a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2)

multiply :: Integral a => Matrix a -> Matrix a -> Matrix a
multiply :: forall a. Integral a => Matrix a -> Matrix a -> Matrix a
multiply
  ( (a
a, a
b)
  , (a
c, a
d)
  )
  ( (a
a', a
b')
  , (a
c', a
d')
  )
  = ( (a
aa -> a -> a
forall a. Num a => a -> a -> a
*a
a'a -> a -> a
forall a. Num a => a -> a -> a
+a
ba -> a -> a
forall a. Num a => a -> a -> a
*a
c', a
aa -> a -> a
forall a. Num a => a -> a -> a
*a
b'a -> a -> a
forall a. Num a => a -> a -> a
+a
ba -> a -> a
forall a. Num a => a -> a -> a
*a
d')
    , (a
ca -> a -> a
forall a. Num a => a -> a -> a
*a
a'a -> a -> a
forall a. Num a => a -> a -> a
+a
da -> a -> a
forall a. Num a => a -> a -> a
*a
c', a
ca -> a -> a
forall a. Num a => a -> a -> a
*a
b'a -> a -> a
forall a. Num a => a -> a -> a
+a
da -> a -> a
forall a. Num a => a -> a -> a
*a
d')
    )