Erweiterter Euklid - Ausgabe

[StGo]

Hallo zusammen,

ich habe mir einen EEA geschrieben bin aber mit meiner Ausgabe unzufrieden. Die Rechnung ist richtig und für meinen Gebrauch reicht das auch. Aber ich würde es gerne etwas aufhübschen und suche jemand der mir einen Tip geben kann bzw mir mit seiner Erfahrung helfen kann.

Meine Ausgabe sieht folgendermassen aus:

Bitte die erste Zahl eingeben:
216
Bitte die zweite Zahl eingeben:
137
m= 137 n= 79 q= 1 s= 1 t= -1
m= 79 n= 58 q= 1 s= -1 t= 2
m= 58 n= 21 q= 1 s= 2 t= -3
m= 21 n= 16 q= 2 s= -5 t= 8
m= 16 n= 5 q= 1 s= 7 t= -11
m= 5 n= 1 q= 3 s= -26 t= 41
m= 1 n= 0 q= 5 s= 137 t= -216
Ergebnis: -216

Das unschöne sind das ich erstens auf der Seite der multiplikativen Inversen eine Zeile (unterste) zu viel habe und das ich keine Idee habe wie ich die Spalten sortieren kann.

Prinzipiell könnte ich das ganze initialisieren und so anfnagne:

m= 0 n= 216 q= 0 s= 1 t= 0
m= 216 n= 137 q= 1 s= 1 t= 0.......

bekomme ich aber nicht hin.

Hier mal mein Code

package rechner;

public class ErweiterterEuklidischerAlogrithmus {
	
	int rest = 0;
	int q = 0;
	int uHelp = 1;
	int vHelp = 0;
	
	int s = 0;
	int t = 1;
	
	int sLast;
	int tLast;
	
	void EEA(int m, int n){
	
		while (n>0) {
			
			q = m/n;
	        rest = m-(q*n);
	        
	        m = n;
	        n = rest;
	        
	        
	        rest = uHelp-(q*s);
	        uHelp = s;
	        s = rest;
	        
	        rest = vHelp-(q*t);
	        vHelp = t;
	        t = rest;
	        
	        System.out.println("m= " +m +" n= " +n +" q= " +q +" s= " +s +" t= " +t);
	        
	        sLast = s;
	        tLast = t;
	        }
		
		 System.out.println("Ergebnis: " +tLast);
	}
}

Oder das Projekt auf meiner Dropbox:
https://dl.dropbox.com/u/3557897/Taschenrechner.zip

Danke für eure Hilfe.

Gruß

 

[SlaterB]

habs mir ein bisschen angeschaut, auch
Erweiterter euklidischer Algorithmus ? Wikipedia
mit dem dortigen Beispiel 99, 78 und dann der Tabelle

a 	b 	q 	u 	s 	v 	t
0 	99 	0 	0 	1 	1 	0
99 	78 	1 	1 	0 	0 	1
78 	21 	3 	0 	1 	1 	-1
21 	15 	1 	1 	-3 	-1 	4
15 	6 	2 	-3 	4 	4 	-5
6 	3 	2 	4 	-11 	-5 	14
3 	0 		-11 	26 	14 	-33

das kommt ja weitgehend raus,

aber ich habe jetzt immer noch keine Idee was bei dir denn nun ungewünscht läuft,
nenne doch bitte konkrete einzelne Werte und Begrundungen, leichter im 99, 78-Beispiel

 

[StGo]

Morgen,

eigentlich ganz einfach. Du hast es in deinen Bsp ja stehen. Wenn ich meine while Schleife los lasse und die erste Ausgabe bekomme fehlen die ersten beiden Zeilen. Grund ist das ich meine Initialisierungswerte und die erste Zeile nicht Ausgegeben bekomme. Meine Ausgabe steht am Ende und gibt deswegen nur die Zeilen ab der ersten Berechnung aus. Dazu kommt das beim Berechnen der multiplikativen Inversen die Zeilen nicht synchron zum Euklid sind.

a 	b 	q 	u 	s 	v 	t
78 	21 	3 	1 	-3 	-1 	4
21 	15 	1 	-3 	4 	4 	-5
15 	6 	2 	4 	-11 -5 	14
6 	3 	2 	-11 26 	14 	-33
3 	0 		x	x 	x 	x

