Größter gemeinsamer Teiler

40

Ihre Aufgabe ist es, den größten gemeinsamen Divisor (GCD) von zwei gegebenen ganzen Zahlen in so wenigen Byte Code wie möglich zu berechnen .

Sie können ein Programm oder eine Funktion schreiben, indem Sie Eingaben vornehmen und Ausgaben mit einer unserer anerkannten Standardmethoden zurückgeben (einschließlich STDIN / STDOUT, Funktionsparameter / Rückgabewerte, Befehlszeilenargumente usw.).

Die Eingabe erfolgt über zwei nicht negative Ganzzahlen. Sie sollten in der Lage sein, entweder den gesamten Bereich zu verarbeiten, der vom Integer-Standardtyp Ihrer Sprache unterstützt wird, oder den Bereich [0,255], der größer ist. Es ist garantiert, dass mindestens einer der Eingänge ungleich Null ist.

Sie dürfen keine integrierten Funktionen verwenden, die entweder die GCD oder die LCM (Least Common Multiple) berechnen.

Es gelten die Standardregeln für .

Testfälle

0 2     => 2
6 0     => 6
30 42   => 6
15 14   => 1
7 7     => 7
69 25   => 1
21 12   => 3
169 123 => 1
20 142  => 2
101 202 => 101
Mike Shlanta
quelle
1
Wenn wir zulassen, dass asm Eingaben in Registern vornimmt, die praktisch sind, und das Ergebnis in Registern, die praktisch sind, sollten wir definitiv Funktionen oder sogar Codefragmente zulassen (dh nur einen Funktionskörper). Wenn ich meine Antwort zu einer vollständigen Funktion mache, würde dies etwa 4B mit einer Registeraufrufkonvention wie dem 32-Bit-Vektoraufruf von MS (ein xchg eax, ein mov und ein ret) oder mehr mit einer Stapelaufrufkonvention hinzufügen.
Peter Cordes
@ PeterCordes Sorry, ich hätte genauer sein sollen. Sie können ganz einfach den notwendigen Code für bear schreiben, aber wenn Sie so freundlich wären, einen Weg einzuschließen, um den Code auszuführen, wäre es nett.
Mike Shlanta
Zählen Sie also nur den gcd-Code, aber geben Sie den umgebenden Code an, damit die Benutzer überprüfen / experimentieren / verbessern können. Übrigens, Ihre Testfälle mit Null als einer der beiden Eingaben lösen unsere x86-Maschinencode-Antworten auf. dividiert durch Null löst eine Hardware-Ausnahme aus. Unter Linux erhält Ihr Prozess eine SIGFPE.
Peter Cordes
3
@CodesInChaos Speicher- und Zeitbeschränkungen werden normalerweise ignoriert, solange der Algorithmus selbst im Prinzip alle Eingaben verarbeiten kann. Die Regel soll nur verhindern, dass Benutzer willkürliche Grenzwerte für Schleifen fest programmieren, die den Algorithmus künstlich auf einen kleineren Bereich von Eingaben beschränken. Ich verstehe nicht ganz, wie Unveränderlichkeit dazu kommt?
Martin Ender
1
gcd (0, n) ist Fehler nicht n
RosLuP

Antworten:

37

Retina , 16

^(.+)\1* \1+$
$1

Hierbei wird der Algorithmus von Euclid überhaupt nicht verwendet. Stattdessen wird die GCD mithilfe von Regex-Übereinstimmungsgruppen gefunden.

Probieren Sie es online aus. - In diesem Beispiel wird GCD (8,12) berechnet.

Eingabe als 2 durch Leerzeichen getrennte Ganzzahlen. Beachten Sie, dass die E / A unär ist. Wenn das nicht akzeptabel ist, können wir dies tun:

Netzhaut, 30

\d+
$*
^(.+)\1* \1+$
$1
1+
$.&

Probieren Sie es online aus.

Wie @ MartinBüttner feststellt, fällt dies bei großen Zahlen auseinander (wie dies im Allgemeinen für alles Unäre der Fall ist). Mindestens eine Eingabe von INT_MAX erfordert die Zuweisung einer Zeichenfolge von 2 GB.

