Euclidean

Contents

Description

Dieses Modull stellt die Typklasse EuclideanRing fuer euklidische Ringe und die wichtige Funktion gcd zur Bestimmung groesster gemeinsamer Teiler zur Verfuegung.

Synopsis

Typklasse fuer euklidische Ringe

class IntegralDomain a ⇒ EuclideanRing a where

Typklasse fuer euklidische Ringe, also Integritaetsbereiche R zusammen mit einer Normabbildung von R \ {0} in die natuerlichen Zahlen mit null, sodass folgendes Axiom erfuellt ist:

Fuer jedes Element x aus R und jedes von null verschiedene Element y aus R gilt: Entweder ist y ein Teiler von x, oder es existiert ein von null verschiedener Rest r derart, dass y ein Teiler von x - r ist und die Norm von r echt kleiner als die von y ist.

Methods

degree ∷ a → Nat

Die Normabbildung. Muss auf dem Nullelement nicht definiert sein.

quotRem

Arguments

∷ a

Dividend x

→ a

Divisor y, nicht null

→ (a, a)

(q,r) mit x = qy + r und N(r) < N(y)

Division mit Rest.

Instances

newtype ER a

Dummytyp, um ueberlappende Instanzdeklarationen vermeiden zu koennen.

Constructors

ER 

Fields

unER ∷ a
 

Instances

Enum a ⇒ Enum (ER a) 
Eq a ⇒ Eq (ER a) 
(Fractional a, EuclideanRing a) ⇒ Fractional (ER a) 
(Integral a, EuclideanRing a) ⇒ Integral (ER a) 
(Num a, EuclideanRing a) ⇒ Num (ER a) 
Ord a ⇒ Ord (ER a) 
(Real a, EuclideanRing a) ⇒ Real (ER a) 
(Show a, EuclideanRing a) ⇒ Show (ER a) 
Arbitrary a ⇒ Arbitrary (ER a) 
HasFloatingApprox a ⇒ HasFloatingApprox (ER a) 
HasTestableAssociatedness a ⇒ HasTestableAssociatedness (ER a) 
IntegralDomain a ⇒ IntegralDomain (ER a) 
Ring a ⇒ Ring (ER a) 
Field a ⇒ Field (ER a) 
EuclideanRing a ⇒ EuclideanRing (ER a) 
(Integral a, EuclideanRing a) ⇒ HasAnnihilatingPolynomials (ER a) 

Umsetzungen des erweiterten euklidischen Algorithmus

gcd

Arguments

∷ EuclideanRing a 
⇒ a

x

→ a

y

→ (a, a, a, a)

(u,v,s,t), mit d = ux + vy ein groesster gemeinsamer Teiler von x und y, x = ds und y = dt.

Bestimmt einen groessten gemeinsamen Teiler ueber den euklidischen Algorithmus. Dieser wird nicht in irgendeiner kanonisierten Form geliefert (eine solche gibt es in einem allgemeinen euklidischen Ring ja auch gar nicht), sondern sollte nur als bis auf Assoziiertheit interpretiert werden.

gcd' ∷ (EuclideanRing a, HasTestableAssociatedness a) ⇒ a → a → (a, a, a, a)

Wie gcd, aber mit folgender Zusatzeigenschaft:

Sollte x zu y assoziiert sein (d.h. sollte ein u mit y = ux existieren), wird garantiert, dass der Aufruf gcd' x y zu (1,0,1,u) fuehrt.

Bei gcd dagegen kann auch (0,1,u,1) zurueckgegeben werden. Dies ist im Smith-Modul sehr wichtig, um Terminierung beim Algorithmus fuer die Smitsche Normalform zu gewaehrleisten.

areCoprime ∷ (EuclideanRing a, HasTestableAssociatedness a) ⇒ a → a → Bool

Testet, ob zwei uebergebene Ringelemente zueinander teilerfremd sind.

Funktionen fuer "Euklidketten" (Sturmketten in allemeinerem Kontext)

euclidChain ∷ EuclideanRing a ⇒ a → a → [a]

Eine Folge (S_0,...,S_n) von Polynomen heisst genau dann /Sturmkette bezueglich des Intervalls [a,b], wenn fuer alle x aus [a,b]/ gilt: Sollte S_k(x) = 0 fuer ein k mit 0 < k < n sein, so gilt S_(k-1)(x) S_(k+1)(x) < 0.

Zu jeder rationalen Funktion R S^(-1), wobei R und S Polynome sind, gibt es die zugehoerige Sturmkette. Diese ist definiert als (S_0,...,S_n), wobei S_k = P_k P_n^(-1) (die Division geht auf) und die P_i aus dem euklidischen Algorithmus, angewendet auf R und S stammen, also 

 P_0 = S
 P_1 = R
 P_(k-1) = Q_k P_k - P_(k+1)

fuer gewisse Reste P_(k+1) fuer alle k >= 1 erfuellen.

Angewendet wird die Funktion euclidChain in RootFinding auf Polynome. Derart spezialisiert bestimmt sie zu zwei gegebenen Polynomen R und S ihre zugehoerige Sturmkette. Sie funktioniert aber auch allgemeiner in beliebigen euklidischen Ringen.

(Der Begriff der zum Bruch zugeordneten Euklidkette ist eigentlich nicht wohldefiniert, da verschiedene Wahlen des Rests in quotRem zu verschiedenen Ketten fuehren. Das ist aber auch das einzige Hindernis: Trifft man die Wahlen konsistent, etwa indem man bei ganzen Zahlen fordert, dass der Rest positiv ist, so sind die Ketten aller Darstellungen eines Bruchs gleich.)

QuickCheck

check_Euclidean ∷ IO ()