numeric-prelude-0.4.4: An experimental alternative hierarchy of numeric type classes
Safe HaskellSafe-Inferred
LanguageHaskell98

Algebra.PrincipalIdealDomain

Synopsis

Class

class (C a, C a) => C a Source #

A principal ideal domain is a ring in which every ideal (the set of multiples of some generating set of elements) is principal: That is, every element can be written as the multiple of some generating element. gcd a b gives a generator for the ideal generated by a and b. The algorithm above works whenever mod x y is smaller (in a suitable sense) than both x and y; otherwise the algorithm may run forever.

Laws:

  divides x (lcm x y)
  x `gcd` (y `gcd` z) == (x `gcd` y) `gcd` z
  gcd x y * z == gcd (x*z) (y*z)
  gcd x y * lcm x y == x * y

(etc: canonical)

Minimal definition: * nothing, if the standard Euclidean algorithm work * if extendedGCD is implemented customly, gcd and lcm make use of it

Instances

Instances details
C Int Source # 
Instance details

Defined in Algebra.PrincipalIdealDomain

Methods

extendedGCD :: Int -> Int -> (Int, (Int, Int)) Source #

gcd :: Int -> Int -> Int Source #

lcm :: Int -> Int -> Int Source #

C Int8 Source # 
Instance details

Defined in Algebra.PrincipalIdealDomain

Methods

extendedGCD :: Int8 -> Int8 -> (Int8, (Int8, Int8)) Source #

gcd :: Int8 -> Int8 -> Int8 Source #

lcm :: Int8 -> Int8 -> Int8 Source #

C Int16 Source # 
Instance details

Defined in Algebra.PrincipalIdealDomain

C Int32 Source # 
Instance details

Defined in Algebra.PrincipalIdealDomain

C Int64 Source # 
Instance details

Defined in Algebra.PrincipalIdealDomain

C Integer Source # 
Instance details

Defined in Algebra.PrincipalIdealDomain

C T Source # 
Instance details

Defined in Number.Peano

Methods

extendedGCD :: T -> T -> (T, (T, T)) Source #

gcd :: T -> T -> T Source #

lcm :: T -> T -> T Source #

Integral a => C (T a) Source # 
Instance details

Defined in MathObj.Wrapper.Haskell98

Methods

extendedGCD :: T a -> T a -> (T a, (T a, T a)) Source #

gcd :: T a -> T a -> T a Source #

lcm :: T a -> T a -> T a Source #

(C a, C a) => C (T a) Source # 
Instance details

Defined in MathObj.Polynomial

Methods

extendedGCD :: T a -> T a -> (T a, (T a, T a)) Source #

gcd :: T a -> T a -> T a Source #

lcm :: T a -> T a -> T a Source #

(Ord a, C a, C a) => C (T a) Source # 
Instance details

Defined in Number.Complex

Methods

extendedGCD :: T a -> T a -> (T a, (T a, T a)) Source #

gcd :: T a -> T a -> T a Source #

lcm :: T a -> T a -> T a Source #

C a => C (T a) Source # 
Instance details

Defined in MathObj.Wrapper.NumericPrelude

Methods

extendedGCD :: T a -> T a -> (T a, (T a, T a)) Source #

gcd :: T a -> T a -> T a Source #

lcm :: T a -> T a -> T a Source #

extendedGCD :: C a => a -> a -> (a, (a, a)) Source #

Compute the greatest common divisor and solve a respective Diophantine equation.

  (g,(a,b)) = extendedGCD x y ==>
       g==a*x+b*y   &&  g == gcd x y

TODO: This method is not appropriate for the PID class, because there are rings like the one of the multivariate polynomials, where for all x and y greatest common divisors of x and y exist, but they cannot be represented as a linear combination of x and y. TODO: The definition of extendedGCD does not return the canonical associate.

gcd :: C a => a -> a -> a Source #

