fact -package:diagrams-contrib

A Fact p is an implicit proof of p, propagated by Haskell's constraint solver. Facts can be used to implicitly introduce or propagate proofs. However, there is a small run-time cost associated with using Facts: typeclass dictionaries for Facts are still passed around. In many cases they will be optimized away, but this is not guaranteed.

Factor the input DSum Event to produce an Event which fires when the DSum key changes and contains both the value of the DSum at switchover and an Event of values produced by subsequent firings of the input Event that do not change the DSum key.

Factor a 'Dynamic t DSum' into a Dynamic DSum containing nested Dynamic values. The outer Dynamic updates only when the key of the DSum changes, while the update of the inner Dynamic represents updates within the current key.

Compute the factorial function n!. Returns +∞ if the input is above 170 (above which the result cannot be represented by a 64-bit Double).

Returns a list of all prime factors; inverse of mconcat.

Restore a number from its factorisation.

Factorise a number into a product of prime powers. Factorisation of 0 is an undefined behaviour. Otherwise following invariants hold:

abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n)))
all ((> 0) . snd) (factorise n)

>>> factorise (1 :: Integer)
[]

>>> factorise (-1 :: Integer)
[]

>>> factorise (6 :: Integer)
[(Prime 2,1),(Prime 3,1)]

>>> factorise (-108 :: Integer)
[(Prime 2,2),(Prime 3,3)]

This function is a replacement for factorise. If you were looking for the latter, please import Math.NumberTheory.Primes.Factorisation instead of this module. Warning: there are no guarantees of any particular order of prime factors, do not expect them to be ascending. E. g.,

>>> factorise 10251562501
[(Prime 101701,1),(Prime 100801,1)]

Infinite zero-based table of factorials.

>>> take 5 factorial
[1,1,2,6,24]

The time-and-space behaviour of factorial is similar to described in Math.NumberTheory.Recurrences.Bilinear#memory.

Prime factors of a factorial.

factorialFactors n == factorise (factorial !! n)

>>> factorialFactors 10
[(Prime 2,8),(Prime 3,4),(Prime 5,2),(Prime 7,1)]

Exact factorial numbers. For a fast approximation see math-functions:Numeric.SpecFunctions.factorial instead. The naive definition of the factorial numbers is:

factorial n
| n < 0     = 0
| otherwise = product [1..n]

However, we use a fast algorithm based on the split-recursive form:

factorial n =
2^(n - popCount n) * product [(q k)^k | forall k, k >= 1]
where
q k = product [j | forall j, n*2^(-k) < j <= n*2^(-k+1), odd j]

Not on Stackage, so not searched. Rational arithmetic in an irrational world.