algebra-4.3.1: Constructive abstract algebra

Safe HaskellSafe
LanguageHaskell98

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

Arguments

:: d

elements divided by

-> d

divisor

-> (d, d)

quotient and remainder

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

Arguments

:: Division d 
=> d

elements divided by

-> d

divisor

-> (d, d)

quotient and remainder

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 #

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 #

chineseRemainder Source #

Arguments

:: Euclidean r 
=> [(r, r)]

List of (m_i, v_i)

-> r

f with f = v_i (mod v_i)