The Greatest Common Divisor is defined by:

  gcd x y == gcd y x
  divides z x && divides z y ==> divides z (gcd x y)   (specification)
  divides (gcd x y) x

lcm :: C a => a -> a -> a Source #

Least common multiple

coprime :: C a => a -> a -> Bool Source #

Standard implementations for instances

euclid :: (C a, C a) => (a -> a -> a) -> a -> a -> a Source #

extendedEuclid :: (C a, C a) => (a -> a -> (a, a)) -> a -> a -> (a, (a, a)) Source #

Algorithms

extendedGCDMulti :: C a => [a] -> (a, [a]) Source #

Compute the greatest common divisor for multiple numbers by repeated application of the two-operand-gcd.

diophantine :: C a => a -> a -> a -> Maybe (a, a) Source #

A variant with small coefficients.

Just (a,b) = diophantine z x y means a*x+b*y = z. It is required that gcd(y,z) divides x.

diophantineMin :: C a => a -> a -> a -> Maybe (a, a) Source #

Like diophantine, but a is minimal with respect to the measure function of the Euclidean algorithm.

diophantineMulti :: C a => a -> [a] -> Maybe [a] Source #

 

chineseRemainder :: C a => (a, a) -> (a, a) -> Maybe (a, a) Source #

Not efficient enough, because GCD/LCM is computed twice.

chineseRemainderMulti :: C a => [(a, a)] -> Maybe (a, a) Source #

For Just (n,b) = chineseRemainderMulti [(m0,a0), (m1,a1), ..., (mk,ak)] and all x with x = b mod n, the congruences x=a0 mod m0, x=a1 mod m1, ..., x=ak mod mk are fulfilled. Also, n is the least common multiplier of all mi.

>>> PID.chineseRemainderMulti [(100,21), (10000,2021::Integer)]
Just (10000,2021)
>>> PID.chineseRemainderMulti [(97,90),(99,10),(100,0::Integer)]
Just (960300,100000)
>>> PID.chineseRemainderMulti [(95,30),(97,27),(98,8),(99,1::Integer)]
Just (89403930,1000000)
QC.listOf genResidueClass /\ \xs -> case PID.chineseRemainderMulti xs of Nothing -> True; Just (n,b) -> abs n == abs (foldl lcm 1 (map fst xs)) && map snd xs == map (mod b . fst) xs
\(QC.NonEmpty ms) b -> let xs = map (\(QC.NonZero m) -> (m, mod b m)) ms in case PID.chineseRemainderMulti xs of Nothing -> False; Just (n,c) -> abs n == abs (foldl lcm 1 (map QC.getNonZero ms)) && mod b n == (c::Integer)

Properties

propMaximalDivisor :: C a => a -> a -> a -> Property Source #

propGCDDiophantine :: (Eq a, C a) => a -> a -> Bool Source #

propExtendedGCDMulti :: (Eq a, C a) => [a] -> Bool Source #

propDiophantine :: (Eq a, C a) => a -> a -> a -> a -> Bool Source #

propDiophantineMin :: (Eq a, C a) => a -> a -> a -> a -> Bool Source #

propDiophantineMulti :: (Eq a, C a) => [(a, a)] -> Bool Source #

propDiophantineMultiMin :: (Eq a, C a) => [(a, a)] -> Bool Source #

propChineseRemainder :: (Eq a, C a) => a -> a -> [a] -> Property Source #

propDivisibleGCD :: C a => a -> a -> Bool Source #

propDivisibleLCM :: C a => a -> a -> Bool Source #

propGCDIdentity :: (Eq a, C a) => a -> Bool Source #

propGCDCommutative :: (Eq a, C a) => a -> a -> Bool Source #

propGCDAssociative :: (Eq a, C a) => a -> a -> a -> Bool Source #

propGCDHomogeneous :: (Eq a, C a) => a -> a -> a -> Bool Source #

propGCD_LCM :: (Eq a, C a) => a -> a -> Bool Source #