Linux @ Home

ggT / gcd, wer kann’s am Kürzesten? Diese Frage, tauchte auf, nachdem ich versuchte, den grössten gemeinsamen Teiler aus Lust und Laune in ein paar Programmiersprachen zu implementieren (und einige male kläglich scheiterte). Von der Auswahl ausgenommen sind esoterische oder „unleserliche“ Sprachen (APL) und natürlich solche, die eine gcd-Funktion bereits in den Bibliotheken haben. Unter diesen Gesichtspunkten gewinnt hier relativ klar Forth! Irgendwie überraschend (aber beim zweiten Nachdenken doch nicht mehr so überraschend), dass eine Programmiersprache aus den Sechzigerjahren des vorigen Jahrhunderts so unglaublich effizient im Ausdruck ist:

: gcd ( a b -- n )
  begin dup while tuck mod repeat drop ;

Zugegeben, ohne genau zu wissen, was tuck macht, ist es etwas schwierig zu verstehen, aber das Prinzip der wiederholenden Modulo ist schon klar zu erkennen.
Aufrufe dieser Funktion macht man dann in etwa so:

142864 24 gcd . 8

oder pro Linie ein Argument (da merkt man deutlich, dass Forth nur auf einem Stack arbeitet):

14361672
649981417530
gcd
. 1446

Wer dies unbedingt austesten will, sollte sich gforth (GNU) installieren. Für Fans der UPN: In Forth rechnet man aufgrund des Stacks natürlich mit der umgekehrten polnischen Notation:

5 3 + 7 2 + * .

(mit dem Punkt holt man sich das letzte Resultat vom Stack, quasi ein pop). Natürlich gibt es auch andere Kandidaten, die zumindest ähnlich kurz sind, aber meines Erachtens ist Forth noch die bekannteste (ich habe jedenfalls noch nie was von K oder Joy gehört). Interessanterweise bietet auch gnuplot eine Lösung dafür an. Ich weiss nicht, ob man Gnuplot zu den Turing-vollständigen Sprachen zählt, deshalb ausser Konkurrenz:

gcd (a, b) = b == 0 ? a : gcd (b, a % b)

Ach ja, der Preis für die längste Implementierung von gcd geht an SED (ein Streaming-Editor von Unix, der eigentlich nie als Programmiersprache gedacht war), den Sourcecode kann man sich bei rosettacode.org angucken