Safe Haskell | None |
---|

- Rings
- Rings with particular elements
- Rings with particular automorphisms
- Normed rings
- Floor and ceiling
- Particular rings
- The ring ℤ₂ of integers modulo 2
- The ring
**D**of dyadic fractions - The ring ℚ of rational numbers
- The ring
*R*[√2] - The ring ℤ[√2]
- The ring
**D**[√2] - The field ℚ[√2]
- The ring
*R*[*i*] - The ring ℤ[
*i*] of Gaussian integers - The ring
**D**[*i*] - The ring ℚ[
*i*] of Gaussian rationals - The ring
**D**[√2,*i*] - The ring ℚ[√2,
*i*] - The ring ℂ of complex numbers
- The ring
*R*[ω] - The ring ℤ[ω]
- The ring
**D**[ω] - The field ℚ[ω]

- Conversion to dyadic
- Real part
- Rings of integers
- Common denominators
- Conversion to ℚ[ω]
- Parity
- Auxiliary functions

This module provides type classes for rings. It also provides
several specific instances of rings, such as the ring ℤ₂ of
integers modulo 2, the ring ℚ of rational numbers, the ring ℤ[½] of
dyadic fractions, the ring ℤ[*i*] of Gaussian integers, the ring
ℤ[√2] of quadratic integers with radix 2, and the ring ℤ[ω] of
cyclotomic integers of degree 8.

- class Num a => Ring a
- class Ring a => HalfRing a where
- half :: a
- fromDyadic :: Dyadic -> a

- class Ring a => RootTwoRing a where
- roottwo :: a
- fromZRootTwo :: RootTwoRing a => ZRootTwo -> a

- class (HalfRing a, RootTwoRing a) => RootHalfRing a where
- roothalf :: a
- fromDRootTwo :: RootHalfRing a => DRootTwo -> a

- class Ring a => ComplexRing a where
- i :: a

- class Ring a => OmegaRing a where
- omega :: a

- class Adjoint a where
- adj :: a -> a

- class Adjoint2 a where
- adj2 :: a -> a

- class Ring r => NormedRing r where
- class Ring r => Floor r where
- floor_of :: r -> Integer
- ceiling_of :: r -> Integer

- data Z2
- data Dyadic = Dyadic !Integer !Integer
- decompose_dyadic :: Dyadic -> (Integer, Integer)
- integer_of_dyadic :: Dyadic -> Integer -> Integer
- newtype Rationals = ToRationals {}
- showsPrec_rational :: (Show a, Integral a) => Int -> Ratio a -> ShowS
- fromRationals :: Fractional a => Rationals -> a
- data RootTwo a = RootTwo !a !a
- type ZRootTwo = RootTwo Integer
- zroottwo_root :: ZRootTwo -> Maybe ZRootTwo
- type DRootTwo = RootTwo Dyadic
- type QRootTwo = RootTwo Rationals
- fromQRootTwo :: (RootTwoRing a, Fractional a) => QRootTwo -> a
- data Cplx a = Cplx !a !a
- type ZComplex = Cplx Integer
- fromZComplex :: ComplexRing a => ZComplex -> a
- type DComplex = Cplx Dyadic
- fromDComplex :: (ComplexRing a, HalfRing a) => DComplex -> a
- type QComplex = Cplx Rationals
- fromQComplex :: (ComplexRing a, Fractional a) => QComplex -> a
- type DRComplex = Cplx DRootTwo
- fromDRComplex :: (RootHalfRing a, ComplexRing a) => DRComplex -> a
- type QRComplex = Cplx QRootTwo
- fromQRComplex :: (RootTwoRing a, ComplexRing a, Fractional a) => QRComplex -> a
- type CDouble = Cplx Double
- type CFloat = Cplx Float
- data Omega a = Omega !a !a !a !a
- omega_real :: Omega a -> a
- type ZOmega = Omega Integer
- fromZOmega :: OmegaRing a => ZOmega -> a
- zroottwo_of_zomega :: ZOmega -> ZRootTwo
- type DOmega = Omega Dyadic
- fromDOmega :: (RootHalfRing a, ComplexRing a) => DOmega -> a
- type QOmega = Omega Rationals
- fromQOmega :: (RootHalfRing a, ComplexRing a, Fractional a) => QOmega -> a
- class ToDyadic a b | a -> b where
- maybe_dyadic :: a -> Maybe b

