| Copyright | (c) 2018 Alexandre Rodrigues Baldé |
|---|---|
| License | MIT |
| Maintainer | Alexandre Rodrigues Baldé <alexandrer_b@outlook.com> |
| Safe Haskell | None |
| Language | Haskell2010 |
Math.NumberTheory.Euclidean
Description
This module exports a class to represent Euclidean domains.
Synopsis
- class Semiring a => GcdDomain a where
- class GcdDomain a => Euclidean a where
- newtype WrappedIntegral a = WrapIntegral {
- unwrapIntegral :: a
- extendedGCD :: (Eq a, Num a, Euclidean a) => a -> a -> (a, a, a)
- isUnit :: (Eq a, GcdDomain a) => a -> Bool
Documentation
class Semiring a => GcdDomain a where #
GcdDomain represents a
GCD domain.
This is a domain, where GCD can be defined,
but which does not necessarily allow a well-behaved
division with remainder (as in Euclidean domains).
For example, there is no way to define rem over
polynomials with integer coefficients such that
remainder is always "smaller" than divisor. However,
gcd is still definable, just not by means of
Euclidean algorithm.
All methods of GcdDomain have default implementations
in terms of Euclidean. So most of the time
it is enough to write:
instance GcdDomain Foo instance Euclidean Foo where quotRem = ... degree = ...
Minimal complete definition
Nothing
Methods
divide :: a -> a -> Maybe a infixl 7 #
Division without remainder.
\x y -> (x * y) `divide` y == Just x
\x y -> maybe True (\z -> x == z * y) (x `divide` y)
Greatest common divisor. Must satisfy
\x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
\x y z -> isJust (gcd (x * z) (y * z) `divide` z)
Lowest common multiple. Must satisfy
\x y -> isJust (lcm x y `divide` x) && isJust (lcm x y `divide` y)
\x y z -> isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)
Test whether two arguments are coprime. Must match its default definition:
\x y -> coprime x y == isJust (1 `divide` gcd x y)
Instances
class GcdDomain a => Euclidean a where #
Informally speaking, Euclidean is a superclass of Integral,
lacking toInteger, which allows to define division with remainder
for a wider range of types, e. g., complex integers
and polynomials with rational coefficients.
Euclidean represents a
Euclidean domain
endowed by a given Euclidean function degree.
Methods
Division with remainder.
\x y -> y == 0 || let (q, r) = x `quotRem` y in x == q * y + r
quot :: a -> a -> a infixl 7 #
Division. Must match its default definition:
\x y -> quot x y == fst (quotRem x y)
Remainder. Must match its default definition:
\x y -> rem x y == snd (quotRem x y)
Euclidean (aka degree, valuation, gauge, norm) function on a. Usually fromIntegral . abs.
degree is rarely used by itself. Its purpose
is to provide an evidence of soundness of quotRem
by testing the following property:
\x y -> y == 0 || let (q, r) = x `quotRem` y in (r == 0 || degree r < degree y)
Instances
newtype WrappedIntegral a #
Constructors
| WrapIntegral | |
Fields
| |
Instances
extendedGCD :: (Eq a, Num a, Euclidean a) => a -> a -> (a, a, a) Source #
Calculate the greatest common divisor of two numbers and coefficients for the linear combination.
For signed types satisfies:
case extendedGCD a b of
(d, u, v) -> u*a + v*b == d
&& d == gcd a bFor unsigned and bounded types the property above holds, but since u and v must also be unsigned,
the result may look weird. E. g., on 64-bit architecture
extendedGCD (2 :: Word) (3 :: Word) == (1, 2^64-1, 1)
For unsigned and unbounded types (like Natural) the result is undefined.
For signed types we also have
abs u < abs b || abs b <= 1 abs v < abs a || abs a <= 1
(except if one of a and b is minBound of a signed type).