Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell98 |
- class (C a, C a) => C a where
- extendedGCD :: a -> a -> (a, (a, a))
- gcd :: a -> a -> a
- lcm :: a -> a -> a
- coprime :: C a => a -> a -> Bool
- euclid :: (C a, C a) => (a -> a -> a) -> a -> a -> a
- extendedEuclid :: (C a, C a) => (a -> a -> (a, a)) -> a -> a -> (a, (a, a))
- extendedGCDMulti :: C a => [a] -> (a, [a])
- diophantine :: C a => a -> a -> a -> Maybe (a, a)
- diophantineMin :: C a => a -> a -> a -> Maybe (a, a)
- diophantineMulti :: C a => a -> [a] -> Maybe [a]
- chineseRemainder :: C a => (a, a) -> (a, a) -> Maybe (a, a)
- chineseRemainderMulti :: C a => [(a, a)] -> Maybe (a, a)
- propMaximalDivisor :: C a => a -> a -> a -> Property
- propGCDDiophantine :: (Eq a, C a) => a -> a -> Bool
- propExtendedGCDMulti :: (Eq a, C a) => [a] -> Bool
- propDiophantine :: (Eq a, C a) => a -> a -> a -> a -> Bool
- propDiophantineMin :: (Eq a, C a) => a -> a -> a -> a -> Bool
- propDiophantineMulti :: (Eq a, C a) => [(a, a)] -> Bool
- propDiophantineMultiMin :: (Eq a, C a) => [(a, a)] -> Bool
- propChineseRemainder :: (Eq a, C a) => a -> a -> [a] -> Property
- propDivisibleGCD :: C a => a -> a -> Bool
- propDivisibleLCM :: C a => a -> a -> Bool
- propGCDIdentity :: (Eq a, C a) => a -> Bool
- propGCDCommutative :: (Eq a, C a) => a -> a -> Bool
- propGCDAssociative :: (Eq a, C a) => a -> a -> a -> Bool
- propGCDHomogeneous :: (Eq a, C a) => a -> a -> a -> Bool
- propGCD_LCM :: (Eq a, C a) => a -> a -> Bool
Class
class (C a, C a) => C a where 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
Nothing
extendedGCD :: 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.
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
Least common multiple
Standard implementations for instances
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 (b,n) = chineseRemainder [(a0,m0), (a1,m1), ..., (an,mn)]
and all x
with x = b mod n
the congruences
x=a0 mod m0, x=a1 mod m1, ..., x=an mod mn
are fulfilled.
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