iota

Safe Haskell	None
Language	GHC2021

Math.Combinatrics

Synopsis

newtype FactCache (p :: Nat) = FactCache (Vector (GF p))
type HasFactCache (p :: Nat) = ?factCache :: FactCache p
newtype RecipFactCache (p :: Nat) = RecipFactCache (Vector (GF p))
type HasRecipFactCache (p :: Nat) = ?recipFactCache :: RecipFactCache p
type HasCombCache (p :: Nat) = (HasFactCache p, HasRecipFactCache p)
fact :: forall (p :: Nat). (HasFactCache p, KnownNat p) => Int -> GF p
recipFact :: forall (p :: Nat). (HasRecipFactCache p, KnownNat p) => Int -> GF p
perm :: forall (p :: Nat). (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p
comb :: forall (p :: Nat). (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p
combNaive :: Int -> Int -> Int
buildFactCache :: forall (p :: Nat). KnownNat p => Int -> FactCache p
withFactCache :: forall (p :: Nat) r. KnownNat p => Int -> (HasFactCache p => r) -> r
buildRecipFactCache :: forall (p :: Nat). (HasFactCache p, KnownNat p) => Int -> RecipFactCache p
withRecipFactCache :: forall (p :: Nat) r. (HasFactCache p, KnownNat p) => Int -> (HasRecipFactCache p => r) -> r
withCombCache :: forall (p :: Nat) r. KnownNat p => Int -> (HasCombCache p => r) -> r
combSmall :: forall (p :: Nat). KnownNat p => Int -> Int -> GF p
combSmallTable :: forall (p :: Nat). KnownNat p => Vector (GF p)

Documentation

newtype FactCache (p :: Nat) Source #

Constructors

FactCache (Vector (GF p))

type HasFactCache (p :: Nat) = ?factCache :: FactCache p Source #

newtype RecipFactCache (p :: Nat) Source #

Constructors

RecipFactCache (Vector (GF p))

type HasRecipFactCache (p :: Nat) = ?recipFactCache :: RecipFactCache p Source #

type HasCombCache (p :: Nat) = (HasFactCache p, HasRecipFactCache p) Source #

fact :: forall (p :: Nat). (HasFactCache p, KnownNat p) => Int -> GF p Source #

O(1)

>>> :set -XDataKinds
>>> withFactCache @1000000007 10 $ fact 10
3628800

recipFact :: forall (p :: Nat). (HasRecipFactCache p, KnownNat p) => Int -> GF p Source #

O(1)

perm :: forall (p :: Nat). (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p Source #

O(1)

n < p

comb :: forall (p :: Nat). (HasFactCache p, HasRecipFactCache p, KnownNat p) => Int -> Int -> GF p Source #

O(1)

n < p

combNaive :: Int -> Int -> Int Source #

O(r)

>>> combNaive 64 32
1832624140942590534
>>> combNaive 123456789 2
7620789313366866
>>> combNaive 123 456
0

buildFactCache :: forall (p :: Nat). KnownNat p => Int -> FactCache p Source #

withFactCache :: forall (p :: Nat) r. KnownNat p => Int -> (HasFactCache p => r) -> r Source #

buildRecipFactCache :: forall (p :: Nat). (HasFactCache p, KnownNat p) => Int -> RecipFactCache p Source #

withRecipFactCache :: forall (p :: Nat) r. (HasFactCache p, KnownNat p) => Int -> (HasRecipFactCache p => r) -> r Source #

withCombCache :: forall (p :: Nat) r. KnownNat p => Int -> (HasCombCache p => r) -> r Source #

combSmall :: forall (p :: Nat). KnownNat p => Int -> Int -> GF p Source #

Lucas's theorem

O(log N)

combSmallTable :: forall (p :: Nat). KnownNat p => Vector (GF p) Source #

O(p ^ 2)