newsynth-0.4.0.0: Exact and approximate synthesis of quantum circuits

Quantum.Synthesis.Ring

Description

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.

Synopsis

Rings

type Ring a = Num a Source #

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 where Source #

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.

Minimal complete definition

half

Methods

half :: a Source #

The value ½.

fromDyadic :: Dyadic -> a Source #

The unique ring homomorphism from ℤ[½] to any HalfRing. This exists because ℤ[½] is the free HalfRing.

Instances

 Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods (HalfRing a, RealFloat a) => HalfRing (Complex a) Source # Methods HalfRing a => HalfRing (Omega a) Source # Methods HalfRing a => HalfRing (Cplx a) Source # Methods (Eq a, HalfRing a) => HalfRing (RootTwo a) Source # Methods (HalfRing a, Nat n) => HalfRing (Matrix n n a) Source # Methodshalf :: Matrix n n a Source #fromDyadic :: Dyadic -> Matrix n n a Source #

Rings with √2

class Ring a => RootTwoRing a where Source #

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.

Minimal complete definition

roottwo

Methods

roottwo :: a Source #

The square root of 2.

fromZRootTwo :: RootTwoRing a => ZRootTwo -> a Source #

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

Instances

 Source # Methods Source # Methods (RootTwoRing a, RealFloat a) => RootTwoRing (Complex a) Source # Methods Ring a => RootTwoRing (Omega a) Source # Methods RootTwoRing a => RootTwoRing (Cplx a) Source # Methods (Eq a, Ring a) => RootTwoRing (RootTwo a) Source # Methods (RootTwoRing a, Nat n) => RootTwoRing (Matrix n n a) Source # Methodsroottwo :: Matrix n n a Source #fromZRootTwo :: ZRootTwo -> Matrix n n a Source #

Rings with 1/√2

class (HalfRing a, RootTwoRing a) => RootHalfRing a where Source #

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.

Minimal complete definition

roothalf

Methods

roothalf :: a Source #

The square root of ½.

fromDRootTwo :: RootHalfRing a => DRootTwo -> a Source #

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.

Instances

 Source # Methods Source # Methods (RootHalfRing a, RealFloat a) => RootHalfRing (Complex a) Source # Methods HalfRing a => RootHalfRing (Omega a) Source # Methods RootHalfRing a => RootHalfRing (Cplx a) Source # Methods (Eq a, HalfRing a) => RootHalfRing (RootTwo a) Source # Methods (RootHalfRing a, Nat n) => RootHalfRing (Matrix n n a) Source # Methodsroothalf :: Matrix n n a Source #fromDRootTwo :: DRootTwo -> Matrix n n a Source #

Rings with i

class Ring a => ComplexRing a where Source #

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

Minimal complete definition

i

Methods

i :: a Source #

The complex unit.

Instances

 (Ring a, RealFloat a) => ComplexRing (Complex a) Source # Methods Ring a => ComplexRing (Omega a) Source # Methods Ring a => ComplexRing (Cplx a) Source # Methodsi :: Cplx a Source # (Eq a, ComplexRing a) => ComplexRing (RootTwo a) Source # Methods (ComplexRing a, Nat n) => ComplexRing (Matrix n n a) Source # Methodsi :: Matrix n n a Source #

Rings with ω

class Ring a => OmegaRing a where Source #

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

Minimal complete definition

omega

Methods

omega :: a Source #

The square root of i.

Instances

 (RealFloat a, RootHalfRing a) => OmegaRing (Complex a) Source # Methods Ring a => OmegaRing (Omega a) Source # Methods (Ring a, RootHalfRing a) => OmegaRing (Cplx a) Source # Methods (Eq a, ComplexRing a, HalfRing a) => OmegaRing (RootTwo a) Source # Methods

Rings with particular automorphisms

Rings with complex conjugation

class Adjoint a where Source #

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.

Minimal complete definition

Methods

adj :: a -> a Source #

Compute the adjoint (complex conjugate transpose).

Instances

Rings with √2-conjugation

class Adjoint2 a where Source #

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.

Minimal complete definition

Methods

adj2 :: a -> a Source #

Compute the adjoint, mapping a + b√2 to ab√2.

Instances

Normed rings

class Ring r => NormedRing r where Source #

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

Minimal complete definition

norm

Methods