x bedeutet das im letzten durchlauf der Schleife Werte berechnet werden denen ich keine Sinn abgewinnen kann.

Das Problem ist also kurz gesagt das meine while Schleife wahrscheinlich nicht besonders intelligent aufgebaut ist.

Danke

Gruß

 

[SlaterB]

also deine neuen Ausgaben kann ich nicht nachvollziehen, das ursprüngliche Programm bietet

m= 78 n= 21 q= 1 s= 1 t= -1
m= 21 n= 15 q= 3 s= -3 t= 4
m= 15 n= 6 q= 1 s= 4 t= -5
m= 6 n= 3 q= 2 s= -11 t= 14
m= 3 n= 0 q= 2 s= 26 t= -33
Ergebnis: -33

die Zeilen stimmen dabei halbwegs, wobei 5 statt 7 Werte immer fraglich ist und manche Werte ja über die Zeilen durchgereicht werden/ doppelt auftauchen, aber die -33 etwa in der letzten Zeile zu 3/0 ist doch genau nach Vorbild,
warum postest du das jetzt in der vorletzen 6/3-Zeile?
vielleicht hast du bei dir Änderungen, die kann ich aber kaum beurteilen

bleiben die ersten beiden Zeilen,
ich habe bisher lieber vermieden, die genaue Bedeutung von u, s, v, t usw. nachzulesen, schon gar nicht was davon in deinem Programm q ist, was fehlt usw., ein dickes Knäuel,

ich schätze aber dass die Anfangszeilen fest sind, oder hast du ein Gegenbeispiel? du selber wirst die Bedeutung doch sicher wissen,
schreibe dann einfach zwei Zeilen vor der Schleife, "0, "+m+", 1, 0, 0, 1" usw.

 

[StGo]

Zu Erklärung:

m und n sind die Eingabewerte
q ist ganzzahlige Division
s und n sind die multiplikativen inversen
u und v dienen nur der Hilfe.

Wenn man EEA per Hand rechnet kann man u und v weglassen da man erst den Euklid (m, n, q) berechnet und dann aus den Werten Rückwärts mit t= (ggt - s *m)/n beide Spalten berechnen kann. Um das ganz zu programmieren kann ich schlecht erst m, n, q berechnen und dann den Rest. Sondern ich mache es wie in Wikipedia beschrieben mit Hilfsvariablen. Da ist nichts besonderes dran oder irgendwas auf meinem Mist gewachsen.

Die Rechnung ist ja auch OK. Ich habe ein Problem mit der Ausgabe. Wenn ich zwei Parameter m und n übergebe aus meiner Eingabe kann ich nicht hin gehen und die Schleife mit m=0 initialisieren um die erste Zeile zu bekommen. Wie soll ich dann in der zweiten Zeile meinen eigentlichen Wert für n einfügen den ich überschrieben habe.
In der Tabelle von Wikipedia ist das einfach da Papier geduldig ist. Per Hand kann ich das auch so rechnen.

Danke Gruß

 

[Flown]

Die Rechnung ist ja auch OK. Ich habe ein Problem mit der Ausgabe. Wenn ich zwei Parameter m und n übergebe aus meiner Eingabe kann ich nicht hin gehen und die Schleife mit m=0 initialisieren um die erste Zeile zu bekommen. Wie soll ich dann in der zweiten Zeile meinen eigentlichen Wert für n einfügen den ich überschrieben habe.
In der Tabelle von Wikipedia ist das einfach da Papier geduldig ist. Per Hand kann ich das auch so rechnen.

Das "Problem" das du hast hat dir SlaterB schon gelöst. Aber nachdem du anscheinend auch nicht gerne liest helf ich dir auf die Sprünge:

    void EEA(int m, int n){
        System.out.println("m= " +m +" n= 0 q= 0 s= 1 t= 0");
        System.out.println("m= 0 n= " + n +" q= 0 s= 0 t= 1");
        while (n>0) {...
        }
    }

 

[StGo]

Danke für die Antwort.

Aber auch leider nicht ganz richtig.

Wenn dann so:

