Safe Haskell	Safe-Inferred
Language	Haskell2010

Math

Description

Math

Sources:

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Synopsis

egcd :: Integral i => i -> i -> (i, i)
egcd2 :: Integral i => i -> i -> (i, i, i)
mkInvFactorials :: (IArray a e, Num e) => Int -> e -> a Int e
mkFactorials :: (IArray a e, Num e) => Int -> a Int e
mkBinom :: forall a e. (IArray a e, Fractional e) => Int -> Int -> Int -> e

Documentation

egcd :: Integral i => i -> i -> (i, i) Source #

Returns (g, s) where g = gcd(a, b); as + bt = g. O(log min(a, b)). Also see note for egcd2.

egcd2 :: Integral i => i -> i -> (i, i, i) Source #

Returns (g, s, t) where g = gcd(a, b); as + bt = g. O(log min(a, b)). Note: If the inputs are negative the returned gcd may be negative. abs the inputs or sign flip the outputs if this is undesirable. The complexity assumes operations quotRem, (-), (*), (==0) all take O(1).

mkInvFactorials :: (IArray a e, Num e) => Int -> e -> a Int e Source #

Given 1/(n!) calculcate inverse factorials for 0..n. O(n).

mkFactorials :: (IArray a e, Num e) => Int -> a Int e Source #

Calculate factorials for 0..n. O(n).

mkBinom :: forall a e. (IArray a e, Fractional e) => Int -> Int -> Int -> e Source #

Given the maximum value of n, calculate binomial coefficients for n, k. Apply partially for multiple queries. O(maxn) to set up, O(1) per query.