algebra-4.3: Constructive abstract algebra

Numeric.Domain.Euclidean

Synopsis

# Documentation

class PID d => Euclidean d where Source #

Methods

degree :: d -> Maybe Natural Source #

Euclidean (degree) function on r.

degree :: Division d => d -> Maybe Natural Source #

Euclidean (degree) function on r.

divide :: d -> d -> (d, d) infix 7 Source #

Division algorithm. a divide b calculates quotient and remainder of a divided by b.

let (q, r) = divide a p in p*q + r == a && degree r < degree q

divide :: Division d => d -> d -> (d, d) infix 7 Source #

Division algorithm. a divide b calculates quotient and remainder of a divided by b.

let (q, r) = divide a p in p*q + r == a && degree r < degree q

quot :: d -> d -> d infixl 7 Source #

rem :: d -> d -> d infixl 7 Source #

Instances

 Source # Methods GCDDomain d => Euclidean (Fraction d) Source # Methodsdivide :: Fraction d -> Fraction d -> (Fraction d, Fraction d) Source #quot :: Fraction d -> Fraction d -> Fraction d Source #rem :: Fraction d -> Fraction d -> Fraction d Source #

euclid :: Euclidean d => d -> d -> [(d, d, d)] Source #

Extended euclidean algorithm.

euclid f g == xs ==> all (\(r, s, t) -> r == f * s + g * t) xs

prs :: Euclidean r => r -> r -> [(r, r, r)] Source #

Arguments

 :: Euclidean r => [(r, r)] List of (m_i, v_i) -> r f with f = v_i (mod v_i)