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.

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

EuclideanDomain ZOmega

EuclideanDomain ZComplex

EuclideanDomain ZRootTwo

Functions

euclid_mod :: EuclideanDomain a => a -> a -> a

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

euclid_div :: EuclideanDomain a => a -> a -> a

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.

Auxiliary functions

rounddiv :: Integral a => a -> a -> a

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].