void EEA(int m, int n){
		System.out.println("m=  n= " +m +" q= 0 s= 1 t= 0");
        System.out.println("m= " +m +"n= " + n +" q= 0 s= 0 t= 1");
		while (n>0) {

Ich glaube es versteht keiner das ich in der Ausgabe einfach den ganzen Algorithmus ausgeben will. Es geht mir nicht darum das Ergebnis dem Bsp an zu passen.

Diese Zeile ist wenn man es rechnet falsch!

System.out.println("m= " +m +"n= " + n +" q= 0 s= 0 t= 1");

Da 99/78 eins ergibt ist q nicht 0!

Ich habe es so ähnlich auch schon probiert. Es hilft weiterhin auch nicht die Zeilen s und t zu korrigieren. Ich probiere ja nicht die Wikipedia Tabelle ab zu malen sondern eine vernünftige Ausgabe zu bekommen.

Danke für eure Hilfe

 

[Flown]

Also ich glaub du weißt als einziger wie das auszusehen hat. Ich glaube ich spreche für die anderen, wenn ich sage es hat keiner eine Ahnung was du wirklich willst.

Mache doch eine Ausgabe wie es jetzt ist und gleich darunter eine wie du sie haben willst. Ich glaube dann ist unserem Verständnis etwas geholfen.

 

[StGo]

Nee das liegt daran das ihr meinen Code anschaut aber nicht den Euklid kennt. Ich werfe keinem Vor das er nicht das nicht durchrechnet. Aber um den Code zu verstehen ist es sinnvoll wenn man das Problem nicht kennt.

Habe das hier mal auf Papier. Meine Idee war das ich meine Ergebnisse kontrollieren will. Das geht auch mit meinem Code. Nur leider ist die Ausgabe nicht wie man es schreibt. Das liegt daran das im ersten Schleifendurchlauf die erste Zeile verschluckt wird da mit den Zahlen aus der Eingabe die zweite Zeile berechnet wir.


Weiterhin ist es effizienter s und t sofort zu berechnen als zuerst den Euklid in einem Array zu speichern und dann wie man es schriftlich macht zurück zu rechnen.
Ich bin mir sicher das jemand der das schon einmal programmiert hat lacht mich aus und sagt: "ganz einfach ....."

 

[Flown]

Jetzt unterstell mir/uns nicht den Euklid'schen Algorithmus nicht zu kennen! Der ist mir in meinem Informatik-Studium zig-male über den Weg gelaufen.

Jetzt da du die Testausgabe geliefert hast ist, das viel einfacher dir zu helfen.

Du solltest eine Variable mitlaufen lassen, die du am Anfang setzt und erst im nächsten durchlauf ausgibst (in deinem Fall s bis zum nächsten durchlauf speichern).

 

[SlaterB]

ich sehe nun, dass in meiner Ausgabe von 9:57 deines Programms vom ersten Posting mit 99/78
in der Zeile 'm= 78 n= 21 q= 1' das q von '78 21 3' von Wikipedia abweicht,

das hast du in deinem Posting von 9:16 schon richtiger und ist sicher leicht erklärt:
das q muss erst nach Berechnung des aktuellen m/n bestimmt werden,
für uHelp braucht man vielleicht ein anderes 'q', alles im Detail anzuschauen

das hast du wie gesagt schon und ist ansonsten im Detail mit dem richtigen Berechnungsablauf zu vergleichen,
sicher könnten das andere auch machen und ein fertiges Programm schreiben, aber das ist wohl eher deine Aufgabe,
nicht grad spannend, nur Arbeit

weil ich gerade dabei war, hier noch eine Möglichkeit für die ersten Zeilen, wenn du das wirklich eleganter als fertige System.out.println findest:

  void EEA(int m1, int n1)
    {
        int m = 0;
        int n = Integer.MAX_VALUE;

        while (n > 0)
        {
            if (n == Integer.MAX_VALUE)
            {
                n = m1; // damit erste Zeile m + n ok
            }
            else if (n == m1)
            {
                m = n;
                n = n1; // damit zweite Zeile m +n ok
            }
            else
            {
                // ab dritter Zeile
                q = m / n; // noch falsches q, für die ersten beiden Zahlen überhaupt nicht berechnet
                rest = m - (q * n);

                m = n;
                n = rest;
            }
            // weiter

vielleicht geht es auch mit den normalen Berechnungen,
wobei mindest bei m = 0 am Anfang für q = m/n eine Spezialbehandlung einzubauen ist,

du beschreibst bisher wenig konkrete Probleme, alles nur einzubauen

 

[StGo]

Kennen und Kennen sind zwei verschiedene Dinge. Du wirst auch Dijkstra kennen aber kannst du den aus dem stehgreif? Wahrscheinlich genau wie ich nicht. Da es eben schon was her ist das wir uns damit beschäftigt haben. Ich will niemandem sein Wissen absprechen.

Das mit der Variable habe ich auch schon gestern überlegt. Habe nur leider keine Idee wie ich den zweiten durchlauf "abfangen" soll um die Ausgabe zu machen. Ich sehe wir kommen dem Problem näher.

Danke

 

[Flown]

package rechner;
 
public class ErweiterterEuklidischerAlogrithmus {
    
    int rest = 0;
    int q = 0;
    int uHelp = 1;
    int vHelp = 0;
    
    int s = 0;
    int t = 1;
    
    int sLast;
    int tLast;
    
    void EEA(int m, int n){
        boolean firstrun = true;
        while (n>0) {
            
            q = m/n;
            rest = m-(q*n);
            
            m = n;
            n = rest;
            
            
            rest = uHelp-(q*s);
            uHelp = s;
            s = rest;
            
            rest = vHelp-(q*t);
            vHelp = t;
            t = rest;
            
            System.out.println("m= " +m +" n= " +n +" q= " +q +" s= " +s +" t= " +firstrun ? t : sLast);
            
            sLast = s;
            tLast = t;
            firstrun = false;
            }
        
         System.out.println("Ergebnis: " +tLast);
    }
}

Ach ich mag mich nicht wegen Wissen/Können streiten, aber du willst Hilfe und die versuchen wir dir zu geben.
Vielleicht funktioniert dieser Code wie du es dir vorgestellt hast

 

[kaschik]

public class ExtendedEuclid {
	static String[] output = new String[100];
	static int counter = 0;

	static int[] gcd(int p, int q) {
		if (q == 0)
			return new int[] { p, 1, 0 };

		if (counter == 0) output[0] = p + "\t" + q + "\t" + p / q + "\t";
		output[++counter] = q + "\t" + p % q + "\t" +  ((p%q !=0)? q / (p % q) : "-") + "\t";

		int[] vals = gcd(q, p % q);

		if (p%q == 0) output[counter] += 1 + "\t" + 0;
		output[--counter] += vals[2] + "\t" + (vals[1] - (p / q) * vals[2]);

		return new int[] { vals[0], vals[2], vals[1] - (p / q) * vals[2] };
	}

	public static void main(String[] args) {
		gcd(409, 258);
		for (String line : output)
			if (line != null) System.out.println(line);

	}
}

Das Programm sieht teilweise so aus, als wäre es durch einen Obfuscator gegangen. xD
Aber zum Nachrechnen hat es mir gereicht und die Ausgabe sieht genau so aus, wie man es in der Uni normalerweise lernt.

 

[StGo]

@SlaterB
Du hast erfasst worum es mir geht! Das ist keine Abweichung sondern ich habe probiert zu erklären das die Zeilen um eins verrutscht sind bei den Werten für s und t.
Zu diesem Problem gesellt sich das die erste komplette Zeile fehlt. Was den Algorithmus nicht als falsch dastehen lässt. Mir ging es nur um die Darstellung weil ich meinen Kommiltonen den Code geben wollte ohne das die sich einarbeiten müssen und das Ergebnis mit ihrem schriftlichen Lösungsweg vergleichen können.
Inzwischen denke ich das es so nicht möglich ist da im Pseudocode nur das Endergebnis wichtig ist und mein Code nicht ohne Umweg jeden Schritt ausgeben kann.
Und ich habe nie gesagt das mir einer das programmieren soll sondern das ich nach Hilfe suche meine Ausgabe zu verbessern.

Aber trotzdem Danke

@Flown
Die Idee mit firstrun ist sehr gut. Ich habe damit etwas gespielt und denke damit kann ich das gröbste grade ziehen. Nach so einem Denkanstoß habe ich gesucht.

Danke

@kaschik
Das sieht spannend aus. Werde ich mich mal mit auseinandersetzen.

Danke

 

[StGo]

@kaschik
Das ist mal nicht schlecht was du gepostet hast. Als hätte ich es per Hand geschrieben.

Für alle die die Interesse dran haben: DepositFiles

Gruß und Danke an alle