Quantum.Synthesis.EuclideanDomain

This module provides a type class for Euclidean domains. A Euclidean domain is a ring with a notion of division with remainder, and therefore greatest common divisors.

Euclidean domains

Definition

class (Eq a, Ring a) => EuclideanDomain a where

A type class for Euclidean domains. A Euclidean domain is a ring with a Euclidean function and a division with remainder.

Minimal complete definition

rank, divmod

Methods

rank :: a -> Integer

The Euclidean function for the Euclidean domain. This is a function rank : R\{0} → ℕ such that:

• for all nonzero a, b ∈ R, rank(a) ≤ rank(ab);
• if b ≠ 0 and (q,r) = a divmod b, then either r = 0 or rank(r) < rank(b).

divmod :: a -> a -> (a, a)

Given a and b≠0, return a quotient and remainder for division of a by b. Specifically, return (q,r) such that a = qb + r, and such that r = 0 or rank(r) < rank(b).

Instances

EuclideanDomain Integer

Methods

rank :: Integer -> Integer

divmod :: Integer -> Integer -> (Integer, Integer)

EuclideanDomain ZOmega

Methods

rank :: ZOmega -> Integer

divmod :: ZOmega -> ZOmega -> (ZOmega, ZOmega)

EuclideanDomain ZComplex

Methods

rank :: ZComplex -> Integer

divmod :: ZComplex -> ZComplex -> (ZComplex, ZComplex)

EuclideanDomain ZRootTwo

Methods

rank :: ZRootTwo -> Integer

divmod :: ZRootTwo -> ZRootTwo -> (ZRootTwo, ZRootTwo)

Functions

euclid_mod :: EuclideanDomain a => a -> a -> a infixl 7

Calculate the remainder for the division of x by y. Assumes that y ≠ 0.

euclid_div :: EuclideanDomain a => a -> a -> a infixl 7

Calculate the quotient for the division of x by y, ignoring the remainder, if any. This is typically, but not always, used in situations where the remainder is known to be 0 ahead of time. Assumes that y ≠ 0.

euclid_gcd :: EuclideanDomain a => a -> a -> a

Calculate the greatest common divisor in any Euclidean domain.

extended_euclid :: EuclideanDomain a => a -> a -> (a, a, a, a, a)

Perform the extended Euclidean algorithm. On inputs x and y, this returns (a,b,s,t,d) such that:

• d = gcd(x,y),
• ax + by = d,
• sx + ty = 0,
• at - bs = 1.

euclid_inverse :: EuclideanDomain a => a -> Maybe a

Find the inverse of a unit in a Euclidean domain. If the given element is not a unit, return Nothing.

is_unit :: EuclideanDomain a => a -> Bool

Determine whether an element of a Euclidean domain is a unit.

inv_mod :: EuclideanDomain a => a -> a -> Maybe a

Compute the inverse of a in R/(p), where R is a Euclidean domain. Note: this works whenever a and p are relatively prime. If a and p are not relatively prime, return Nothing.

euclid_divides :: EuclideanDomain a => a -> a -> Bool

Check whether a is a divisor of b.

euclid_associates :: EuclideanDomain a => a -> a -> Bool

Check whether a and b are associates, i.e., differ at most by a multiplicative unit.

euclid_extract_power :: EuclideanDomain a => a -> a -> (Integer, a)

Given elements x and y of a Euclidean domain, find the largest k such that x can be written as y^kz. Return the pair (k, z).

If x=0 or y is a unit, return (0, x).

Auxiliary functions

rounddiv :: Integral a => a -> a -> a infixl 7

For y ≠ 0, find the integer q closest to x / y. This works regardless of whether x and/or y are positive or negative. The distance q − x / y is guaranteed to be in (-1/2, 1/2].