Numeric.Domain.Euclidean

Documentation

class PID d => Euclidean d where

Methods

degree :: d -> Maybe Natural

Euclidean (degree) function on r.

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

Euclidean (degree) function on r.

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

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

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

rem :: d -> d -> d infixl 7

Instances

Euclidean Integer

Methods

degree :: Integer -> Maybe Natural

divide :: Integer -> Integer -> (Integer, Integer)

quot :: Integer -> Integer -> Integer

rem :: Integer -> Integer -> Integer

GCDDomain d => Euclidean (Fraction d)

Methods

degree :: Fraction d -> Maybe Natural

divide :: Fraction d -> Fraction d -> (Fraction d, Fraction d)

quot :: Fraction d -> Fraction d -> Fraction d

rem :: Fraction d -> Fraction d -> Fraction d

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

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

chineseRemainder

Arguments

:: Euclidean r

=> [(r, r)]

List of (m_i, v_i)

-> r

f with f = v_i (mod v_i)