Die Mutter aller Algorithmen – Der Euklidische Algorithmus

In meinem letztem Blogbeitrag habe ich den Euklidischen Algorithmus als einen der ersten uns bekannten modernen Algorithmen beschrieben. Hier möchte ich nun näher auf diesen Algorithmus eingehen. Mein Ziel ist es den Euklidischen Algorithmus nur anhand von einfachen Beispielen zu erklären. Bevor ich jedoch näher auf den Algorithmus eingehe, möchte ich Einiges zur dessen Entstehungsgeschichte erzählen.

Historische Entwicklung

Anders als wir es aus unserem Mathematikunterricht kennen, haben die Griechen keine Formeln benutzt. Sie „rechneten“ rein geometrisch und mithilfe von Texten, in denen sie ihre mathematischen Gedankengänge niederschrieben. Kurz gesagt, die alten Griechen beschrieben Mathematik mit “gesprochenen“ Bildern. So auch der Euklidische Algorithmus.

Der euklidische Algorithmus zählt zu den älteste uns bekannten „modernen“ Algorithmen. Er wurde von Euklid im Jahre 300 v. Chr. in seinem Werk „Die Elemente“ formal beschrieben. Euklid selber war nicht der Entwickler dieses Algorithmus. Der Algorithmus wurde lange vor Euklid von Handwerkern aus der Antike benutzt. Kein Scherz! Die Handwerker im antiken Griechenland sind damals womöglich wie folgt vorgegangen:

Die antiken Handwerker

Angenommen wir wären ein antiker Handwerker und vor uns würden zwei Stäbe unterschiedlicher Längen vorliegen. Jetzt möchten wir wissen, was denn die größte gemeinsame Länge dieser beiden Stäbe ist. Warum? Mit dieser Information können wir uns ein eigenes „Maßband“ erstellen (es gab ja damals weder antike Baumärkte noch das metrische System).

Das folgende Beispiel soll anhand zweier Stäbe der Länge 52 und 18 verdeutlichen, wie unsere antiken Handwerker vorgegangen sein könnten:

Wir sehen, dass der kurze Stab (18) zwei mal in den längeren Stab (52) reinpasst. Jetzt nehmen wir den Rest (14) und sehen, dass dieser (14) in den vorherigen kürzeren Stab (18) nur einmal rein passt und ein weiteres Stück (4) übrigbleibt. Dieses kurze Stück (4) passt drei mal in den Rest (14) und am Ende bleibt uns ein Stück (2) über, welches genau zwei mal in den Letzteren (4) rein passt.

Das bedeutet, dass das letzte Stück (2) als größtes gemeinsames Maß für beide Stücke (52 und 18) verwendet werden kann. Natürlich können wir das letzte Maß (für uns die Länge zwei, weil wir einen Maßstab haben), weiter unterteilen. Dieses Stück können wir jetzt mit einem Knoten an einem Faden markieren und bekommen damit ein eigenes „Maßband“. Nennen wir dieses Stück „Handwerker Stavros antiker Zentimeter“ und können jetzt dem langen Stab die Länge „52“ und dem kürzeren die Länge „18“ zuordnen.

Jetzt sind wir als Handwerker in der Lage Seitenverhältnisse und Längen zu bestimmen (allerdings nur „geeicht“ auf Stavros antikem Zentimeter). So ähnlich könnte sich dies im antiken Griechenland abgespielt haben.

Die Wechselwegnahme

Man erkennt sofort aus dem Beispiel ein methodisches Vorgehen. Dieses Vorgehen nannten die Griechen „Wechselwegnahme“ (weil man immer etwas wegnimmt – subtrahiert). Euklid formalisierte und bewies, dass dieses Vorgehen immer richtig ist, wenn man den größten gemeinsamen Teiler (ggt) zweier natürlicher Zahlen bestimmen möchte. Jahrhunderte später wurde unabhängig von Euklid, der Euklidische Algorithmus in Indien und China entwickelt.

Die Funktionsweise des Euklidischen Algorithmus

Wie würden wir vorgehen, wenn wir nach dem größten gemeinsamen Teiler von zwei natürlichen Zahlen suchen würden? Angenommen dies wären die Zahlen 42 und 77. Wir können hier ganz Naiv vorgehen, indem wir schrittweise von der kleineren Zahl eine 1 abziehen und überprüfen, ob diese Zahl die beiden teilt. Sobald wir solch eine Zahl vorliegen haben, haben wir den größten gemeinsamen Teiler gefunden. Dies ginge wie folgt:

Wir haben unseren ggT gefunden: Es ist die 7. Aber ist dieser Algorithmus praktikabel? Offensichtlich nicht, da der Aufwand bei großen Zahlen (wie sie in der Kryptographie verwendet werden) viel zu groß ist. Wir müsste uns die ganze Zahlenkette nach unten schrittweise durchhangeln, was bei großen Zahlen so lange dauern könnte wie das Universum alt ist.