- to_dyadic :: ToDyadic a b => a -> b
- class RealPart a b | a -> b where
- real :: a -> b

- class WholePart a b | a -> b where
- from_whole :: b -> a
- to_whole :: a -> b

- class DenomExp a where
- denomexp :: a -> Integer
- denomexp_factor :: a -> Integer -> a

- denomexp_decompose :: (WholePart a b, DenomExp a) => a -> (b, Integer)
- showsPrec_DenomExp :: (WholePart a b, Show b, DenomExp a) => Int -> a -> ShowS
- class ToQOmega a where
- class Parity a where
- lobit :: Integer -> Integer
- log2 :: Integer -> Maybe Integer
- hibit :: Integer -> Int
- intsqrt :: Integral n => n -> n

# Rings

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.

# Rings with particular elements

We define several classes of rings with special elements.

## Rings with ½

class Ring a => HalfRing a whereSource

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.

The value ½.

fromDyadic :: Dyadic -> aSource

HalfRing Double | |

HalfRing Float | |

HalfRing Rational | |

HalfRing SymReal | |

HalfRing Rationals | |

HalfRing Dyadic | |

(HalfRing a, RealFloat a) => HalfRing (Complex a) | |

Precision e => HalfRing (FixedPrec e) | |

HalfRing a => HalfRing (Omega a) | |

HalfRing a => HalfRing (Cplx a) | |

(Eq a, HalfRing a) => HalfRing (RootTwo a) | |

(HalfRing a, Nat n) => HalfRing (Matrix n n a) |

## Rings with √2

class Ring a => RootTwoRing a whereSource

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.

The square root of 2.

fromZRootTwo :: RootTwoRing a => ZRootTwo -> aSource

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

RootTwoRing Double | |

RootTwoRing Float | |

RootTwoRing SymReal | |

(RootTwoRing a, RealFloat a) => RootTwoRing (Complex a) | |

Precision e => RootTwoRing (FixedPrec e) | |

Ring a => RootTwoRing (Omega a) | |

RootTwoRing a => RootTwoRing (Cplx a) | |

(Eq a, Ring a) => RootTwoRing (RootTwo a) | |

(RootTwoRing a, Nat n) => RootTwoRing (Matrix n n a) |

## Rings with 1/√2

class (HalfRing a, RootTwoRing a) => RootHalfRing a whereSource

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.

The square root of ½.

fromDRootTwo :: RootHalfRing a => DRootTwo -> aSource

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

RootHalfRing Double | |

RootHalfRing Float | |

RootHalfRing SymReal | |

(RootHalfRing a, RealFloat a) => RootHalfRing (Complex a) | |

Precision e => RootHalfRing (FixedPrec e) | |

HalfRing a => RootHalfRing (Omega a) | |

RootHalfRing a => RootHalfRing (Cplx a) | |

(Eq a, HalfRing a) => RootHalfRing (RootTwo a) | |

(RootHalfRing a, Nat n) => RootHalfRing (Matrix n n a) |

## Rings with *i*

class Ring a => ComplexRing a whereSource

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

(Ring a, RealFloat a) => ComplexRing (Complex a) | |

Ring a => ComplexRing (Omega a) | |

Ring a => ComplexRing (Cplx a) | |

(Eq a, ComplexRing a) => ComplexRing (RootTwo a) | |

(ComplexRing a, Nat n) => ComplexRing (Matrix n n a) |

## Rings with ω

class Ring a => OmegaRing a whereSource

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

(ComplexRing a, RootHalfRing a) => OmegaRing a | |

OmegaRing ZOmega | |

OmegaRing (Omega Z2) |