norm :: r -> Integer Source #

Instances

 Source # Methods NormedRing a => NormedRing (Omega a) Source # Methodsnorm :: Omega a -> Integer Source # NormedRing a => NormedRing (Cplx a) Source # Methodsnorm :: Cplx a -> Integer Source # (Eq a, NormedRing a) => NormedRing (RootTwo a) Source # Methods

Floor and ceiling

class Ring r => Floor r where Source #

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.

Methods

floor_of :: r -> Integer Source #

Compute the floor of x, i.e., the greatest integer n such that nx.

ceiling_of :: r -> Integer Source #

Compute the ceiling of x, i.e., the least integer n such that xn.

Instances

 Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods

Particular rings

The ring ℤ₂ of integers modulo 2

data Z2 Source #

The ring ℤ₂ of integers modulo 2.

Constructors

 Even Odd

Instances

 Source # Methods(==) :: Z2 -> Z2 -> Bool #(/=) :: Z2 -> Z2 -> Bool # Source # Methods(+) :: Z2 -> Z2 -> Z2 #(-) :: Z2 -> Z2 -> Z2 #(*) :: Z2 -> Z2 -> Z2 #negate :: Z2 -> Z2 #abs :: Z2 -> Z2 #signum :: Z2 -> Z2 # Source # MethodsshowsPrec :: Int -> Z2 -> ShowS #show :: Z2 -> String #showList :: [Z2] -> ShowS # Source # Methodsadj2 :: Z2 -> Z2 Source # Source # Methodsadj :: Z2 -> Z2 Source # Source # Methods Source # Methods

The ring D of dyadic fractions

data Dyadic Source #

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/2n 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.

Constructors

Instances

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

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

The ring ℚ of rational numbers

newtype Rationals Source #

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.

Constructors

 ToRationals FieldsunRationals :: Rational

Instances

 Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods Source # MethodsproperFraction :: Integral b => Rationals -> (b, Rationals) #truncate :: Integral b => Rationals -> b #round :: Integral b => Rationals -> b #ceiling :: Integral b => Rationals -> b #floor :: Integral b => Rationals -> b # Source # MethodsshowList :: [Rationals] -> ShowS # Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods

showsPrec_rational :: (Show a, Integral a) => Int -> Ratio a -> ShowS Source #

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

fromRationals :: Fractional a => Rationals -> a Source #

Conversion from Rationals to any Fractional type.

The ring R[√2]

data RootTwo a Source #

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

Constructors

 RootTwo !a !a

Instances

 Source # MethodsshowList :: [DRComplex] -> ShowS # Source # Methods Source # Methods Source # Methods Source # Methods Source # Methods Eq a => Eq (RootTwo a) Source # Methods(==) :: RootTwo a -> RootTwo a -> Bool #(/=) :: RootTwo a -> RootTwo a -> Bool # (Eq a, Fractional a) => Fractional (RootTwo a) Source # Methods(/) :: RootTwo a -> RootTwo a -> RootTwo a #recip :: RootTwo a -> RootTwo a # (Eq a, Num a) => Num (RootTwo a) Source # Methods(+) :: RootTwo a -> RootTwo a -> RootTwo a #(-) :: RootTwo a -> RootTwo a -> RootTwo a #(*) :: RootTwo a -> RootTwo a -> RootTwo a #negate :: RootTwo a -> RootTwo a #abs :: RootTwo a -> RootTwo a #signum :: RootTwo a -> RootTwo a # (Eq a, Ring a) => Ord (RootTwo a) Source # Methodscompare :: RootTwo a -> RootTwo a -> Ordering #(<) :: RootTwo a -> RootTwo a -> Bool #(<=) :: RootTwo a -> RootTwo a -> Bool #(>) :: RootTwo a -> RootTwo a -> Bool #(>=) :: RootTwo a -> RootTwo a -> Bool #max :: RootTwo a -> RootTwo a -> RootTwo a #min :: RootTwo a -> RootTwo a -> RootTwo a # (Show a, Eq a, Ring a) => Show (RootTwo a) Source # MethodsshowsPrec :: Int -> RootTwo a -> ShowS #show :: RootTwo a -> String #showList :: [RootTwo a] -> ShowS # ToQOmega a => ToQOmega (RootTwo a) Source # Methods (Eq a, NormedRing a) => NormedRing (RootTwo a) Source # Methods (Adjoint2 a, Num a) => Adjoint2 (RootTwo a) Source # Methodsadj2 :: RootTwo a -> RootTwo a Source # Adjoint a => Adjoint (RootTwo a) Source # Methodsadj :: RootTwo a -> RootTwo a Source # (Eq a, ComplexRing a, HalfRing a) => OmegaRing (RootTwo a) Source # Methods (Eq a, ComplexRing a) => ComplexRing (RootTwo a) Source # Methods (Eq a, HalfRing a) => RootHalfRing (RootTwo a) Source # Methods (Eq a, Ring a) => RootTwoRing (RootTwo a) Source # Methods (Eq a, HalfRing a) => HalfRing (RootTwo a) Source # Methods (ShowLaTeX a, Eq a, Ring a) => ShowLaTeX (RootTwo a) Source # Methods HalfRing a => RealPart (Omega a) (RootTwo a) Source # Methodsreal :: Omega a -> RootTwo a Source # ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b) Source # Methods Residue a b => Residue (RootTwo a) (RootTwo b) Source # Methodsresidue :: RootTwo a -> RootTwo b Source # Nat m => Show (Matrix m n DRComplex) # MethodsshowsPrec :: Int -> Matrix m n DRComplex -> ShowS #show :: Matrix m n DRComplex -> String #showList :: [Matrix m n DRComplex] -> ShowS # Nat m => Show (Matrix m n DRootTwo) # MethodsshowsPrec :: Int -> Matrix m n DRootTwo -> ShowS #show :: Matrix m n DRootTwo -> String #showList :: [Matrix m n DRootTwo] -> ShowS # Nat n => ShowLaTeX (Matrix n m DRComplex) Source # Methods