Die Frage ist, ob es effizientere Algorithmen gibt? Die Antwort ist „Ja“. Es ist der Euklidische Algorithmus (und er ist sogar der effizienteste Algorithmus). Er beruht auf dem Gedanken, dass der ggT zweier Zahlen auch die Differenz teilen muss. In unserem Bespiele wäre dies:

Wir sehen hier sofort, dass der Euklidische Algoritrhmus dem „naiven“ Algorithmus haushoch übelegen ist, da dieser nur zwei Schritte benötigte. Das folgende Nassi-Shneiderman-Diagram beschreibt den Algorithmus formal:

Der Euklidische Algorithmus lässt sich in Python wie folgt implementieren:

# Implementierung des ggT durch den Euklidischen Algorithmus
def ggT(a,b):  
   while a>0 and b>0:
      if a>b:
         a=a-b
      else
         b=b-a
   if b==0:
      return a
   else
      return b

Ich werde in meinen kommenden Blogartikeln ausschliesslich Python als Programmiersprache benutzen. Der Grund hierzu ist der, dass Python sich mittlerweile quasi als Standard für Data Scientist und Algorithmiker im Bereich Künstlicher Intelligenz entwickelt hat.

Der klassische Euklidische Algorithmus

Warum ist der Algorithmus nach so vielen Jahren immer noch aktuell? Das liegt daran, dass der Euklidische Algorithmus nicht nur in vielen mathematischen Beweisketten vorkommt, sondern auch in in sehr vielen Branchen angewendet wird. Hier wären einige Beispiele:

• Kryptographie: Speziell zu erwähnen ist das asymmetrische Verschlüsselungsverfahren. Dieses ist heutzutage nicht mehr aus dem Internet wegzudenken. So basieren z.B. fast alle Finanztransaktionen auf Basis von RSA und Elliptische Kurven (werden von mir in den kommenden Blogs näher beschrieben). Auch das Homebanking nutzt diese Verschlüsselungen. Der Euklidische Algorithmus bildet das Fundament dieser Verfahren.
• Datenkomprimierung: Die Mathematik hinter dem Komprimieren von Dateien nutzt den ggT und damit auch den Euklidischen Algorithmus. Das bedeutet, dass jeder der einmal seine Dateien „gezippt“ hat, auch den Euklidischen Algorithmus im Hintergrund benutzt. Ich werde sicherlich auch einen Blogartikel schreiben, wo ich verschieden Komprimierungsverfahren vorstellen werde.
• Audio- und Videocodecs: Codecs sind Algorithmen, welche digitale Signale kodieren (coden) bzw. dekodieren (decoden). Umgangssprachlich hat sich die Verwendung des Begriffs Codec etabliert. Die meisten Codecs sind Codecs, welche Audio- und Videosignale bearbeiten (für Streamingdienste wie Netflix & Co. nicht mehr wegzudenken). Ich werde einige Blogartikel schreiben, in welchen ich auf die gängigsten Codec-Formate (MPEG, MP4, AVI und Co.) eingehen werde. Hier hat sich ein ganzer Zoo von Algorithmen angesammelt und ich möchte unbedingt ein wenig „Licht ins Dunkle bringen“.
• Zahlentheorie: Ohne die Berechnung des ggT. wäre man nicht in der Lage mit großen Zahlen auf Mikrocontrollern zu rechnen. Diese mathematischen Objekte nennt man „Kongruenzen“. Keine Angst, klingt kompliziert ist aber so etwas wie Rechnen mit Uhrzeiten. Auch hierzu wird es einen Blogartikel geben.
• Statistik: Jegliche Anwendung in der Statistik basieren auf der Wahrscheinlichkeitstheorie, welche den ggT. nutzen und damit auch den Euklidischen Algorithmus. Speziell möchte ich hier die Pharmabranche bei der Untersuchung der Wirksamkeit von Medikamenten erwähnen. Ebenfalls spielt die Statistik eine sehr große Rolle in der Meinungs- und Versicherungsbranche.

Wie bereits am Anfang erwähnt, möchte ich den Euklidischen Algorithmus nicht beweisen. Wer dennoch interessiert ist, kann sich den Beweis unter [1] ansehen.

Zusammenfassung

Wir haben uns den Euklidischen Algorithmus angeguckt und etwas über dessen Entstehungsgeschichte gelernt. Danach haben wir gesehen, wie sich der Euklidische Algorithmus mittels Python implementieren lässt. Ebenfalls habe ich die wichtigsten Anwendungsgebiete des Algorithmmus aufgezählt. In meinem nächsten Blogbeitrag wird es um einen weiteren antiken Algorithmus gehen. Es handelt sich um den „Der Sieb des Eratosthenes“. Dies ist der erste Algorithmus zur Ermittlung von Primzahlen.

Da der Euklidische Algorithmus in so vielen Branchen eingesetzt wird, möchte ich wie folgt abschließen. Der Euklidische Algorithmus ist die Mutter aller Algorithmen!

Referenzen

[1] Jochen Ziegenbalg „Elementare Zahlentheorie“ Kapitel 3 2. Auflage Springer Spektrum