# Rings with particular automorphisms

## Rings with complex conjugation

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.

Adjoint Double | |

Adjoint Float | |

Adjoint Int | |

Adjoint Integer | |

Adjoint Rational | |

Adjoint SymReal | |

Adjoint Rationals | |

Adjoint Dyadic | |

Adjoint Z2 | |

(Adjoint a, Ring a) => Adjoint (Complex a) | |

Precision e => Adjoint (FixedPrec e) | |

(Adjoint a, Ring a) => Adjoint (Omega a) | |

(Adjoint a, Ring a) => Adjoint (Cplx a) | |

Adjoint a => Adjoint (RootTwo a) | |

(Nat n, Adjoint a) => Adjoint (Matrix n n a) |

## Rings with √2-conjugation

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.

Adjoint2 Int | |

Adjoint2 Integer | |

Adjoint2 Rational | |

Adjoint2 SymReal | |

Adjoint2 Rationals | |

Adjoint2 Dyadic | |

Adjoint2 Z2 | |

Precision e => Adjoint2 (FixedPrec e) | |

(Adjoint2 a, Ring a) => Adjoint2 (Omega a) | |

(Adjoint2 a, Ring a) => Adjoint2 (Cplx a) | |

(Adjoint2 a, Num a) => Adjoint2 (RootTwo a) | |

(Nat n, Adjoint2 a) => Adjoint2 (Matrix n n a) |

# Normed rings

class Ring r => NormedRing r whereSource

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.

NormedRing Integer | |

NormedRing a => NormedRing (Omega a) | |

NormedRing a => NormedRing (Cplx a) | |

(Eq a, NormedRing a) => NormedRing (RootTwo a) |

# Floor and ceiling

