-- http://www.haskellforall.com/2020/04/blazing-fast-fibonacci-numbers-using.html
-- a blog entry by Gabriel Gonzales
--
-- fast fibonacci: O(log n)

module Main where

import System.Environment (getArgs)

-- --------------------
--
-- standard algorithm with runtime O(n)

fib0 :: Integer -> Integer
fib0 = fib' 0 1
  where
    fib' x0 x1 n
      | n == 0    = x0
      | otherwise = fib' x1 (x0 + x1) (n - 1)

-- --------------------
--
-- 2x2 matrix for computing the next step

data Matrix2x2 = Matrix
    { x00 :: Integer, x01 :: Integer
    , x10 :: Integer, x11 :: Integer
    }

instance Semigroup Matrix2x2 where
  Matrix l00 l01 l10 l11 <> Matrix r00 r01 r10 r11 =
    Matrix
    { x00 = l00 * r00 + l01 * r10, x01 = l00 * r01 + l01 * r11
    , x10 = l10 * r00 + l11 * r10, x11 = l10 * r01 + l11 * r11
    }

instance Monoid Matrix2x2 where
  mempty =
    Matrix
    { x00 = 1, x01 = 0
    , x10 = 0, x11 = 1
    }

-- --------------------
--
-- fast exponentiation
-- generalized to monoids
--
-- copied from Data.Monoid

mtimes :: Monoid a => Integer -> a -> a
mtimes n x
  | n == 0 = mempty
  | n >  0 = stimes n x
  | otherwise = error "mtimes: negative argument"

stimes :: Semigroup a => Integer -> a -> a
stimes n x
  | n == 1    = x
  | even n    = stimes (n `div` 2) (x <> x)
  | otherwise = stimes (n - 1) x <> x

-- --------------------

fib :: Integer -> Integer
fib n = x01 (mtimes n matrix)
  where
    matrix =
      Matrix
      { x00 = 0, x01 = 1
      , x10 = 1, x11 = 1
      }

-- --------------------

main :: IO ()
main = do (inp : _) <- getArgs
          let arg = read inp
          let res = fib arg
          let out = "fib " <> show arg <> " = " <> show res
          putStrLn out


-- --------------------
--
-- simple test with removed output
--
-- :set +s

t1 = (== 0) $ fib  (10^6)
t2 = (== 0) $ fib0 (10^6)

-- --------------------