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





  • 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


Anmelden zum Antworten