class Ring r => Floor r whereSource

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`

.

# Particular rings

## The ring ℤ₂ of integers modulo 2

The ring ℤ₂ of integers modulo 2.

## The ring **D** of dyadic fractions

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^{n} 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.

Eq Dyadic | |

Num Dyadic | |

Ord Dyadic | |

Real Dyadic | |

Show DOmega | |

Show DRComplex | |

Show Dyadic | |

ToQOmega Dyadic | |

DenomExp DOmega | |

DenomExp DRootTwo | |

Adjoint2 Dyadic | |

Adjoint Dyadic | |

HalfRing Dyadic | |

ShowLaTeX DOmega | |

ShowLaTeX Dyadic | |

WholePart DOmega ZOmega | |

WholePart DRootTwo ZRootTwo | |

WholePart Dyadic Integer | |

ToDyadic Rational Dyadic | |

ToDyadic Rationals Dyadic | |

ToDyadic Dyadic Dyadic | |

Nat m => Show (Matrix m n DOmega) | |

Nat m => Show (Matrix m n DRComplex) | |

Nat m => Show (Matrix m n DRootTwo) | |

Nat n => ShowLaTeX (Matrix n m DRComplex) | |

Nat n => ShowLaTeX (Matrix n m DOmega) |

decompose_dyadic :: Dyadic -> (Integer, Integer)Source

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

integer_of_dyadic :: Dyadic -> Integer -> IntegerSource

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

## The ring ℚ of rational numbers

showsPrec_rational :: (Show a, Integral a) => Int -> Ratio a -> ShowSSource

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

fromRationals :: Fractional a => Rationals -> aSource

Conversion from `Rationals`

to any `Fractional`

type.

## The ring *R*[√2]

The ring *R*[√2], where *R* is any ring. The value `RootTwo`

*a*
*b* represents *a* + *b* √2.

RootTwo !a !a |

Show DRComplex | |

Parity ZRootTwo | |

DenomExp DRootTwo | |

Floor QRootTwo | |

EuclideanDomain ZRootTwo | |

WholePart DRootTwo ZRootTwo | |

Eq a => Eq (RootTwo a) | |

(Eq a, Fractional a) => Fractional (RootTwo a) | |

(Eq a, Num a) => Num (RootTwo a) | |

(Eq a, Ring a) => Ord (RootTwo a) | |

(Show a, Eq a, Ring a) => Show (RootTwo a) | |

ToQOmega a => ToQOmega (RootTwo a) | |

(Eq a, NormedRing a) => NormedRing (RootTwo a) | |

(Adjoint2 a, Num a) => Adjoint2 (RootTwo a) | |

Adjoint a => Adjoint (RootTwo a) | |

(Eq a, ComplexRing a) => ComplexRing (RootTwo a) | |

(Eq a, HalfRing a) => RootHalfRing (RootTwo a) | |

(Eq a, Ring a) => RootTwoRing (RootTwo a) | |

(Eq a, HalfRing a) => HalfRing (RootTwo a) | |

(ShowLaTeX a, Eq a, Ring a) => ShowLaTeX (RootTwo a) | |

HalfRing a => RealPart (Omega a) (RootTwo a) | |

ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b) | |

Residue a b => Residue (RootTwo a) (RootTwo b) | |

Nat m => Show (Matrix m n DRComplex) | |

Nat m => Show (Matrix m n DRootTwo) | |

Nat n => ShowLaTeX (Matrix n m DRComplex) |

## The ring ℤ[√2]

zroottwo_root :: ZRootTwo -> Maybe ZRootTwoSource

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

.

## The ring **D**[√2]

## The field ℚ[√2]

fromQRootTwo :: (RootTwoRing a, Fractional a) => QRootTwo -> aSource

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

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.

Cplx !a !a |

Show DRComplex | |

EuclideanDomain ZComplex | |

Eq a => Eq (Cplx a) | |

Fractional a => Fractional (Cplx a) | |

Num a => Num (Cplx a) | |

(Eq a, Show a, Num a) => Show (Cplx a) | |

ToQOmega a => ToQOmega (Cplx a) | |

DenomExp a => DenomExp (Cplx a) | |

NormedRing a => NormedRing (Cplx a) | |

(Adjoint2 a, Ring a) => Adjoint2 (Cplx a) | |

(Adjoint a, Ring a) => Adjoint (Cplx a) | |

Ring a => ComplexRing (Cplx a) | |

RootHalfRing a => RootHalfRing (Cplx a) | |

RootTwoRing a => RootTwoRing (Cplx a) | |

HalfRing a => HalfRing (Cplx a) | |

(ShowLaTeX a, Ring a, Eq a) => ShowLaTeX (Cplx a) | |

RealPart (Cplx a) a | |

WholePart a b => WholePart (Cplx a) (Cplx b) | |

ToDyadic a b => ToDyadic (Cplx a) (Cplx b) | |

Residue a b => Residue (Cplx a) (Cplx b) | |

Nat m => Show (Matrix m n DRComplex) | |

Nat n => ShowLaTeX (Matrix n m DRComplex) |

## The ring ℤ[*i*] of Gaussian integers

fromZComplex :: ComplexRing a => ZComplex -> aSource

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

## The ring **D**[*i*]

fromDComplex :: (ComplexRing a, HalfRing a) => DComplex -> aSource

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

fromQComplex :: (ComplexRing a, Fractional a) => QComplex -> aSource

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

fromDRComplex :: (RootHalfRing a, ComplexRing a) => DRComplex -> aSource

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 ring ℚ[√2, *i*]

fromQRComplex :: (RootTwoRing a, ComplexRing a, Fractional a) => QRComplex -> aSource

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.

## The ring ℂ of complex numbers

We provide two versions of the complex numbers using floating point arithmetic.

## The ring *R*[ω]

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*ω^{3}+*b*ω^{2}+*c*ω+*d*.

Omega !a !a !a !a |

Show DOmega | |

DenomExp DOmega | |

OmegaRing ZOmega | |

ShowLaTeX DOmega | |

ShowLaTeX ZOmega | |

EuclideanDomain ZOmega | |

WholePart DOmega ZOmega | |

Eq a => Eq (Omega a) | |

Fractional a => Fractional (Omega a) | |

Num a => Num (Omega a) | |

(Show a, Ring a) => Show (Omega a) | |

ToQOmega a => ToQOmega (Omega a) | |

NormedRing a => NormedRing (Omega a) | |

(Adjoint2 a, Ring a) => Adjoint2 (Omega a) | |

(Adjoint a, Ring a) => Adjoint (Omega a) | |

OmegaRing (Omega Z2) | |

Ring a => ComplexRing (Omega a) | |

HalfRing a => RootHalfRing (Omega a) | |

Ring a => RootTwoRing (Omega a) | |

HalfRing a => HalfRing (Omega a) | |

ShowLaTeX (Omega Z2) | |

HalfRing a => RealPart (Omega a) (RootTwo a) | |

ToDyadic a b => ToDyadic (Omega a) (Omega b) | |

Residue a b => Residue (Omega a) (Omega b) | |

Nat m => Show (Matrix m n DOmega) | |

Nat n => ShowLaTeX (Matrix n m DOmega) |

omega_real :: Omega a -> aSource

An inverse to the embedding *R* ↦ *R*[ω]: return the "real
rational" part.
In other words, map *a*ω^{3}+*b*ω^{2}+*c*ω+*d* to *d*.

## The ring ℤ[ω]

type ZOmega = Omega IntegerSource

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

fromZOmega :: OmegaRing a => ZOmega -> aSource

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

zroottwo_of_zomega :: ZOmega -> ZRootTwoSource

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**[ω]

type DOmega = Omega DyadicSource

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.

fromDOmega :: (RootHalfRing a, ComplexRing a) => DOmega -> aSource

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

## The field ℚ[ω]

fromQOmega :: (RootHalfRing a, ComplexRing a, Fractional a) => QOmega -> aSource

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

# Conversion to dyadic

class ToDyadic a b | a -> b whereSource

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

maybe_dyadic :: a -> Maybe bSource

Convert a "rational" value to a "dyadic" value, if the
denominator is a power of 2. Otherwise, return `Nothing`

.

ToDyadic Rational Dyadic | |

ToDyadic Rationals Dyadic | |

ToDyadic Dyadic Dyadic | |

ToDyadic a b => ToDyadic (Omega a) (Omega b) | |

ToDyadic a b => ToDyadic (Cplx a) (Cplx b) | |

ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b) | |

ToDyadic a b => ToDyadic (Vector n a) (Vector n b) | |

ToDyadic a b => ToDyadic (Matrix m n a) (Matrix m n b) |

to_dyadic :: ToDyadic a b => a -> bSource

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

# Real part

# Rings of integers

class WholePart a b | a -> b whereSource

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.

from_whole :: b -> aSource

The embedding of the ring of integers into the larger ring.

The inverse of `from_whole`

. Throws an error if the given
element is not actually an integer in the ring.

WholePart () () | |

WholePart DOmega ZOmega | |

WholePart DRootTwo ZRootTwo | |

WholePart Dyadic Integer | |

WholePart a b => WholePart [a] [b] | |

WholePart a b => WholePart (Cplx a) (Cplx b) | |

(WholePart a a', WholePart b b') => WholePart (a, b) (a', b') | |

WholePart a b => WholePart (Vector n a) (Vector n b) | |

WholePart a b => WholePart (Matrix m n a) (Matrix m n b) |

# Common denominators

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.

denomexp_decompose :: (WholePart a b, DenomExp a) => a -> (b, Integer)Source

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

showsPrec_DenomExp :: (WholePart a b, Show b, DenomExp a) => Int -> a -> ShowSSource

Generic `show`

-like method that factors out a common denominator
exponent.

# Conversion to ℚ[ω]

`QOmega`

is the largest one of our "exact" arithmetic types. We
define a `toQOmega`

family of functions for converting just about
anything to `QOmega`

.

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

# Parity

A type class for things that have parity.

# Auxiliary functions

lobit :: Integer -> IntegerSource

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

log2 :: Integer -> Maybe IntegerSource

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