Safe Haskell | None |
---|
This module provides a type class for Euclidean domains. A Euclidean domain is a ring with a notion of division with remainder, and therefore greatest common divisors.
- class (Eq a, Ring a) => EuclideanDomain a where
- euclid_mod :: EuclideanDomain a => a -> a -> a
- euclid_div :: EuclideanDomain a => a -> a -> a
- euclid_gcd :: EuclideanDomain a => a -> a -> a
- extended_euclid :: EuclideanDomain a => a -> a -> (a, a, a, a, a)
- euclid_inverse :: EuclideanDomain a => a -> Maybe a
- is_unit :: EuclideanDomain a => a -> Bool
- inv_mod :: EuclideanDomain a => a -> a -> Maybe a
- euclid_divides :: EuclideanDomain a => a -> a -> Bool
- euclid_associates :: EuclideanDomain a => a -> a -> Bool
- euclid_extract_power :: EuclideanDomain a => a -> a -> (Integer, a)
- rounddiv :: Integral a => a -> a -> a
Euclidean domains
Definition
class (Eq a, Ring a) => EuclideanDomain a whereSource
A type class for Euclidean domains. A Euclidean domain is a ring with a Euclidean function and a division with remainder.
The Euclidean function for the Euclidean domain. This is a function rank : R\{0} → ℕ such that:
- for all nonzero a, b ∈ R, rank(a) ≤ rank(ab);
- if b ≠ 0 and (q,r) = a
divmod
b, then either r = 0 or rank(r) < rank(b).
divmod :: a -> a -> (a, a)Source
Given a and b≠0, return a quotient and remainder for division of a by b. Specifically, return (q,r) such that a = qb + r, and such that r = 0 or rank(r) < rank(b).
Functions
euclid_mod :: EuclideanDomain a => a -> a -> aSource
Calculate the remainder for the division of x by y. Assumes that y ≠ 0.
euclid_div :: EuclideanDomain a => a -> a -> aSource
Calculate the quotient for the division of x by y, ignoring the remainder, if any. This is typically, but not always, used in situations where the remainder is known to be 0 ahead of time. Assumes that y ≠ 0.
euclid_gcd :: EuclideanDomain a => a -> a -> aSource
Calculate the greatest common divisor in any Euclidean domain.
extended_euclid :: EuclideanDomain a => a -> a -> (a, a, a, a, a)Source
Perform the extended Euclidean algorithm. On inputs x and y, this returns (a,b,s,t,d) such that:
- d = gcd(x,y),
- ax + by = d,
- sx + ty = 0,
- at - bs = 1.
euclid_inverse :: EuclideanDomain a => a -> Maybe aSource
Find the inverse of a unit in a Euclidean domain. If the given
element is not a unit, return Nothing
.
is_unit :: EuclideanDomain a => a -> BoolSource
Determine whether an element of a Euclidean domain is a unit.
inv_mod :: EuclideanDomain a => a -> a -> Maybe aSource
Compute the inverse of a in R/(p), where R is a Euclidean
domain. Note: this works whenever a and p are relatively
prime. If a and p are not relatively prime, return Nothing
.
euclid_divides :: EuclideanDomain a => a -> a -> BoolSource
Check whether a is a divisor of b.
euclid_associates :: EuclideanDomain a => a -> a -> BoolSource
Check whether a and b are associates, i.e., differ at most by a multiplicative unit.
euclid_extract_power :: EuclideanDomain a => a -> a -> (Integer, a)Source
Given elements x and y of a Euclidean domain, find the largest k such that x can be written as y^{k}z. Return the pair (k, z).
If x=0 or y is a unit, return (0, x).