Digitales Trauma
quelle
2
Ich würde gerne mehr dafür stimmen
MickyT
Sollte mit dem Nummernkreis jetzt in Ordnung sein. Ich habe die Spezifikation geändert (mit der Erlaubnis des OPs), um nur den natürlichen Zahlenbereich der Sprache zu fordern (oder [0,255], wenn das mehr ist). Sie müssen jedoch Nullen unterstützen, obwohl ich denke, dass das Ändern Ihres +s zu *s tun sollte. Und Sie können die letzte Stufe des langen Codes erheblich verkürzen, indem Sie ihn auf reduzieren 1.
Martin Ender
2
Zum späteren Nachschlagen habe ich gerade eine alternative 16-Byte-Lösung gefunden, die für eine beliebige Anzahl von Eingaben (einschließlich einer) funktioniert, sodass sie in anderen Kontexten möglicherweise nützlicher ist: retina.tryitonline.net/…
Martin Ender,
1
Ich habe nur bemerkt, dass weder Ihre Lösungen noch die in meinem Kommentar oben genannten die benötigen ^, da es unmöglich ist, dass das Match von der Startposition aus fehlschlägt.
Martin Ender
28

Maschinencode i386 (x86-32), 8 Byte (9 Byte für vorzeichenlose Zeichen)

+ 1B, wenn wir mit b = 0Eingaben umgehen müssen .

Computercode amd64 (x86-64), 9 Byte (10B für vorzeichenlose oder 14B 13B für vorzeichenlose 64B-Ganzzahlen)

10 9B für unsigned auf amd64, das mit beiden Eingängen = 0 abbricht


Die Eingänge sind 32 - Bit - Nicht-Null unterzeichnete ganze Zahlen in eaxund ecx. Ausgabe in eax.

## 32bit code, signed integers:  eax, ecx
08048420 <gcd0>:
 8048420:       99                      cdq               ; shorter than xor edx,edx
 8048421:       f7 f9                   idiv   ecx
 8048423:       92                      xchg   edx,eax    ; there's a one-byte encoding for xchg eax,r32.  So this is shorter but slower than a mov
 8048424:       91                      xchg   ecx,eax    ; eax = divisor(from ecx), ecx = remainder(from edx), edx = quotient(from eax) which we discard
    ; loop entry point if we need to handle ecx = 0
 8048425:       41                      inc    ecx        ; saves 1B vs. test/jnz in 32bit mode
 8048426:       e2 f8                   loop   8048420 <gcd0>
08048428 <gcd0_end>:
 ; 8B total
 ; result in eax: gcd(a,0) = a

