module Math (
    fac,
    inverseMod,
    fib,
    isPrime,
    nPk,
    nCk
) where

fac :: Integral a => a -> a
fac n = foldl (*) 1 [1..n]

inverseMod :: Integral a => a -> a -> a
inverseMod q 1 = 1
inverseMod q r = (n * q + 1) `div` r
    where n = r - inverseMod r (q `mod` r)

fib :: Integral a => a -> a
fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

isPrime :: Integral a => a -> Bool
isPrime x = all (\a -> mod x a /= 0) [2..n]
    where n = floor . sqrt . fromIntegral $ x

nPk :: Integral a => a -> a -> a
nPk n k = (fac n) `div` (fac $ n - k)

nCk :: Integral a => a -> a -> a
nCk n k = div (fac n) $ (fac $ n - k) * (fac k)