| Copyright | (c) 2018 Alexandre Rodrigues Baldé |
|---|---|
| License | MIT |
| Maintainer | Alexandre Rodrigues Baldé <alexandrer_b@outlook.com> |
| Stability | Provisional |
| Portability | Non-portable (GHC extensions) |
| Safe Haskell | None |
| Language | Haskell2010 |
Math.NumberTheory.Euclidean
Description
This module exports a class to represent Euclidean domains.
Synopsis
- class (Eq a, Num a) => Euclidean a where
- newtype WrappedIntegral a = WrappedIntegral {
- unWrappedIntegral :: a
Documentation
class (Eq a, Num a) => Euclidean a where #
Methods
When restriced to a subring of the Euclidean domain a isomorphic to
Integer, this function should match quotRem for Integers.
When restriced to a subring of the Euclidean domain a isomorphic to
Integer, this function should match divMod for Integers.
gcd x yx and y.
lcm x yx and y divide.
Test whether two numbers are coprime .
extendedGCD :: a -> a -> (a, a, a) #
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).
Instances
newtype WrappedIntegral a #
Wrapper around Integral, which has an Eucledian instance.
Constructors
| WrappedIntegral | |
Fields
| |