Diese Schleifenstruktur besteht den Testfall wo nicht ecx = 0. ( divVerursacht eine #DEHardwareausführung beim Teilen durch Null. (Unter Linux liefert der Kernel eine SIGFPE(Gleitkomma-Ausnahme).) Wenn der Loop-Einstiegspunkt direkt vor dem liegt inc, vermeiden wir das Problem. Die x86-64-Version kann damit umgehen kostenlos, siehe unten.

Die Antwort von Mike Shlanta war der Ausgangspunkt dafür . Meine Schleife macht dasselbe wie seine, aber für vorzeichenbehaftete ganze Zahlen, weil cdqein Byte kürzer ist als xor edx,edx. Und ja, es funktioniert korrekt mit einem oder beiden negativen Eingängen. Mikes Version wird schneller laufen und weniger Platz im UOP-Cache beanspruchen ( xchg3 UOPs auf Intel-CPUs und loopauf den meisten CPUs sehr langsam ), aber diese Version gewinnt bei der Größe des Maschinencodes.

Ich habe zunächst nicht bemerkt, dass die Frage 32bit ohne Vorzeichen erfordert . Ein Zurück zu xor edx,edxanstatt cdqwürde ein Byte kosten. divhat die gleiche Größe wie idivund alles andere kann gleich bleiben ( xchgfür die Datenübertragung und inc/loopfunktioniert immer noch).

Interessanterweise haben für 64-Bit-Operanden ( raxund rcx) vorzeichenbehaftete und vorzeichenlose Versionen dieselbe Größe. Die signierte Version benötigt ein REX-Präfix für cqo(2B), die nicht signierte Version kann jedoch weiterhin 2B verwenden xor edx,edx.

Im 64-Bit-Code inc ecxist 2B: Die Einzelbyte- inc r32und dec r32Opcodes wurden als REX-Präfixe neu verwendet. inc/loopspeichert keine Codegröße im 64-Bit-Modus, also könnten Sie es auch test/jnz. Bei 64-Bit-Ganzzahlen wird ein weiteres Byte pro Befehl in REX-Präfixen hinzugefügt, mit Ausnahme von loopoder jnz. Es ist möglich, dass der Rest alle Nullen in den niedrigen 32b hat (zB gcd((2^32), (2^32 + 1))), also müssen wir den gesamten RCX testen und können kein Byte mit speichern test ecx,ecx. Das langsamere jrcxzINSN ist jedoch nur 2B, und wir können es oben in die Schleifeecx=0 einfügen, um es bei der Eingabe zu behandeln :

## 64bit code, unsigned 64 integers:  rax, rcx
0000000000400630 <gcd_u64>:
  400630:       e3 0b                   jrcxz  40063d <gcd_u64_end>   ; handles rcx=0 on input, and smaller than test rcx,rcx/jnz
  400632:       31 d2                   xor    edx,edx                ; same length as cqo
  400634:       48 f7 f1                div    rcx                      ; REX prefixes needed on three insns
  400637:       48 92                   xchg   rdx,rax
  400639:       48 91                   xchg   rcx,rax
  40063b:       eb f3                   jmp    400630 <gcd_u64>
000000000040063d <gcd_u64_end>:
## 0xD = 13 bytes of code
## result in rax: gcd(a,0) = a

Vollständig lauffähiges Testprogramm, einschließlich eines Programms main, mit dem printf("...", gcd(atoi(argv[1]), atoi(argv[2])) ); Quell- und Asm-Ausgabe im Godbolt Compiler Explorer für die Versionen 32 und 64b ausgeführt werden. Getestet und lauffähig für 32bit ( -m32), 64bit ( -m64) und x32 ABI ( -mx32) .

Ebenfalls enthalten: eine Version, bei der nur die wiederholte Subtraktion verwendet wird. Dies ist 9B für den Modus ohne Vorzeichen, auch für den x86-64-Modus, und kann einen seiner Eingänge in einem beliebigen Register annehmen. Es kann jedoch keine der Eingaben verarbeiten, die bei der Eingabe 0 sind (es erkennt, wenn subeine Null erzeugt wird, was x - 0 niemals tut).

GNU C Inline Asm Source für die 32bit Version (kompilieren mit gcc -m32 -masm=intel)

int gcd(int a, int b) {
    asm (// ".intel_syntax noprefix\n"
        // "jmp  .Lentry%=\n" // Uncomment to handle div-by-zero, by entering the loop in the middle.  Better: `jecxz / jmp` loop structure like the 64b version
        ".p2align 4\n"                  // align to make size-counting easier
         "gcd0:   cdq\n\t"              // sign extend eax into edx:eax.  One byte shorter than xor edx,edx
         "        idiv    ecx\n"
         "        xchg    eax, edx\n"   // there's a one-byte encoding for xchg eax,r32.  So this is shorter but slower than a mov
         "        xchg    eax, ecx\n"   // eax = divisor(ecx), ecx = remainder(edx), edx = garbage that we will clear later
         ".Lentry%=:\n"
         "        inc     ecx\n"        // saves 1B vs. test/jnz in 32bit mode, none in 64b mode
         "        loop    gcd0\n"
        "gcd0_end:\n"
         : /* outputs */  "+a" (a), "+c"(b)
         : /* inputs */   // given as read-write outputs
         : /* clobbers */ "edx"
        );
    return a;
}

Normalerweise würde ich eine ganze Funktion in asm schreiben, aber GNU C inline asm scheint der beste Weg zu sein, um ein Snippet einzubeziehen, das Ein- / Ausgänge in den von uns gewählten Regs haben kann. Wie Sie sehen, macht die GNU C-Inline-asm-Syntax asm hässlich und laut. Es ist auch ein sehr schwieriger Weg , asm zu lernen .

Es würde tatsächlich kompilieren und im .att_syntax noprefixModus arbeiten, da alle verwendeten Insns entweder Single / No Operand oder sind xchg. Keine wirklich nützliche Beobachtung.

Peter Cordes
quelle
2
@ MikeShlanta: Danke. Wenn Sie asm optimieren möchten, schauen Sie sich einige meiner Antworten zum Stackoverflow an. :)
Peter Cordes
2
@MikeShlanta: Ich habe doch jrcxzin der uint64_t-Version eine Verwendung gefunden :). Ich habe auch nicht bemerkt, dass Sie unsigniert angegeben haben, also habe ich auch die Anzahl der Bytes eingeschlossen.
Peter Cordes
Warum konnten Sie jecxzin der 32-Bit-Version nicht den gleichen Effekt erzielen?
Cody Grey
1
@CodyGray: inc/loopIn der 32-Bit-Version sind es 3 Byte, in der 64-Bit-Version 4 Byte. Das bedeutet , dass in der 64-Bit - Version, ist es nicht zusätzliches Bytes kostet zu verwenden jrcxzund jmpstatt inc / loop.
Peter Cordes
Kannst du nicht als Eintrag auf die Mitte zeigen?
14.
14

Hexagony , 17 Bytes

?'?>}!@<\=%)>{\.(

Entfaltet:

  ? ' ?
 > } ! @
