arithmoi-0.9.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 (Eq a, Num a) => Euclidean a where Source #

A class to represent a Euclidean domain, which is basically an Integral without toInteger.

Minimal complete definition

Methods

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

When restriced to a subring of the Euclidean domain a isomorphic to Integer, this function should match quotRem for Integers.

divMod :: a -> a -> (a, a) Source #

When restriced to a subring of the Euclidean domain a isomorphic to Integer, this function should match divMod for Integers.

quot :: a -> a -> a Source #

rem :: a -> a -> a Source #

div :: a -> a -> a Source #

mod :: a -> a -> a Source #

gcd :: a -> a -> a Source #

gcd x y is the greatest number that divides both x and y.

lcm :: a -> a -> a Source #

lcm x y is the smallest number that both x and y divide.

coprime :: a -> a -> Bool Source #

Test whether two numbers are coprime.

extendedGCD :: 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).

Instances
 Source # Instance detailsDefined in Math.NumberTheory.Euclidean MethodsquotRem :: Int -> Int -> (Int, Int) Source #divMod :: Int -> Int -> (Int, Int) Source #quot :: Int -> Int -> Int Source #rem :: Int -> Int -> Int Source #div :: Int -> Int -> Int Source #mod :: Int -> Int -> Int Source #gcd :: Int -> Int -> Int Source #lcm :: Int -> Int -> Int Source #coprime :: Int -> Int -> Bool Source #extendedGCD :: Int -> Int -> (Int, Int, Int) Source # Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods Source # Beware that extendedGCD does not make any sense for Natural. Instance detailsDefined in Math.NumberTheory.Euclidean Methods Source # Instance detailsDefined in Math.NumberTheory.Euclidean MethodsquotRem :: Word -> Word -> (Word, Word) Source #divMod :: Word -> Word -> (Word, Word) Source #quot :: Word -> Word -> Word Source #rem :: Word -> Word -> Word Source #div :: Word -> Word -> Word Source #mod :: Word -> Word -> Word Source #gcd :: Word -> Word -> Word Source #lcm :: Word -> Word -> Word Source #extendedGCD :: Word -> Word -> (Word, Word, Word) Source # Source # Instance details Methods Source # Instance details Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods

newtype WrappedIntegral a Source #

Wrapper around Integral, which has an Euclidean instance.

Constructors

 WrappedIntegral FieldsunWrappedIntegral :: a
Instances
 Enum a => Enum (WrappedIntegral a) Source # Instance detailsDefined in Math.NumberTheory.Euclidean MethodsenumFrom :: WrappedIntegral a -> [WrappedIntegral a] #enumFromTo :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a] # Eq a => Eq (WrappedIntegral a) Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods(==) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(/=) :: WrappedIntegral a -> WrappedIntegral a -> Bool # Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods Num a => Num (WrappedIntegral a) Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods Ord a => Ord (WrappedIntegral a) Source # Instance detailsDefined in Math.NumberTheory.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) Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods Show a => Show (WrappedIntegral a) Source # Instance detailsDefined in Math.NumberTheory.Euclidean MethodsshowList :: [WrappedIntegral a] -> ShowS # Source # Instance detailsDefined in Math.NumberTheory.Euclidean Methods