Stein'scher Algorithmus
-
Hallo,
bei Wikipedia habe ich einen Eintrag zum Stein'schen Algorithmus zur effizienten Berechnung des ggT gefunden, mit einer in Pseudocode beschriebenen Implementierung, die ich in C++ umgesetzt habe.
Leider funktiniert sie keineswegs richtig oder ich habe einen Fehler gemacht, den ich nicht finden kann(keineswegs unwahrscheinlich).Wikipedia's Pseudocode (http://de.wikipedia.org/wiki/Steinscher_Algorithmus)
STEIN(a,b) 1 k <- 0 2 solange a und b gerade Zahlen sind 3 a <- a/2 4 b <- b/2 5 k <- k + 1 6 wenn a eine ungerade Zahl ist 7 dann t <- -b 8 sonst t <- a 9 solange t != 0 10 solange t eine gerade Zahl ist 11 t <- t/2 12 wenn t > 0 13 dann a <- t 14 sonst b <- -t 15 t <- a - b 16 return a * 2^k
Meine C++ "Übersetzung":
int ggT(int numerator, int denominator){ // based on Stein's algorithm int a = numerator; int b = denominator; int c = 0; int tmp; while ((a%2 == 0) && (b%2==0)){ a /= 2; b /= 2; c++; } if((a%2) != 0) tmp = -b; else tmp = a; while (tmp != 0){ while( tmp%2 == 0){ tmp /= 2; } if(tmp > 0) a = tmp; else b = -tmp; tmp = a - b; } return (a * functions::n_pow(2, c)); }; //dazu noch die n_pow(int, int) funktion, die sollte aber funktionieren... int n_pow(int x, int ex){ int i = 1; while(i<=ex) { x*=x; i++; } return x; };
Also diese ggT() Funktion meint, der ggT(2, 27) = 2 ... das ist dann wohl falsch...
Ich sehe den Fehler aber überhaupt nicht bzw. kann es sein, dass Wiki hier schwachsinn verzappft (klar kann es sein, aber ist es so)?
-
also meiner sieht so aus, den ich schonmal implementiert habe und er liefert immer ein richtiges ergebnis
int ggT(int a,int b) { while(b != 0) { int temp = a%b; a = b; b = temp; } return a; }
-
Hallo,
dieser Stein'sche Algorithmus hat mich interessiert,
daher habe ich ihn bei wiki gesucht und bin auf
folgender englischer Seite gelandet:http://en.wikipedia.org/wiki/Binary_GCD_algorithm
dort ist eine Beispiel Implementierung in c
aufgefuehrt. Vielleicht hilft dir das weiter.
Poste doch hier mal den link auf die wiki Seite
die dir als Vorlage diente.Gruss Ulli
-
http://de.wikipedia.org/wiki/Größter_gemeinsamer_Teiler#Euklidischer_und_steinscher_Algorithmus
Das sollte doch schon reichen oder nicht?
-
Folgendes ist falsch:
int n_pow(int x, int ex){ int i = 1; while(i<=ex) { x*=x; i++; } return x; };
2^4 ist dort:
x = 2
x = 2 * 2 = 4
x = 4 * 4 = 16
x = 16 * 16 = 256
also nicht ganz korrekt.Besser:
int n_pow(int x, int ex){ int i = 1; int r = x; while(i<=ex) { r*=x; i++; } return r; };
-
Also die n_pow funktion habe ich umgeschrieben, der Fehler scheint aber noch vorhanden zu sein (z.B. ggT(5, 10) = 10 meint er...).
Den euklidischen Algorithmus wollte ich nicht, ich wollte ein bisschen schneller sein(wobei das vermutlich kein mensch merkt). Ich wüsste nur gerne, ob das in Wiki vielleicht inkorrekt ist.
-
Was sollen die ">>=" Operatoren in dem englischen Wiki Artikel bedeuten ? Bitweise verschiebung ?
-
Hallo,
Floyd schrieb:
Was sollen die ">>=" Operatoren in dem englischen Wiki Artikel bedeuten ? Bitweise verschiebung ?
Was sonst? Ist einer der C/C++-Operatoren (bitweises Verschieben nach rechts und Zuweisung)
MfG,
Probe-Nutzer
-
Floyd schrieb:
Was sollen die ">>=" Operatoren in dem englischen Wiki Artikel bedeuten ? Bitweise verschiebung ?
Jup.
a >>= b ist (fast) equivalent zu a = a >> b , also bitweise Verschiebung. (wenn a ein Ausdruck ist, wird er beim >>= nur einmal ausgewertet, beim anderen zweimal)
-
Ok, diese englische, völlig C++-konforme C-Lösung, scheint nach allen bisherigen Tests tatsächlich zu funktionieren. Dank an Alle!
Hier nochmal die URL zu der richtigen Lösung: http://en.wikipedia.org/wiki/Binary_GCD_algorithm