< \ = % )
 > { \ .
  ( . .

Probieren Sie es online!

Es war ein Kinderspiel, es in Seitenlänge 3 einzubauen. Das Abschalten dieser zwei Bytes am Ende war nicht ... Ich bin auch nicht überzeugt, dass es optimal ist, aber ich bin mir sicher, dass es nahe ist.

Erläuterung

Eine weitere Implementierung des euklidischen Algorithmus.

Das Programm verwendet drei Speicherflanken, die ich als A , B und C bezeichne , wobei der Speicherzeiger (MP) wie folgt beginnt:

Bildbeschreibung hier eingeben

Hier ist das Kontrollflussdiagramm:

Bildbeschreibung hier eingeben

Der Kontrollfluss beginnt auf dem grauen Pfad mit einem kurzen linearen Bit für die Eingabe:

?    Read first integer into memory edge A.
'    Move MP backwards onto edge B.
?    Read second integer into B.

Beachten Sie, dass der Code jetzt an den Kanten <in der linken Ecke umbrochen wird. Dies <wirkt als Zweig. Wenn die aktuelle Flanke Null ist (dh der euklidische Algorithmus endet), wird die IP nach links abgelenkt und nimmt den roten Pfad. Andernfalls wird auf dem grünen Pfad eine Iteration des euklidischen Algorithmus berechnet.

Wir betrachten zuerst den grünen Weg. Beachten Sie, dass >und \alle als Spiegel fungieren, die den Befehlszeiger einfach ablenken. Beachten Sie auch, dass der Kontrollfluss dreimal um die Kanten verläuft, einmal von unten nach oben, einmal von der rechten Ecke zur unteren Reihe und schließlich von der rechten unteren Ecke zur linken Ecke, um den Zustand erneut zu überprüfen. Beachten Sie auch, dass .No-Ops sind.

Damit bleibt der folgende lineare Code für eine einzelne Iteration übrig:

{    Move MP forward onto edge C.
'}   Move to A and back to C. Taken together this is a no-op.
=    Reverse the direction of the MP so that it now points at A and B. 
%    Compute A % B and store it in C.
)(   Increment, decrement. Taken together this is a no-op, but it's
     necessary to ensure that IP wraps to the bottom row instead of
     the top row.

Jetzt sind wir wieder da, wo wir angefangen haben, mit der Ausnahme, dass die drei Kanten ihre Rollen zyklisch geändert haben (das ursprüngliche C übernimmt jetzt die Rolle von B und das ursprüngliche B die Rolle von A ...). Tatsächlich haben wir die Eingaben Aund Bmit Bbzw. verschoben A % B.

Sobald A % B(an Kante C ) Null ist, kann die GCD an Kante B gefunden werden . Wieder >lenkt der Just die IP ab, also auf dem roten Pfad, den wir ausführen:

}    Move MP to edge B.
!    Print its value as an integer.
@    Terminate the program.
Martin Ender
quelle
9

32-Bit-Little-Endian-x86-Maschinencode, 14 Byte

Generiert mit nasm -f bin

d231 f3f7 d889 d389 db85 f475

    gcd0:   xor     edx,edx
            div     ebx
            mov     eax,ebx
            mov     ebx,edx
            test    ebx,ebx
            jnz     gcd0
Mike Shlanta
quelle
4
Ich habe dies auf 8 Bytes mit cdqund signiert idivund ein Byte xchg eax, r32statt mov. Für 32-Bit-Code: inc/loopstatt test/jnz(ich konnte keinen Weg finden, ihn zu verwenden jecxz, und es gibt keinen jecxnz). Ich habe meine endgültige Version als neue Antwort veröffentlicht, da ich denke, dass die Änderungen groß genug sind, um dies zu rechtfertigen.
Peter Cordes
9

T-SQL, 153 169 Bytes

Jemand hat die schlechteste Sprache zum Golfen erwähnt?

CREATE FUNCTION G(@ INT,@B INT)RETURNS TABLE RETURN WITH R AS(SELECT 1D,0R UNION ALL SELECT D+1,@%(D+1)+@B%(D+1)FROM R WHERE D<@ and D<@b)SELECT MAX(D)D FROM R WHERE 0=R

Erstellt eine Tabellenwertfunktion , die eine rekursive Abfrage verwendet, um die gemeinsamen Teiler zu ermitteln. Dann gibt es das Maximum zurück . Nun nutzt den euklidischen Algorithmus die GCD zu bestimmen , aus meiner Antwort abgeleitet hier .

Anwendungsbeispiel

SELECT * 
FROM (VALUES
        (15,45),
        (45,15),
        (99,7),
        (4,38)
    ) TestSet(A, B)
    CROSS APPLY (SELECT * FROM G(A,B))GCD

A           B           D
----------- ----------- -----------
15          45          15
45          15          15
99          7           1
4           38          2

(4 row(s) affected)
MickyT
quelle
1
Jesus, das ist wortreich.
Cyoce
9

Gelee, 7 Bytes

ṛß%ðḷṛ?

Rekursive Implementierung des euklidischen Algorithmus. Probieren Sie es online!

Wenn die Verwendung von integrierten Funktionen nicht verboten wäre g(1 Byte, integrierte GCD), würde dies zu einer besseren Bewertung führen.

Wie es funktioniert

ṛß%ðḷṛ?  Main link. Arguments: a, b

   ð     Convert the chain to the left into a link; start a new, dyadic chain.
 ß       Recursively call the main link...
ṛ %        with b and a % b as arguments.
     ṛ?  If the right argument (b) is non-zero, execute the link.
    ḷ    Else, yield the left argument (a).
Dennis
quelle
Das fühlt sich fast wie Betrug an, haha, ich muss vielleicht spezifizieren, dass Antworten keine Butlins verwenden können ...
Mike Shlanta
13
Wenn Sie sich dazu entschließen, sollten Sie es schnell tun. Derzeit würden drei der Antworten ungültig.
Dennis
Beachten Sie, dass die angegebene Länge in Byte angegeben ist. Diese Zeichen sind in UTF8 meistens größer als 1 Byte.
Cortices
8
@cortices Ja, alle Code-Golfwettbewerbe werden standardmäßig in Bytes gewertet. Jelly verwendet jedoch nicht UTF-8, sondern eine benutzerdefinierte Codepage , die jedes der 256 Zeichen, die es versteht, als einzelnes Byte codiert.
Dennis
@ Tennis ah, klug.
Cortices
7

Haskell, 19 Bytes

a#0=a
a#b=b#rem a b

Anwendungsbeispiel: 45 # 35-> 5.

Wieder Euklid.

PS: Natürlich gibt es auch eine eingebaute gcd.

nimi
quelle
Sie sollten den Trick erklären, der die Eingabereihenfolge umkehrt, um die bedingte Prüfung zu vermeiden
stolzer Haskeller
@ proudhaskeller: welcher trick? Jeder benutzt diesen Algorithmus, dh, er stoppt 0oder fährt mit dem Modul fort.
Nimi
Trotzdem, jeder nutzt den Trick
stolzer Haskeller 10.04.16
Dies ist, weniger golfen, fast genau das, was drin istPrelude
Michael Klein
6

Python 3, 31

3 Bytes gespart dank Sp3000.

g=lambda a,b:b and g(b,a%b)or a
Morgan Thrapp
quelle
3
In Python 3.5+:from math import*;gcd
Sp3000
@ Sp3000 Schön, ich wusste nicht, dass sie es auf Mathe verschoben hatten.
Morgan Thrapp
1
Während Sie gerade dabei sind:g=lambda a,b:b and g(b,a%b)or a
Sp3000
@ Sp3000 Danke! Ich habe gerade eine rekursive Lösung beendet, aber das ist noch besser als das, was ich hatte.
Morgan Thrapp
Built-Ins für GCD und LCM sind nicht zulässig, daher ist die 2. Lösung nicht gültig.
mbomb007
6

MATL , 11 9 Bytes

Bisher scheint noch niemand rohe Gewalt angewendet zu haben, also hier ist es.

ts:\a~f0)

Die Eingabe ist ein Spaltenarray mit den beiden Zahlen ( ;als Trennzeichen).

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Erläuterung

t     % Take input [a;b] implicitly. Duplicate
s     % Sum. Gives a+b
:     % Array [1,2,...,a+b]
\     % Modulo operation with broadcast. Gives a 2×(a+b) array
a~    % 1×(a+b) array that contains true if the two modulo operations gave 0
f0)   % Index of last true value. Implicitly display
Luis Mendo
quelle
5