The ring ℤ[√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]

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

The field ℚ[√2]

The field ℚ[√2].

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

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]

data Cplx a Source #

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.

Constructors

 Cplx !a !a

Instances

 Source # MethodsshowList :: [DRComplex] -> ShowS # Source # Methods Eq a => Eq (Cplx a) Source # Methods(==) :: Cplx a -> Cplx a -> Bool #(/=) :: Cplx a -> Cplx a -> Bool # Fractional a => Fractional (Cplx a) Source # Methods(/) :: Cplx a -> Cplx a -> Cplx a #recip :: Cplx a -> Cplx a # Num a => Num (Cplx a) Source # Methods(+) :: Cplx a -> Cplx a -> Cplx a #(-) :: Cplx a -> Cplx a -> Cplx a #(*) :: Cplx a -> Cplx a -> Cplx a #negate :: Cplx a -> Cplx a #abs :: Cplx a -> Cplx a #signum :: Cplx a -> Cplx a # (Eq a, Show a, Num a) => Show (Cplx a) Source # MethodsshowsPrec :: Int -> Cplx a -> ShowS #show :: Cplx a -> String #showList :: [Cplx a] -> ShowS # ToQOmega a => ToQOmega (Cplx a) Source # Methods DenomExp a => DenomExp (Cplx a) Source # Methods NormedRing a => NormedRing (Cplx a) Source # Methodsnorm :: Cplx a -> Integer Source # (Adjoint2 a, Ring a) => Adjoint2 (Cplx a) Source # Methodsadj2 :: Cplx a -> Cplx a Source # (Adjoint a, Ring a) => Adjoint (Cplx a) Source # Methodsadj :: Cplx a -> Cplx a Source # (Ring a, RootHalfRing a) => OmegaRing (Cplx a) Source # Methods Ring a => ComplexRing (Cplx a) Source # Methodsi :: Cplx a Source # RootHalfRing a => RootHalfRing (Cplx a) Source # Methods RootTwoRing a => RootTwoRing (Cplx a) Source # Methods HalfRing a => HalfRing (Cplx a) Source # Methods (ShowLaTeX a, Ring a, Eq a) => ShowLaTeX (Cplx a) Source # Methodsshowlatex_p :: Int -> Cplx a -> ShowS Source # RealPart (Cplx a) a Source # Methodsreal :: Cplx a -> a Source # WholePart a b => WholePart (Cplx a) (Cplx b) Source # Methodsfrom_whole :: Cplx b -> Cplx a Source #to_whole :: Cplx a -> Cplx b Source # ToDyadic a b => ToDyadic (Cplx a) (Cplx b) Source # Methodsmaybe_dyadic :: Cplx a -> Maybe (Cplx b) Source # Residue a b => Residue (Cplx a) (Cplx b) Source # Methodsresidue :: Cplx a -> Cplx b Source # Nat m => Show (Matrix m n DRComplex) # MethodsshowsPrec :: Int -> Matrix m n DRComplex -> ShowS #show :: Matrix m n DRComplex -> String #showList :: [Matrix m n DRComplex] -> ShowS # Nat n => ShowLaTeX (Matrix n m DRComplex) Source # Methods

