 |
 |
 |
 |
 |
 |
Startseite » Forum » Erweiterter Euklidischer Algorithmus
Erweiterter Euklidischer Algorithmus
Universität / Fachhochschule
Tags: Analysis
 
|
anonymous 16:34 Uhr, 30.11.2006  |
|
|---|---|
|
Hallo zusammen, ich habe ein kleines Verständnisproblem mit dem erweiterten euklidischen Algorithmus. Und zwar verstehe ich nicht, wie man s und t errechnen kann. Habe schon stundenlang gegoogelt aber kein einfaches Beispiel gefunden. Kann mir da jemand weiterhelfen?? Wie kommt man auf die Koeffizientenfolge bzw. schlussendlich dem s und dem t? Wenn jemand weiß, wo ich eine Implementierung in Java oder so finden kann - nur raus damit. Das würde mir vielleicht auch weiterhelfen. Besten dank schonmal,Gruß Benni |
|
| |
 |
|
|
Hallo, ich habe mal bei Wikipedia geschaut: de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus Gemäß den Angaben dort habe ich dann den Algorithmus in Python implementiert, ging einfach am schnellst, wenn auch nur langweilig prozedural. div(a,b) ist dabei die ganzzahlige Division, mod(a,b) gibt den Rest der Division zurück. def ggT(a, b): m=a n=b s=1 t=0 u=0 v=1 while n!=0: q=div(m,n) r=mod(m,n) m=n n=r u_=s-q*u v_=t-q*v s=u t=v u=u_ v=v_ print s print t print s*a+t*b Gruß, Marco |
|
|
|
|
|
Zitat: Und zwar verstehe ich nicht, wie man s und t errechnen kann. Die Berechnung erfolgt iterativ mit den Startpaaren s=1,t=0 und s=0,t=1, sodass 2 Gleichungen entstehen... a= 1* a + 0* b b= 0* a + 1* b de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus ...enthält einen Algorithmus. Du wirst erkennen, dass diese s,t nicht eindeutig sind. Man könnte geometrische Überlegungen anhand der Hesse-NF anstellen... Richtungen von Verbesserungen. Lass das bitte hier ausser acht. ---snip Zum Verständnis (kommt im Wiki-Beitrag nicht so klar rüber), schwafel ich mal etwas herum: Gegeben seien a,b € N. Betrachte Eigenschaften der ominösen Menge M := {s*a + t*b € N | s,t € Z}. Summen und Vielfache von x,y € M sind wiederum in M (was Operationen wie beim Additionsverfahren für Gleichungssysteme erlaubt). M enthält für a,b != 0 unendlich viele Elemente, also vor allem M != { } Die Menge M ist durch 0 nach unten beschränkt (weil enthält nur ... € N). Es gibt also ein KLEINSTES g € M (mit irgendeiner Darstellung g = S*a + T*b). - Diese Darstellung (in S,T) ist nicht eindeutig, wohl aber dieses g > 0 (wie gesagt: kleinstes). Es gibt bislang keinen Grund, sich mit diesem minimalen g zu beschäftigen..., hätte es nicht bzgl. a,b interessante Eigenschaften (I)+(II)... (I) Wenn d|a und d|b, dann a= x*d und b=y*d. Dann folgt jedoch aus g=S*x*d + T*y*d, dass d|g, kurz: Alle Teiler von a,b teilen auch g. Das wäre die Max. Eigenschaft eines ggT. Wenn denn g nur Teiler wäre von a,b... - Genau dies steht in (II). (II) Ich behaupte: g|a UND g|b. Also: a = x*g + r = x* (S*a + T*b) + r <=> r = (1- xS) *a + (-T) *b € M Dabei war 0 <= r < g (!!). Minimales g impliziert r=0, d.h. g|a. Genauso läuft es mit g|b. Zusammengefasst: Dieses g ist Teiler beider a,b und grösster, kurz: g=ggT Damit g äusserst interessant. --- snip Für die Berechnung waren die obigen + fetten Teile notwendig. Ich starte also mit etwas € M und bleibe mit Summen und Vielfachen € M, also drin. Und mein Ziel ist dieses minimale g (links aller Gleichheitszeichen). Natürlich kommt man auch aus, wenn man nur mit einfachen Differenzen drinbleibt (€ M), daher als Einstiegsbeispiel... Bsp.: Für a=6 und b=15 sieht das so aus... 6 = 1* 6 + 0*15 ... (Merker) 15= 0* 6 + 1*15 ----------------------- 9 = (-1)* 6 + 1*15 6 = 1* 6 + 0* 15 ----------------------- 6 = 1* 6 + 0* 15 3 = (-2)* 6 + 1*15 ----------------------- 3 = (-2)* 6 + 1*15 <-- Zwei Darstellungen des ggT übrigens 3 = 3* 6 + (-1)* 15 <-- --dto. ----------------------- 0 = 5 *6 + (-2) *15 Schaut man sich den obigen Merker an, könnte man mit 2* 6 die linke Seite schneller gegen Minimum bringen, schliesslich ist die linke Seite das Objekt unserer Begierde, das g = ggT... 6 = 1* 6 + 0*15 ... | *2 15= 0* 6 + 1*15 ----------------------- 3 = (-2) *6 + 1*15 Bei Betrachtung der linken Seiten ist mit 2*3 (unten) und 6 (oben) eh Schluss, es wird also keine Darstellung der 2 (links) oder gar 1 (=teilerfremd) möglich sein. - Drin bleiben in M ist also Voraussetzung UND schnell runterkommen (mit den linken Seiten) ist exakt der Wiki-Algorithmus. - Die erlaubten Vielfachen kamen bei mir didaktisch erst später ins Spiel. -Steele- Hoffe, jetzt geht klar... __________________ Irgendetwas in Quotes setzen, scheint nicht Foren-konform. - Die Darstellung dankt es mit merkwürdigen Slashes... - Das Angebot der Bescheidenheit ist eines. Ich halte Verbesserungen für angemessen. |
471421
471419