A type class to denote rings. We make Ring a synonym of Haskell's Num type class, so that we can use the usual notation +, -, * for the ring operations. This is not a perfect fit, because Haskell's Num class also contains two non-ring operations abs and signum. By convention, for rings where these notions don't make sense (or are inconvenient to define), we set abs x = x and signum x = 1.

A type class for rings that contain ½.

Minimal complete definition: half. The default definition of fromDyadic uses the expression a*half^n. However, this can give potentially bad round-off errors for fixed-precision types where the expression half^n can underflow. For such rings, one should provide a custom definition, for example by using a/2^n instead.

A type class for rings that contain √2.

Minimal complete definition: roottwo. The default definition of fromZRootTwo uses the expression x+roottwo*y. However, this can give potentially bad round-off errors for fixed-precision types, where the expression roottwo*y can be vastly inaccurate if y is large. For such rings, one should provide a custom definition.

A type class for rings that contain 1/√2.

Minimal complete definition: roothalf. The default definition of fromDRootTwo uses the expression x+roottwo*y. However, this can give potentially bad round-off errors for fixed-precision types, where the expression roottwo*y can be vastly inaccurate if y is large. For such rings, one should provide a custom definition.

A type class for rings that contain a square root of -1.

A type class for rings that contain a square root of i, or equivalently, a fourth root of −1.

A type class for rings with complex conjugation, i.e., an automorphism mapping i to −i.

When instances of this type class are vectors or matrices, the conjugation also exchanges the roles of rows and columns (in other words, it is the adjoint).

For rings that are not complex, the conjugation can be defined to be the identity function.

A type class for rings with a √2-conjugation, i.e., an automorphism mapping √2 to −√2.

When instances of this type class are vectors or matrices, the √2-conjugation does not exchange the roles of rows and columns.

For rings that have no √2, the conjugation can be defined to be the identity function.

A (number-theoretic) norm on a ring R is a function N : R → ℤ such that N(rs) = N(r)N(s), for all r, s ∈ R. The norm also satisfies N(r) = 0 iff r = 0, and N(r) = ±1 iff r is a unit of the ring.

The floor and ceiling functions provided by the standard Haskell libraries are predicated on many unnecessary assumptions. This type class provides an alternative.

Minimal complete definition: floor_of or ceiling_of.

The ring ℤ₂ of integers modulo 2.

A dyadic fraction is a rational number whose denominator is a power of 2. We denote the dyadic fractions by D = ℤ[½].

We internally represent a dyadic fraction a/2ⁿ as a pair (a,n). Note that this representation is not unique. When it is necessary to choose a canonical representative, we choose the least possible n≥0.

Given a dyadic fraction r, return (a,n) such that r = a/2ⁿ, where n≥0 is chosen as small as possible.

Given a dyadic fraction r and an integer k≥0, such that a = r2^k is an integer, return a. If a is not an integer, the behavior is undefined.

We define our own variant of the rational numbers, which is an identical copy of the type Rational from the standard Haskell library, except that it has a more sensible Show instance.

An auxiliary function for printing rational numbers, using correct precedences, and omitting denominators of 1.

Conversion from Rationals to any Fractional type.

The ring R[√2], where R is any ring. The value RootTwo a b represents a + b √2.

The ring ℤ[√2].

Return a square root of an element of ℤ[√2], if such a square root exists, or else Nothing.

The ring D[√2] = ℤ[1/√2].

The field ℚ[√2].

The unique ring homomorphism from ℚ[√2] to any ring containing the rational numbers and √2. This exists because ℚ[√2] is the free such ring.

The ring R[i], where R is any ring. The reason we do not use the Complex a type from the standard Haskell libraries is that it assumes too much, for example, it assumes a is a member of the RealFloat class. Also, this allows us to define a more sensible Show instance.

The ring ℤ[i] of Gaussian integers.

The unique ring homomorphism from ℤ[i] to any ring containing i. This exists because ℤ[i] is the free such ring.

The ring D[i] = ℤ[½, i] of Gaussian dyadic fractions.

The unique ring homomorphism from D[i] to any ring containing ½ and i. This exists because D[i] is the free such ring.

The ring ℚ[i] of Gaussian rationals.

The unique ring homomorphism from ℚ[i] to any ring containing the rational numbers and i. This exists because ℚ[i] is the free such ring.

The ring D[√2, i] = ℤ[1/√2, i].

The unique ring homomorphism from D[√2, i] to any ring containing 1/√2 and i. This exists because D[√2, i] = ℤ[1/√2, i] is the free such ring.

The field ℚ[√2, i].

The unique ring homomorphism from ℚ[√2, i] to any ring containing the rational numbers, √2, and i. This exists because ℚ[√2, i] is the free such ring.

Double precision complex floating point numbers.

Single precision complex floating point numbers.

The ring R[ω], where R is any ring, and ω = e^iπ/4 is an 8th root of unity. The value Omega a b c d represents aω³+bω²+cω+d.

An inverse to the embedding R ↦ R[ω]: return the "real rational" part. In other words, map aω³+bω²+cω+d to d.

The ring ℤ[ω] of cyclotomic integers of degree 8. Such rings were first studied by Kummer around 1840, and used in his proof of special cases of Fermat's Last Theorem. See also:

• http://fermatslasttheorem.blogspot.com/2006/05/basic-properties-of-cyclotomic.html
• http://fermatslasttheorem.blogspot.com/2006/02/cyclotomic-integers.html
• Harold M. Edwards, "Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory".

The unique ring homomorphism from ℤ[ω] to any ring containing ω. This exists because ℤ[ω] is the free such ring.

Inverse of the embedding ℤ[√2] → ℤ[ω]. Note that ℤ[√2] = ℤ[ω] ∩ ℝ. This function takes an element of ℤ[ω] that is real, and converts it to an element of ℤ[√2]. It throws an error if the input is not real.

The ring D[ω]. Here D=ℤ[½] is the ring of dyadic fractions. In fact, D[ω] is isomorphic to the ring D[√2, i], but they have different Show instances.

The unique ring homomorphism from D[ω] to any ring containing ω and 1/2. This exists because D[ω] is the free such ring.

The field ℚ[ω] of cyclotomic rationals of degree 8.

The unique ring homomorphism from ℚ[ω] to any ring containing the rational numbers and ω. This exists because ℚ[ω] is the free such ring.

A type class relating "rational" types to their dyadic counterparts.

Convert a "rational" value to a "dyadic" value, if the denominator is a power of 2. Otherwise, throw an error.

A type class for rings that have a "real" component. A typical instance is a = DRComplex with b = DRootTwo.

A type class for rings that have a distinguished subring "of integers". A typical instance is a = DRootTwo, which has b = ZRootTwo as its ring of integers.

A type class for things from which a common power of 1/√2 (a least denominator exponent) can be factored out. Typical instances are DRootTwo, DRComplex, as well as tuples, lists, vectors, and matrices thereof.

Calculate and factor out the least denominator exponent k of a. Return (b,k), where a = b/(√2)^k and k≥0.

Generic show-like method that factors out a common denominator exponent.

A type class for things that can be exactly converted to ℚ[ω].

A type class for things that have parity.

Return the position of the rightmost "1" bit of an Integer, or -1 if none. Do this in time O(n log n), where n is the size of the integer (in digits).

If n is of the form 2^k, return k. Otherwise, return Nothing.

Return 1 + the position of the leftmost "1" bit of a non-negative Integer. Do this in time O(n log n), where n is the size of the integer (in digits).

For n ≥ 0, return the floor of the square root of n. This is done using integer arithmetic, so there are no rounding errors.