C 38 Bytes

g(x,y){while(x^=y^=x^=y%=x);return y;}
Wie Chen
quelle
1
Sie müssen die Definition der Funktion in Ihr bytecount aufnehmen.
29.
1
@Riker Entschuldigung, ich füge die Definition hinzu und aktualisiere die Zählung
Wie Chen
Sie können zwei Bytes speichern, indem Sie die Funktion einfach ganstelle von benennen gcd.
Steadybox
@Steadybox ok, ja, das erste Mal dieser Community beitreten :)
Wie Chen
1
Willkommen bei PPCG!
29.
4

C 28 Bytes

Eine ziemlich einfache Funktion, die den Euclid-Algorithmus implementiert. Vielleicht kann man mit einem alternativen Algorithmus kürzer werden.

g(a,b){return b?g(b,a%b):a;}

Wenn man eine kleine Hauptverpackung schreibt

int main(int argc, char **argv)
{
  printf("gcd(%d, %d) = %d\n", atoi(argv[1]), atoi(argv[2]), g(atoi(argv[1]), atoi(argv[2])));
}

dann kann man ein paar werte testen:

$ ./gcd 6 21
GCD (6, 21) = 3
$ ./gcd 21 6
GCD (21, 6) = 3
$ ./gcd 6 8
GCD (6, 8) = 2
$ ./gcd 1 1
gcd (1, 1) = 1
$ ./gcd 6 16
GCD (6, 16) = 2
$ ./gcd 27 244
gcd (27, 244) = 1
CL-
quelle
4

