Zum Inhalt springen

Steinscher Algorithmus

aus Wikipedia, der freien Enzyklopädie

Der steinsche Algorithmus oder binäre euklidische Algorithmus dient der effizienten Berechnung des größten gemeinsamen Teilers. Der Algorithmus wurde 1967 vom Physiker Josef Stein (Hebräische Universität Jerusalem) vorgestellt.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Donald E. Knuth zufolge entwickelten R. Silver und J. Tersian den Algorithmus bereits 1962, publizierten ihn aber nicht.<ref name="KNUTH">Donald E. Knuth: The Art of Computer Programming. Band 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley Professional, 1997, ISBN 0-201-89684-2, S. 338–341.</ref>

Funktionsweise

Der Algorithmus nutzt folgende Rechenregeln:

Falls <math>b = 0</math>:

  • <math>\operatorname{ggT}(a,\ 0) = a \qquad </math> und Haltebedingung des Algorithmus

Falls <math>b = \text{ungerade}</math>:

  • <math>\operatorname{ggT}(a,\ b) = \begin{cases}
                                     \operatorname{ggT}(a,\ b-a)\ \ \quad & \text{falls } b \ge a \\
                                     \operatorname{ggT}(b,\ a-b)\ \ \quad & \text{sonst }
                                   \end{cases}</math>

Falls <math>b = \text{gerade}</math>:

  • <math>\operatorname{ggT}(a,\ b) = \begin{cases}
                                     \operatorname{ggT}(a,\ b/2)             & \text{falls } a \text{ ungerade} \\
                                     \operatorname{ggT}(a/2,\ b/2) \cdot 2   & \text{sonst }
                                   \end{cases}</math>
Funktionsweise
a) Nutzt <math>\operatorname{ggT}(a,\ 0) = a\ </math> aus und ist gleichzeitig die Haltebedingung des Algorithmus.
b) Wird abgewendet, wenn <math>b</math> ungerade ist.
b1) Ist <math>b \ge a</math>, wird <math>b</math> um <math>a</math> reduziert. <math>\operatorname{ggT}(a,\ b) = \operatorname{ggT}(a,\ b-a)</math> ausgenutzt.
b2) Ist <math>b < a</math>, wird als erster Operand der zweite Operand <math>b</math> benutzt und als zweiter Operand <math>a-b</math>.
Durch dieses geschickte Umsortieren wird das Horrorszenario des klassischen euklidischen Algorithmus vermieden, in dem ein sehr großer Operand nur sehr langsam reduziert wird.
c) wird verwendet, wenn <math>b</math> gerade ist:
c1) Wenn nur ein Operand gerade ist, kann die <math>2</math> als gemeinsamer Teiler gestrichen werden.
c2) Wenn beide Operanden gerade ist, werde beide um den Teiler <math>2</math> verringert, diese Operation wird sich aber für das Endergebnis gemerkt, da es ja ein gemeinsamer Teiler ist.

Wir benutzen dafür das Horrorszenario für den klassischen euklidischen Algorithmus, zwei große fast gleiche Zahlen <math>209865</math> und <math>209797</math>:

<math>\begin{array}{rl|l}

\operatorname{ggT}(209865,\ 209797) & = \operatorname{ggT}(209797,\ 68) & \scriptstyle{\text{b2}} \\ \operatorname{ggT}(209797,\ 68) & = \operatorname{ggT}(209797,\ 34) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(209797,\ 34) & = \operatorname{ggT}(209797,\ 17) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(209797,\ 17) & = \operatorname{ggT}(17,\ 209780) & \scriptstyle{\text{b2, hier bekommt der klassische euklidische Algorithmus ein Problem, hier wird allerdings eine ungerade Zahl durch Division durch 2 erzeugt und diese nach vorn gebracht}} \\ \operatorname{ggT}(17,\ 209780) & = \operatorname{ggT}(17,\ 104890) & \scriptstyle{\text{c1, hier wird entweder halbiert oder diese ungerade Zahl subtrahiert und damit eine gerade Zahl erzeugt}} \\ \operatorname{ggT}(17,\ 104890) & = \operatorname{ggT}(17,\ 52445) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 52445) & = \operatorname{ggT}(17,\ 52428) & \scriptstyle{\text{b1}} \\ \operatorname{ggT}(17,\ 52428) & = \operatorname{ggT}(17,\ 26214) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 26214) & = \operatorname{ggT}(17,\ 13107) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 13107) & = \operatorname{ggT}(17,\ 13090) & \scriptstyle{\text{b1}} \\ \operatorname{ggT}(17,\ 13090) & = \operatorname{ggT}(17,\ 6545) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 6545) & = \operatorname{ggT}(17,\ 6528) & \scriptstyle{\text{b1}} \\ \operatorname{ggT}(17,\ 6528) & = \operatorname{ggT}(17,\ 3264) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 3264) & = \operatorname{ggT}(17,\ 1632) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 1632) & = \operatorname{ggT}(17,\ 816) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 816) & = \operatorname{ggT}(17,\ 408) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 408) & = \operatorname{ggT}(17,\ 204) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 204) & = \operatorname{ggT}(17,\ 102) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 102) & = \operatorname{ggT}(17,\ 51) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 51) & = \operatorname{ggT}(17,\ 34) & \scriptstyle{\text{b1}} \\ \operatorname{ggT}(17,\ 34) & = \operatorname{ggT}(17,\ 17) & \scriptstyle{\text{c1}} \\ \operatorname{ggT}(17,\ 17) & = \operatorname{ggT}(17,\ 0) & \scriptstyle{\text{b1}} \\ \operatorname{ggT}(17,\ 0) & = 17 & \scriptstyle{\text{a}} \\ \end{array} </math>