The ring ℤ[i] of Gaussian integers

The ring ℤ[i] of Gaussian integers.

fromZComplex :: ComplexRing a => ZComplex -> a Source #

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

The ring D[i]

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

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

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 ring ℚ[i] of Gaussian rationals.

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

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]

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

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

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]

The field ℚ[√2, i].

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

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.

Double precision complex floating point numbers.

Single precision complex floating point numbers.

The ring R[ω]

data Omega a Source #

The ring R[ω], where R is any ring, and ω = eiπ/4 is an 8th root of unity. The value Omega a b c d represents aω3+bω2+cω+d.

Constructors

 Omega !a !a !a !a

Instances

 Source # MethodsshowsPrec :: Int -> DOmega -> ShowS #showList :: [DOmega] -> ShowS # Source # Methods Source # Methodsdivmod :: ZOmega -> ZOmega -> (ZOmega, ZOmega) Source # Source # Methods Source # Methods Source # Methods Eq a => Eq (Omega a) Source # Methods(==) :: Omega a -> Omega a -> Bool #(/=) :: Omega a -> Omega a -> Bool # Fractional a => Fractional (Omega a) Source # Methods(/) :: Omega a -> Omega a -> Omega a #recip :: Omega a -> Omega a # Num a => Num (Omega a) Source # Methods(+) :: Omega a -> Omega a -> Omega a #(-) :: Omega a -> Omega a -> Omega a #(*) :: Omega a -> Omega a -> Omega a #negate :: Omega a -> Omega a #abs :: Omega a -> Omega a #signum :: Omega a -> Omega a # (Show a, Ring a) => Show (Omega a) Source # MethodsshowsPrec :: Int -> Omega a -> ShowS #show :: Omega a -> String #showList :: [Omega a] -> ShowS # ToQOmega a => ToQOmega (Omega a) Source # Methods NormedRing a => NormedRing (Omega a) Source # Methodsnorm :: Omega a -> Integer Source # (Adjoint2 a, Ring a) => Adjoint2 (Omega a) Source # Methodsadj2 :: Omega a -> Omega a Source # (Adjoint a, Ring a) => Adjoint (Omega a) Source # Methodsadj :: Omega a -> Omega a Source # Ring a => OmegaRing (Omega a) Source # Methods Ring a => ComplexRing (Omega a) Source # Methods HalfRing a => RootHalfRing (Omega a) Source # Methods Ring a => RootTwoRing (Omega a) Source # Methods HalfRing a => HalfRing (Omega a) Source # Methods Source # Methods HalfRing a => RealPart (Omega a) (RootTwo a) Source # Methodsreal :: Omega a -> RootTwo a Source # ToDyadic a b => ToDyadic (Omega a) (Omega b) Source # Methodsmaybe_dyadic :: Omega a -> Maybe (Omega b) Source # Residue a b => Residue (Omega a) (Omega b) Source # Methodsresidue :: Omega a -> Omega b Source # Nat m => Show (Matrix m n DOmega) # MethodsshowsPrec :: Int -> Matrix m n DOmega -> ShowS #show :: Matrix m n DOmega -> String #showList :: [Matrix m n DOmega] -> ShowS # Nat n => ShowLaTeX (Matrix n m DOmega) Source # Methods

omega_real :: Omega a -> a Source #

An inverse to the embedding RR[ω]: return the "real rational" part. In other words, map aω3+bω2+cω+d to d.

The ring ℤ[ω]

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:

fromZOmega :: OmegaRing a => ZOmega -> a Source #

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

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 :: (OmegaRing a, HalfRing a) => DOmega -> a Source #

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

The field ℚ[ω]

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

