arithmoi-0.9.0.0: Efficient basic number-theoretic functions.

Copyright(c) 2018 Alexandre Rodrigues Baldé
LicenseMIT
MaintainerAlexandre Rodrigues Baldé <alexandrer_b@outlook.com>
Safe HaskellNone
LanguageHaskell2010

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

quotRem, divMod

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
Euclidean Int Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Methods

quotRem :: 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 #

Euclidean Integer Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Euclidean Natural Source #

Beware that extendedGCD does not make any sense for Natural.

Instance details

Defined in Math.NumberTheory.Euclidean

Euclidean Word Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Euclidean GaussianInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.GaussianIntegers

Euclidean EisensteinInteger Source # 
Instance details

Defined in Math.NumberTheory.Quadratic.EisensteinIntegers

Integral a => Euclidean (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

newtype WrappedIntegral a Source #

Wrapper around Integral, which has an Euclidean instance.

Constructors

WrappedIntegral 

Fields

Instances
Enum a => Enum (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Eq a => Eq (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Integral a => Integral (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Num a => Num (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Ord a => Ord (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Real a => Real (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Show a => Show (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean

Integral a => Euclidean (WrappedIntegral a) Source # 
Instance details

Defined in Math.NumberTheory.Euclidean