arithmoi-0.10.0.0: Efficient basic number-theoretic functions.

Copyright (c) 2018 Alexandre Rodrigues Baldé MIT Alexandre Rodrigues Baldé None Haskell2010

Math.NumberTheory.Euclidean

Description

This module exports a class to represent Euclidean domains.

Synopsis

# 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)

gcd :: a -> a -> a #

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)

lcm :: a -> a -> a #

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)

coprime :: a -> a -> Bool #

Test whether two arguments are coprime. Must match its default definition:

\x y -> coprime x y == isJust (1 divide gcd x y)
Instances
 Instance detailsDefined in Data.Euclidean Methodsgcd :: Double -> Double -> Double #lcm :: Double -> Double -> Double #coprime :: Double -> Double -> Bool # Instance detailsDefined in Data.Euclidean Methodsgcd :: Float -> Float -> Float #lcm :: Float -> Float -> Float #coprime :: Float -> Float -> Bool # Instance detailsDefined in Data.Euclidean Methodsdivide :: Int -> Int -> Maybe Int #gcd :: Int -> Int -> Int #lcm :: Int -> Int -> Int #coprime :: Int -> Int -> Bool # Instance detailsDefined in Data.Euclidean Methods Instance detailsDefined in Data.Euclidean Methods Instance detailsDefined in Data.Euclidean Methodsdivide :: Word -> Word -> Maybe Word #gcd :: Word -> Word -> Word #lcm :: Word -> Word -> Word #coprime :: Word -> Word -> Bool # Instance detailsDefined in Data.Euclidean Methodsdivide :: () -> () -> Maybe () #gcd :: () -> () -> () #lcm :: () -> () -> () #coprime :: () -> () -> Bool # Instance detailsDefined in Data.Euclidean Methodsgcd :: CFloat -> CFloat -> CFloat #lcm :: CFloat -> CFloat -> CFloat #coprime :: CFloat -> CFloat -> Bool # Instance detailsDefined in Data.Euclidean Methods Source # Instance details Methods Source # Instance details Methods Integral a => GcdDomain (Ratio a) Instance detailsDefined in Data.Euclidean Methodsdivide :: Ratio a -> Ratio a -> Maybe (Ratio a) #gcd :: Ratio a -> Ratio a -> Ratio a #lcm :: Ratio a -> Ratio a -> Ratio a #coprime :: Ratio a -> Ratio a -> Bool # Field a => GcdDomain (Complex a) Instance detailsDefined in Data.Euclidean Methodsdivide :: Complex a -> Complex a -> Maybe (Complex a) #gcd :: Complex a -> Complex a -> Complex a #lcm :: Complex a -> Complex a -> Complex a #coprime :: Complex a -> Complex a -> Bool # Instance detailsDefined in Data.Euclidean Methods Instance detailsDefined in Data.Euclidean Methods

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.

Minimal complete definition

Methods

quotRem :: a -> a -> (a, a) #

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)

rem :: a -> a -> a infixl 7 #

Remainder. Must match its default definition:

\x y -> rem x y == snd (quotRem x y)

degree :: a -> Natural #

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
 Instance detailsDefined in Data.Euclidean MethodsquotRem :: Double -> Double -> (Double, Double) #quot :: Double -> Double -> Double #rem :: Double -> Double -> Double # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Float -> Float -> (Float, Float) #quot :: Float -> Float -> Float #rem :: Float -> Float -> Float # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Int -> Int -> (Int, Int) #quot :: Int -> Int -> Int #rem :: Int -> Int -> Int # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Integer -> Integer -> (Integer, Integer) # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Natural -> Natural -> (Natural, Natural) # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Word -> Word -> (Word, Word) #quot :: Word -> Word -> Word #rem :: Word -> Word -> Word # Instance detailsDefined in Data.Euclidean MethodsquotRem :: () -> () -> ((), ()) #quot :: () -> () -> () #rem :: () -> () -> () #degree :: () -> Natural # Instance detailsDefined in Data.Euclidean MethodsquotRem :: CFloat -> CFloat -> (CFloat, CFloat) #quot :: CFloat -> CFloat -> CFloat #rem :: CFloat -> CFloat -> CFloat # Instance detailsDefined in Data.Euclidean MethodsquotRem :: CDouble -> CDouble -> (CDouble, CDouble) # Source # Instance details Methods Source # Instance details Methods Integral a => Euclidean (Ratio a) Instance detailsDefined in Data.Euclidean MethodsquotRem :: Ratio a -> Ratio a -> (Ratio a, Ratio a) #quot :: Ratio a -> Ratio a -> Ratio a #rem :: Ratio a -> Ratio a -> Ratio a #degree :: Ratio a -> Natural # Field a => Euclidean (Complex a) Instance detailsDefined in Data.Euclidean MethodsquotRem :: Complex a -> Complex a -> (Complex a, Complex a) #quot :: Complex a -> Complex a -> Complex a #rem :: Complex a -> Complex a -> Complex a #degree :: Complex a -> Natural # Instance detailsDefined in Data.Euclidean Methods Instance detailsDefined in Data.Euclidean Methods

newtype WrappedIntegral a #

Wrapper around Integral with GcdDomain and Euclidean instances.

Constructors

 WrapIntegral FieldsunwrapIntegral :: a
Instances
 Enum a => Enum (WrappedIntegral a) Instance detailsDefined in Data.Euclidean MethodsenumFrom :: WrappedIntegral a -> [WrappedIntegral a] #enumFromTo :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a] # Eq a => Eq (WrappedIntegral a) Instance detailsDefined in Data.Euclidean Methods(==) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(/=) :: WrappedIntegral a -> WrappedIntegral a -> Bool # Instance detailsDefined in Data.Euclidean Methods Num a => Num (WrappedIntegral a) Instance detailsDefined in Data.Euclidean Methods Ord a => Ord (WrappedIntegral a) Instance detailsDefined in Data.Euclidean Methods(<) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(<=) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(>) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(>=) :: WrappedIntegral a -> WrappedIntegral a -> Bool # Real a => Real (WrappedIntegral a) Instance detailsDefined in Data.Euclidean Methods Show a => Show (WrappedIntegral a) Instance detailsDefined in Data.Euclidean MethodsshowList :: [WrappedIntegral a] -> ShowS # Bits a => Bits (WrappedIntegral a) Instance detailsDefined in Data.Euclidean MethodstestBit :: WrappedIntegral a -> Int -> Bool # Instance detailsDefined in Data.Euclidean Methods Instance detailsDefined in Data.Euclidean Methods Num a => Semiring (WrappedIntegral a) Instance detailsDefined in Data.Euclidean Methods Num a => Ring (WrappedIntegral a) Instance detailsDefined in Data.Euclidean Methods

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 b

For 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).

isUnit :: (Eq a, GcdDomain a) => a -> Bool Source #

Check whether an element is a unit of the ring.