Labyrinth , 18 Bytes

?}
:
)"%{!
( =
}:{

Beendet mit einem Fehler, aber die Fehlermeldung geht an STDERR.

Probieren Sie es online!

Das fühlt sich noch nicht optimal an, aber ich sehe derzeit keine Möglichkeit, die Schleife unter 3x3 zu komprimieren.

Erläuterung

Dies verwendet den euklidischen Algorithmus.

Erstens gibt es ein lineares Bit, um die Eingabe zu lesen und in die Hauptschleife zu gelangen. Der Anweisungszeiger (IP) beginnt in der oberen linken Ecke und geht nach Osten.

?    Read first integer from STDIN and push onto main stack.
}    Move the integer over to the auxiliary stack.
     The IP now hits a dead end so it turns around.
?    Read the second integer.
     The IP hits a corner and follows the bend, so it goes south.
:    Duplicate the second integer.
)    Increment.
     The IP is now at a junction. The top of the stack is guaranteed to be
     positive, so the IP turns left, to go east.
"    No-op.
%    Modulo. Since `n % (n+1) == n`, we end up with the second input on the stack.

Wir betreten nun eine Art while-do-Schleife, die den euklidischen Algorithmus berechnet. Die Stapeloberseiten enthalten aund b(zusätzlich zu einer impliziten unendlichen Anzahl von Nullen, die wir jedoch nicht benötigen). Wir werden die Stapel von Seite zu Seite darstellen und aufeinander zuwachsen:

    Main     Auxiliary
[ ... 0 a  |  b 0 ... ]

Die Schleife endet, sobald aNull ist. Eine Schleifeniteration funktioniert wie folgt:

=    Swap a and b.           [ ... 0 b  |  a 0 ... ]
{    Pull a from aux.        [ ... 0 b a  |  0 ... ]
:    Duplicate.              [ ... 0 b a a  |  0 ... ]
}    Move a to aux.          [ ... 0 b a  |  a 0 ... ]
()   Increment, decrement, together a no-op.
%    Modulo.                 [ ... 0 (b%a)  |  a 0 ... ]

Sie können sehen, wir haben ersetzt aund bmit b%aund ajeweils.

Wenn einmal b%aNull ist, bewegt sich die IP weiter nach Osten und führt Folgendes aus:

{    Pull the non-zero value, i.e. the GCD, over from aux.
!    Print it.
     The IP hits a dead end and turns around.
{    Pull a zero from aux.
%    Attempt modulo. This fails due to division by 0 and the program terminates.
Martin Ender
quelle
4

Julia, 21-15 Bytes

a\b=a>0?b%a\a:b

Rekursive Implementierung des euklidischen Algorithmus. Probieren Sie es online!

Wenn die Verwendung von integrierten Funktionen nicht verboten wäre gcd(3 Byte, integrierte GCD), würde dies zu einer besseren Bewertung führen.

Wie es funktioniert

a\b=             Redefine the binary operator \ as follows:
    a>0?     :       If a > 0:
        b%a\a        Resursively apply \ to b%a and a. Return the result.
              b      Else, return b.
Dennis
quelle
4

Cubix , 10 12 Bytes

?v%uII/;O@

Probieren Sie es hier aus

Dies wird wie folgt auf den Würfel gewickelt:

    ? v
    % u
I I / ; O @ . .
. . . . . . . .
    . .
    . .

Verwendet die euklidische Methode.

IIZwei Zahlen sind aus STDIN packen und auf dem Stapel
/Fluss reflektierte bis
%Mod die Oberseite des Stapels. Rest links oben auf Stapel
?Wenn TOS 0 dann weitermachen, sonst rechts abbiegen
vWenn nicht 0 , dann umleiten nach unten und unach rechts abbiegen zweimal wieder auf die mod
/Wenn 0 geht um den Würfel zu dem Reflektor
;Drop TOS, OAusgang TOS und @Ende

MickyT
quelle
Ich habe gerade eine 12-Byte-Cubix-Antwort geschrieben und dann angefangen, durch die Antworten zu scrollen, um zu sehen, ob ich mit beidem fertig werden musste, 0,xund x,0... dann bin ich auf diese Antwort gestoßen . Schön!
ETHproductions
4

C #, 24 Bytes

x=(a,b)=>b<1?a:x(b,a%b);
Morgan Thrapp
quelle
3

Windows Batch, 76 Bytes

Rekursive Funktion. Nennen Sie es wie GCD a bmit Dateinamen gcd.

:g
if %2 equ 0 (set f=%1
goto d)
set/a r=%1 %% %2
call :g %2 %r%
:d
echo %f%
Timtech
quelle
3

MATL, 7 Bytes

pG1$Zm/

Probieren Sie es online!

Erläuterung

Da wir die eingebaute GCD-Funktion ( Zdin MATL) nicht explizit verwenden können , habe ich die Tatsache ausgenutzt, dass das kleinste gemeinsame Vielfache von aund bder größte gemeinsame Nenner von aund bgleich dem Produkt von aund ist b.

p       % Grab the input implicitly and multiply the two elements
G       % Grab the input again, explicitly this time
1$Zm    % Compute the least-common multiple
/       % Divide the two to get the greatest common denominator
Suever
quelle
Sie können ein Byte mit zwei separaten Eingaben speichern:*1MZm/
Luis Mendo
3

Racket (Schema), 44 Bytes

Euklid-Implementierung in Racket (Schema)

(define(g a b)(if(= 0 b)a(g b(modulo a b))))

Edit: @Numeris Lösung nicht gesehen lol. Irgendwie haben wir unabhängig voneinander genau den gleichen Code

kronicmage
quelle
Funktioniert das in beiden?
NoOneIsHere
@NoOneIsHere ja, es funktioniert in beiden
kronicmage
3

> <> 32 Bytes

::{::}@(?\=?v{:}-
.!09}}${{/;n/>

Akzeptiert zwei Werte aus dem Stapel und wendet den euklidischen Algorithmus an, um ihre GCD zu erzeugen.

Sie können es hier ausprobieren !

Für eine viel bessere Antwort in> <>, schauen Sie sich Sok's an !

Aaron
quelle
1
Ich habe heute eine neue Sprache gefunden :)
nsane
3

ReRegex , 23 Bytes

Funktioniert identisch mit der Retina-Antwort.

^(_*)\1* \1*$/$1/#input

Probieren Sie es online!

Ein Taco
quelle
2

GML, 57 Bytes

a=argument0
b=argument1
while b{t=b;b=a mod b;a=t}return a
Timtech
quelle
2

Delphi 7, 148

Nun, ich denke, ich habe die neue schlechteste Sprache zum Golfen gefunden.

unit a;interface function g(a,b:integer):integer;implementation function g(a,b:integer):integer;begin if b=0then g:=a else g:=g(b,a mod b);end;end.
Morgan Thrapp
quelle
Oh, ich weiß nicht, Parenthetic ist ziemlich schlecht zum Golfen
MickyT
2

Hoon, 20 Bytes

|=
{@ @}
d:(egcd +<)

-

Hoon # 2, 39 Bytes

|=
{a/@ b/@}
?~
b
a
$(a b, b (mod a b))

Seltsamerweise ist die einzige Implementierung in Hoons stdlib for GCD diejenige, die für die RSA-Krypto verwendet wird, die auch einige andere Werte zurückgibt. Ich muss es in eine Funktion packen, die nur dvon der Ausgabe nimmt.

Die andere Implementierung ist nur die standardmäßige rekursive GCD-Definition.

Rendereinstellungen
quelle
2

Python 3.5, 70 82 73 Bytes:

lambda*a:max([i for i in range(1,max(*a)+1)if not sum(g%i for g in[*a])])

In notdiesem Fall wird sichergestellt, dass die Summe aller Zahlen in *argsModulo iNull ist.

Außerdem kann diese Lambda-Funktion jetzt so viele Werte aufnehmen, wie Sie möchten, solange die Anzahl der Werte >=2der gcdFunktion des Mathematikmoduls nicht entspricht. Zum Beispiel kann es die Werte aufnehmen 2,4,6,8,10und den korrekten GCD von 2 zurückgeben.

R. Kap
quelle
1
Sie sind wegen Variablennamen mit mehreren Zeichen verhaftet. (Oder Funktionsargumente, aber was auch immer)
CalculatorFeline
2

Ruby, 23 Bytes

g=->a,b{b>0?a:g[b,a%b]}

Denken Sie daran, dass Ruby-Blöcke mit g [...] oder g.call (...) anstelle von g (...) aufgerufen werden.

Teilgutschriften für die Voidpigeon

Luis Masuelli
quelle
2
Anstelle von g.call(a,b)Ihnen können verwenden g[a,b]. Stattdessen proc{|a,b|können Sie verwenden ->a,b{.
ängstlich
1
Sie können auch ein Byte speichern, indem Sie b>0anstelle b<=0der anderen Operanden die Reihenfolge ändern.
ängstlich
2

ARM-Maschinencode, 12 Byte:

Versammlung:

gcd: cmp r0, r1
     sublt r0, r0, r1
     bne gcd

Derzeit kann dies nicht kompiliert werden, aber jede Anweisung in ARM benötigt 4 Bytes. Wahrscheinlich könnte es mit dem THUMB-2-Modus abgespielt werden.

Styroporfliege
quelle
Netter Job, Mann, jeder, der das im Maschinencode macht, bekommt ernsthafte Requisiten von mir.
Mike Shlanta
Dies scheint ein Versuch zu sein, Euklids Algo nur durch Subtraktion zu erreichen , aber ich denke nicht, dass es funktioniert. Wenn r0 > r1dann subltnichts tun wird ( ltPrädikat ist falsch) und bnewird eine Endlosschleife sein. Ich denke, Sie brauchen einen Swap, wenn nicht lt, so dass die gleiche Schleife tun kann b-=aoder a-=bwie benötigt. Oder eine Verneinung, wenn das Sub produziert (aka ausleihen).
Peter Cordes
Diese ARM-Anweisungssatzanleitung verwendet tatsächlich einen Subtraktions-GCD-Algorithmus als Beispiel für die Vorhersage. (S. 25). Sie benutzen cmp r0, r1/ subgt r0, r0, r1/ sublt r1, r1, r0/ bne gcd. Das sind 16B in ARM-Anweisungen, vielleicht 12 in thumb2-Anweisungen?
Peter Cordes
1
Auf x86 verwaltete ich 9 Bytes mit: sub ecx, eax/ jae .no_swap/ add ecx,eax/ xchg ecx,eax/ jne. Anstelle eines cmp setze ich also einfach ein Sub, mache es dann rückgängig und tausche es aus, wenn das Sub in die andere Richtung hätte gehen sollen. Ich habe das getestet und es funktioniert. ( addBeendet das jneProgramm nicht zur falschen Zeit, da es keine Null erzeugen kann, es sei denn, eine der Eingaben war anfangs Null, und wir unterstützen das nicht. Update: Wir müssen beide Eingaben als Null unterstützen: /)
Peter Cordes
Für Thumb2 gibt es eine iteAnweisung: if-then-else. Sollte perfekt für cmp / sub in eine Richtung / sub in die andere Richtung sein.
Peter Cordes
2

TI-Basic, 10 Bytes

Prompt A,B:gcd(A,B

Nicht konkurrierend aufgrund der neuen Regel, die verbietet, dass gcd eingebaut ist


17-Byte- Lösung ohne gcd(eingebautes

Prompt A,B:abs(AB)/lcm(A,B

Nicht konkurrierend wegen neuer Regel, die lcm-Einbauten verbietet


27-Byte- Lösung ohne gcd(oder lcm(eingebaut:

Prompt A,B:While B:B→T:BfPart(A/B→B:T→A:End:A

35 Byte rekursive Lösung ohne gcd(oder mit lcm(integrierten Funktionen (erfordert ein 2,53 MP-Betriebssystem oder höher, muss benannt werden prgmG ):

If Ans(2:Then:{Ans(2),remainder(Ans(1),Ans(2:prgmG:Else:Disp Ans(1:End

Sie würden Argumente an die rekursive Variante übergeben, wie {A,B}dies beispielsweise {1071, 462}:prgmGder Fall wäre 21.

Timtech
quelle
Färbe mich beeindruckt.
Mike Shlanta
Sie sollten wahrscheinlich erwähnen, dass der letzte als gespeichert werden muss prgmG.
ein Spaghetto
2

Oracle SQL 11.2, 104 118 Bytes

SELECT MAX(:1+:2-LEVEL+1)FROM DUAL WHERE(MOD(:1,:1+:2-LEVEL+1)+MOD(:2,:1+:2-LEVEL+1))*:1*:2=0 CONNECT BY LEVEL<=:1+:2;

Bei Eingabe von 0 behoben

Jeto
quelle
Funktioniert nicht richtig, wenn einer der Eingänge Null ist.
Egor Skriptunoff
Das sollte dir ein paar ersparenSELECT MAX(LEVEL)FROM DUAL WHERE MOD(:1,LEVEL)+MOD(:2,LEVEL)=0 CONNECT BY LEVEL<=:1+:2;
MickyT 10.04.16
2

> <> , 12 + 3 = 15 Bytes

:?!\:}%
;n~/

Erwartet, dass die Eingabenummern auf dem Stapel vorhanden sind, also +3 Byte für das -vFlag. Probieren Sie es online!

Eine weitere Implementierung des Euklidischen Algorithmus.

Sok
quelle