fromQOmega :: (OmegaRing a, Fractional a) => QOmega -> a Source #

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

class ToDyadic a b | a -> b where Source #

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

Minimal complete definition

Methods

maybe_dyadic :: a -> Maybe b Source #

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

Instances

to_dyadic :: ToDyadic a b => a -> b Source #

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

Real part

class RealPart a b | a -> b where Source #

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

Minimal complete definition

real

Methods

real :: a -> b Source #

Take the real part.

Instances

 RealPart (Cplx a) a Source # Methodsreal :: Cplx a -> a Source # HalfRing a => RealPart (Omega a) (RootTwo a) Source # Methodsreal :: Omega a -> RootTwo a Source #

Rings of integers

class WholePart a b | a -> b where Source #

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.

Minimal complete definition

Methods

from_whole :: b -> a Source #

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

to_whole :: a -> b Source #

The inverse of from_whole. Throws an error if the given element is not actually an integer in the ring.

Instances

 WholePart () () Source # Methodsfrom_whole :: () -> () Source #to_whole :: () -> () Source # Source # Methods Source # Methods Source # Methods WholePart a b => WholePart [a] [b] Source # Methodsfrom_whole :: [b] -> [a] Source #to_whole :: [a] -> [b] Source # WholePart a b => WholePart (Cplx a) (Cplx b) Source # Methodsfrom_whole :: Cplx b -> Cplx a Source #to_whole :: Cplx a -> Cplx b Source # (WholePart a a', WholePart b b') => WholePart (a, b) (a', b') Source # Methodsfrom_whole :: (a', b') -> (a, b) Source #to_whole :: (a, b) -> (a', b') Source # WholePart a b => WholePart (Vector n a) (Vector n b) Source # Methodsfrom_whole :: Vector n b -> Vector n a Source #to_whole :: Vector n a -> Vector n b Source # WholePart a b => WholePart (Matrix m n a) (Matrix m n b) Source # Methodsfrom_whole :: Matrix m n b -> Matrix m n a Source #to_whole :: Matrix m n a -> Matrix m n b Source #

Common denominators

class DenomExp a where Source #

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.

Minimal complete definition

Methods

denomexp :: a -> Integer Source #

Calculate the least denominator exponent k of a. Returns the smallest k≥0 such that a = b/√2k for some integral b.

denomexp_factor :: a -> Integer -> a Source #

Factor out a kth power of 1/√2 from a. In other words, calculate a√2k.

Instances

 DenomExp () Source # Methodsdenomexp :: () -> Integer Source #denomexp_factor :: () -> Integer -> () Source # Source # Methods Source # Methods DenomExp a => DenomExp [a] Source # Methodsdenomexp :: [a] -> Integer Source #denomexp_factor :: [a] -> Integer -> [a] Source # DenomExp a => DenomExp (Cplx a) Source # Methods (DenomExp a, DenomExp b) => DenomExp (a, b) Source # Methodsdenomexp :: (a, b) -> Integer Source #denomexp_factor :: (a, b) -> Integer -> (a, b) Source # DenomExp a => DenomExp (Vector n a) Source # Methodsdenomexp :: Vector n a -> Integer Source #denomexp_factor :: Vector n a -> Integer -> Vector n a Source # DenomExp a => DenomExp (Matrix m n a) Source # Methodsdenomexp :: Matrix m n a -> Integer Source #denomexp_factor :: Matrix m n a -> Integer -> Matrix m n a Source #

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 -> ShowS Source #

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.

class ToQOmega a where Source #

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

Minimal complete definition

toQOmega

Methods

toQOmega :: a -> QOmega Source #

Conversion to QOmega.

Instances

 Source # Methods Source # Methods Source # Methods Source # Methods ToQOmega a => ToQOmega (Omega a) Source # Methods ToQOmega a => ToQOmega (Cplx a) Source # Methods ToQOmega a => ToQOmega (RootTwo a) Source # Methods

Parity

class Parity a where Source #

A type class for things that have parity.

Minimal complete definition

parity

Methods

parity :: a -> Z2 Source #

Return the parity of something.

Instances

 Integral a => Parity a Source # Methodsparity :: a -> Z2 Source # Source # Methods

Auxiliary functions

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 2k, 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).

intsqrt :: Integral n => n -> n Source #

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