Zu beachten ist, dass der steinsche Algorithmus nur dann richtig funktioniert, wenn vorzeichenlose Integer verwendet werden. Negative Zahlen müssen zuerst in positive überführt werden. Der euklidische Algorithmus hingegen funktioniert auch mit vorzeichenbehafteten Integertypen, wenn ein Operand nicht die kleinste darstellbare Zahl ist.

Prinzip

Zu bestimmen sei der größte gemeinsame Teiler der beiden positiven Zahlen <math>a</math> und <math>b</math>. Dazu wird als erstes eine Variable <math>k</math> definiert und dieser wird der Wert 0 zugewiesen. Dann werden sowohl <math>a</math> als auch <math>b</math> solange durch 2 geteilt, bis <math>a</math> und <math>b</math> nicht mehr durch 2 teilbar sind. Bei jeder Halbierung wird <math>k</math> um 1 erhöht.

Der zweite Teil benötigt eine zusätzliche Variable <math>t</math>, der die Differenz von <math>a</math> und <math>b</math> zugewiesen wird. Jeder gemeinsame Teiler von <math>a</math> und <math>b</math> ist auch Teiler von <math>t</math>, sodass gilt: <math>\operatorname{ggT}(a, b) = \operatorname{ggT}(a, t) = \operatorname{ggT}(b, t)</math>. Die Variable <math>t</math> wird anschließend noch, solange es sich um eine gerade Zahl handelt, durch 2 geteilt. Dann wird <math>a</math> durch <math>t</math> ersetzt und mit dem neuen <math>a</math> ein neues <math>t</math> berechnet. Der Algorithmus ist beendet, sobald <math>t = 0</math> gilt. Das Ergebnis ist dann <math>\operatorname{ggT}(a, b) = a \cdot 2^k</math>.<ref>{{#if:2018-03-28|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Alexander Weers|Alexander Weers: }}{{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C{{#if:Größter gemeinsamer Teiler|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1=https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Größter gemeinsamer Teiler}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Größter gemeinsamer Teiler}}}}|[{{#invoke:URLutil|getNormalized|1=https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Größter gemeinsamer Teiler}}}}]}}{{#if:| ({{{format}}}{{#if:Formelsammlung24.dehttps://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/{{#if: 2018-03-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}}%7C%7C}}}}{{#if:Größter gemeinsamer Teiler|{{#if:{{#invoke:WLink|isValidLinktext|1=Größter gemeinsamer Teiler|lines=0}}||}}}}{{#if: Formelsammlung24.de| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Formelsammlung24.de}}}}{{#if: | {{{hrsg}}}{{#if: https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C,%7C{{#if: 2018-03-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C,%7C{{#if: 2018-03-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C,%7C{{#if: 2018-03-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/{{#invoke:TemplUtl%7Cfaculty%7C}}%7C+{{#if:%7C{{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7Carchiviert%7Cehemals}}%7C{{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7CArchiviert%7CEhemals}}}}+{{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7Cvom%7Cim}}+Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: 2018-03-28| am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|2018-03-28{{#if:135743||(?)}}}}}}{{#if: 2018-03-27|;}}}}{{#if: 2018-03-27| {{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/{{#invoke:TemplUtl%7Cfaculty%7C}}%7Cabgerufen%7CAbgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2018-03-27 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2018-03-27|class=Zitationswartung}} }} {{#invoke:DateTime|format|2018-03-27|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:Formelsammlung24.dehttps://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/{{#if: 2018-03-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/{{#if: 2018-03-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7C%7C{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/
      | {{#if:{{#invoke:URLutil|isWebURL|https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/
       | {{#if:{{#invoke:URLutil|isWebURL|https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/ }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/
      | {{#if:{{#invoke:URLutil|isWebURL|https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/
       | {{#if:{{#invoke:URLutil|isWebURL|https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/ }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:https://web.archive.org/web/20180328041145/https://www.formelsammlung24.de/sites/Primfaktorzerlegung/ggT/%7CVorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

Algorithmus

Die hier in Pseudocode beschriebene Variante des Algorithmus entspricht im Wesentlichen derjenigen, die Donald E. Knuth in seinem Werk The Art of Computer Programming beschreibt. 

STEIN(a,b)
  wenn a = 0
      dann return b
  k <math>\leftarrow</math> 0
  solange a und b gerade Zahlen sind
      a <math>\leftarrow</math> a/2
      b <math>\leftarrow</math> b/2
      k <math>\leftarrow</math> k + 1
  wenn a eine ungerade Zahl ist
      dann t <math>\leftarrow</math> -b
      sonst t <math>\leftarrow</math> a
  solange t ≠ 0
      solange t eine gerade Zahl ist
          t <math>\leftarrow</math> t/2
      wenn t > 0
          dann a <math>\leftarrow</math> t
          sonst b <math>\leftarrow</math> -t
      t <math>\leftarrow</math> a - b
  return a <math> \cdot </math> 2k

Viele Prozessoren haben heutzutage Befehlssätze, die sehr schnell (oft in einem Takt) bestimmen können, wie oft eine Ganzzahl durch Zwei teilbar ist. Zum Beispiel stellt die x86-Architektur seit dem 80386 für diesen Zweck die Instruktion bsf zur Verfügung. Unter Verwendung einer solchen Instruktion ist es möglich, zwei der drei Schleifen des Algorithmus einzusparen und damit seine Laufzeit signifikant zu verbessern. Die folgende Implementierung in der Programmiersprache C nutzt zu diesem Zwecke die POSIX-Standardfunktion ffs (find first set):

<syntaxhighlight lang="c">

  1. include <stdlib.h> /* für abs() */
  2. include <strings.h> /* für ffs() */

int ggt(int a, int b) { 

   int c;

   if (a == 0 || b == 0) // falls eines oder beide Argumente 0 sind,
       return a | b; // ist das andere Argument oder 0 das Ergebnis

   // dies kann weggelassen werden, wenn a und b nicht negativ sein können
   a = abs(a);
   b = abs(b);

   c = ffs(a | b) - 1;
   a >>= ffs(a) - 1;

   do {
       b >>= ffs(b) - 1;
       if (a > b) {
           // vertausche Variablen, damit bei Subtraktion kein Überlauf stattfinden kann
           int temp = b;
           b = a;
           a = temp;
       }

       b -= a;
   } while (b != 0);

   return a << c;

} </syntaxhighlight>

Eine Implementierung für vorzeichenlose Ganzzahlen in x86-Assembler, die bsf nutzt:

<syntaxhighlight lang="nasm"> ggt: 

       mov     ecx, 4[esp]     ; Lade a
       mov     eax, 8[esp]     ; Lade b
       test    ecx, ecx        ; Vergleiche a mit 0:
       jz      done            ;  falls a gleich 0 ist das Ergebnis b

       cmp     eax, ecx        ; Vergleiche a mit b:
       je      done            ;  falls a gleich b ist das Ergebnis b

       mov     edx, eax        ; Lade b
       mov     eax, ecx        ; Lade a
       test    edx, edx        ; Vergleiche b mit 0:
       jz      done            ;  falls b gleich 0 ist das Ergebnis a

       push    ebx
       bsf     ecx, edx        ; Bestimme größte Zweierpotenz von b
       bsf     ebx, eax        ; Bestimme größte Zweierpotenz von a
       cmp     ebx, ecx        ; Vergleiche beide
       cmova   ebx, ecx        ;  und merke deren Minimum
       shr     edx, cl         ; Dividiere b durch größte Zweierpotenz

next: 

       bsf     ecx, eax        ; Bestimme größte Zweierpotenz von a
       shr     eax, cl         ; Dividiere a durch größte Zweierpotenz
       mov     ecx, edx
       cmp     edx, eax        ; Vergleiche b mit a
       cmovb   edx, eax        ;  und vertausche beide, falls b kleiner a
       cmovb   eax, ecx
       sub     edx, eax        ; Subtrahiere a von b
       jnz     next            ;  und wiederhole, bis b gleich 0

       mov     ecx, ebx
       shl     eax, cl         ; Multipliziere a mit 2**Minimum
       pop     ebx

done: 

       ret

</syntaxhighlight>

Quellen

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Steinscher_Algorithmus&oldid=135743“