Safe Haskell	None
Language	Haskell2010

MathObj.FactoredRational

Contents

Type
Utilities

Description

A representation of rational numbers as lists of prime powers, allowing efficient representation, multiplication and division of large numbers, especially of the sort occurring in combinatorial computations.

The module also includes a method for generating factorials in factored form directly, and for generating all divisors of factored integers, or computing Euler's totient (phi) function and the Möbius (mu) function.

Synopsis

data T
factorial :: Integer -> T
eulerPhi :: T -> Integer
divisors :: T -> [T]
mu :: T -> Integer

Type

data T Source #

The type of factored rationals.

Instances are provided for Eq, Ord, Additive, Ring, ZeroTestable, Real, ToRational, Integral, RealIntegral, ToInteger, and Field.

Note that currently, addition is performed on factored rationals by converting them to normal rationals, performing the addition, and factoring. This could probably be made more efficient by finding a common denominator, pulling out common factors from the numerators, and performing the addition and factoring only on the relatively prime parts.

Instances

Eq T Source #
Instance details Defined in MathObj.FactoredRational Methods (==) :: T -> T -> Bool # (/=) :: T -> T -> Bool #
Ord T Source #
Instance details Defined in MathObj.FactoredRational Methods compare :: T -> T -> Ordering # (<) :: T -> T -> Bool # (<=) :: T -> T -> Bool # (>) :: T -> T -> Bool # (>=) :: T -> T -> Bool # max :: T -> T -> T # min :: T -> T -> T #
Show T Source #
Instance details Defined in MathObj.FactoredRational Methods showsPrec :: Int -> T -> ShowS # show :: T -> String # showList :: [T] -> ShowS #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods toInteger :: T -> Integer #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods quot :: T -> T -> T # rem :: T -> T -> T # quotRem :: T -> T -> (T, T) #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods toRational :: T -> Rational #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods (/) :: T -> T -> T # recip :: T -> T # fromRational' :: Rational -> T # (^-) :: T -> Integer -> T #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods abs :: T -> T # signum :: T -> T #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods div :: T -> T -> T # mod :: T -> T -> T # divMod :: T -> T -> (T, T) #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods (*) :: T -> T -> T # one :: T # fromInteger :: Integer -> T # (^) :: T -> Integer -> T #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods isZero :: T -> Bool #
C T Source #
Instance details Defined in MathObj.FactoredRational Methods zero :: T # (+) :: T -> T -> T # (-) :: T -> T -> T # negate :: T -> T #

Utilities

factorial :: Integer -> T Source #

Efficiently compute n! directly as a factored rational.

eulerPhi :: T -> Integer Source #

Compute Euler's totient function (eulerPhi n is the number of integers less than and relatively prime to n). Only makes sense for (nonnegative) integers.

divisors :: T -> [T] Source #

List of the divisors of n. Only makes sense for integers.

mu :: T -> Integer Source #

Möbius (mu) function of a positive integer: mu(n) = 0 if one or more repeated prime factors, 1 if n = 1, and (-1)^k if n is a product of k distinct primes.