Twoim zadaniem jest obliczenie największego wspólnego dzielnika (GCD) z dwóch podanych liczb całkowitych w jak najmniejszej liczbie bajtów kodu.

Możesz napisać program lub funkcję, przyjmując dane wejściowe i zwracając dane wyjściowe za pomocą dowolnej z naszych akceptowanych standardowych metod (w tym STDIN / STDOUT, parametry funkcji / zwracane wartości, argumenty wiersza polecenia itp.).

Dane wejściowe będą dwie nieujemne liczby całkowite. Powinieneś być w stanie obsłużyć albo pełny zakres obsługiwany przez domyślny typ liczb całkowitych twojego języka, albo zakres [0,255], w zależności od tego, który jest większy. Masz gwarancję, że co najmniej jedno z wejść będzie niezerowe.

Nie wolno używać wbudowanych funkcji obliczających GCD lub LCM (najmniejszą wspólną wielokrotność).

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

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

Retina , 16 lat

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

W ogóle nie korzysta z algorytmu Euclid - zamiast tego znajduje GCD za pomocą grup dopasowania wyrażeń regularnych.

Wypróbuj online. - W tym przykładzie obliczono GCD (8,12).

Wprowadź jako 2 liczby całkowite oddzielone spacjami. Zauważ, że I / O jest jednoargumentowy. Jeśli nie jest to do zaakceptowania, możemy to zrobić:

Retina, 30

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

Wypróbuj online.

Jak zauważa @ MartinBüttner, to rozpada się na duże liczby (jak to zwykle ma miejsce w przypadku wszystkiego, co jednoargumentowe). Co najmniej wejście INT_MAX będzie wymagało alokacji ciągu 2 GB.

Kod maszynowy i386 (x86-32), 8 bajtów (9B dla niepodpisanych)

+ 1B, jeśli musimy obsłużyć b = 0dane wejściowe.

amd64 (x86-64) kod maszynowy, 9 bajtów (10B dla niepodpisanych lub 14B 13B dla liczb całkowitych 64b podpisanych lub niepodpisanych)

10 9B dla bez znaku na amd64, który psuje się przy obu wejściach = 0

Wejścia są 32bit niezerowe podpisane liczby całkowite eaxi ecx. Wyjście w 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

Ta struktura pętli zawodzi w przypadku testowym, w którym ecx = 0. ( divpowoduje wykonanie #DEsprzętu przy dzieleniu przez zero. (W Linuksie jądro dostarcza SIGFPE(wyjątek zmiennoprzecinkowy)). Jeśli punkt wejścia do pętli był tuż przed inc, uniknęlibyśmy problemu. Wersja x86-64 może sobie z tym poradzić za darmo, patrz poniżej.

Odpowiedź Mike Shlanta była punktem wyjścia . Moja pętla robi to samo, co jego, ale dla liczb całkowitych ze cdqznakiem, ponieważ jest o jeden bajt krótsza niż xor edx,edx. I tak, działa poprawnie z jednym lub dwoma wejściami ujemnymi. Wersja Mike'a będzie działać szybciej i zajmie mniej miejsca w pamięci podręcznej uop ( xchgjest 3 uops na procesorach Intela i loopjest naprawdę wolna na większości procesorów ), ale ta wersja wygrywa przy rozmiarze kodu maszynowego.

Z początku nie zauważyłem, że pytanie wymaga niepodpisanego 32-bitowego. Powrót do xor edx,edxzamiast cdqkosztowałby jeden bajt. divma taki sam rozmiar jak idivi wszystko inne może pozostać niezmienione ( xchgdo przenoszenia danych i inc/loopnadal działać).

Co ciekawe, dla 64- bitowego rozmiaru operandu ( raxi rcx) wersje podpisane i niepodpisane mają ten sam rozmiar. Podpisana wersja wymaga prefiksu REX dla cqo(2B), ale wersja bez znaku może nadal używać 2B xor edx,edx.

W kodzie 64-bitowym inc ecxjest 2B: jednobajtowe inc r32i dec r32opcodes zostały zmienione na prefiksy REX. inc/loopnie zapisuje żadnego rozmiaru kodu w trybie 64-bitowym, więc równie dobrze możesz test/jnz. Operowanie na 64-bitowych liczbach całkowitych dodaje kolejny jeden bajt na instrukcję w prefiksach REX, z wyjątkiem looplub jnz. Reszta może mieć wszystkie zera na niskim 32b (np. gcd((2^32), (2^32 + 1))), Więc musimy przetestować cały rcx i nie możemy zapisać bajtu test ecx,ecx. Jednak wolniejszy jrcxzinsn to tylko 2B i możemy go umieścić na górze pętli, aby obsłużyć ecx=0przy wejściu :

## 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

W pełni działający program testowy, w tym program mainuruchamiający printf("...", gcd(atoi(argv[1]), atoi(argv[2])) ); źródło i asm w programie Godbolt Compiler Explorer , dla wersji 32 i 64b. Testowane i działające dla 32-bitowych ( -m32), 64-bitowych ( -m64) i x32 ABI ( -mx32) .

Zawiera także: wersję wykorzystującą tylko powtarzane odejmowanie , która wynosi 9B dla niepodpisanego, nawet dla trybu x86-64, i może przyjmować jedno z danych wejściowych w dowolnym rejestrze. Jednak nie może obsłużyć żadnego z wejść przy wejściu 0 (wykrywa, kiedy subtworzy zero, czego x-0 nigdy nie robi).

GNU C wbudowane źródło asm dla wersji 32-bitowej (kompilacja z 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;
}

Normalnie napisałbym całą funkcję w asm, ale wbudowany asm GNU C wydaje się być najlepszym sposobem na włączenie fragmentu, który może mieć wejścia / wyjścia w dowolnych regach, które wybieramy. Jak widać, wbudowana składnia asm GNU C powoduje, że asm jest brzydki i głośny. To także bardzo trudny sposób na naukę asm .

W rzeczywistości skompilowałby się i działałby w .att_syntax noprefixtrybie, ponieważ wszystkie użyte insny to albo pojedynczy / brak operandu, albo xchg. Niezbyt przydatna obserwacja.

Sześciokąt , 17 bajtów

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

Rozłożony:

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

Wypróbuj online!

Dopasowanie go do boku o długości 3 było dziecinnie proste. Golenie tych dwóch bajtów na końcu nie było ... Nie jestem również przekonany, czy to optymalne, ale jestem pewien, że myślę, że jest blisko.

Wyjaśnienie

Kolejna implementacja algorytmu euklidesowego.

Program wykorzystuje trzy krawędzie pamięci, które nazywam A , B i C , przy czym wskaźnik pamięci (MP) zaczyna się tak, jak pokazano:

Oto schemat kontrolny:

Przepływ sterowania rozpoczyna się na szarej ścieżce krótkim bitem liniowym do wprowadzania:

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

Zauważ, że kod jest teraz zawijany wokół krawędzi do <lewego rogu. To <działa jak gałąź. Jeśli bieżąca krawędź wynosi zero (tzn. Algorytm euklidesowy kończy się), adres IP jest odchylany w lewo i przechodzi na czerwoną ścieżkę. W przeciwnym razie iteracja algorytmu euklidesowego jest obliczana na zielonej ścieżce.

Najpierw rozważymy zieloną ścieżkę. Należy pamiętać, że >i \wszystko działa jak lustra, które po prostu odchyliłyby wskaźnik instrukcji. Należy również pamiętać, że przepływ kontrolny owija się wokół krawędzi trzy razy, raz od dołu do góry, raz od prawego rogu do dolnego rzędu i wreszcie od prawego dolnego rogu do lewego rogu, aby ponownie sprawdzić warunek. Zauważ też, że .nie ma operacji.

To pozostawia następujący kod liniowy dla pojedynczej iteracji:

{    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.

Teraz jesteśmy z powrotem tam, gdzie zaczęliśmy, z tą różnicą, że trzy krawędzie zmieniały swoje role cyklicznie (pierwotne C przyjmuje teraz rolę B, a oryginalne B rolę A ...). W efekcie mamy relpaced wejść Ai Bz Bi A % Bodpowiednio.

Raz A % B(na krawędzi C ) wynosi zero, GCD znajduje się na krawędzi B . Ponownie po >prostu odchyla adres IP, więc na czerwonej ścieżce wykonujemy:

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

32-bitowy kod maszynowy little-endian x86, 14 bajtów

Wygenerowano za pomocą 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

T-SQL, 153 169 bajtów

Ktoś wspomniał o najgorszym języku do gry w golfa?

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

Tworzy funkcję cenioną w tabeli, która wykorzystuje zapytanie rekurencyjne w celu opracowania wspólnych dzielników. Następnie zwraca maksimum . Teraz używa algorytmu euklidesowego do ustalenia GCD pochodzącego z mojej odpowiedzi tutaj .

Przykładowe użycie

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)

Galaretka, 7 bajtów

ṛß%ðḷṛ?

Rekurencyjna implementacja algorytmu euklidesowego. Wypróbuj online!

Gdyby wbudowane nie były zabronione, g(1 bajt, wbudowany GCD) osiągnąłby lepszy wynik.

Jak to działa

ṛß%ðḷṛ?  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).

Haskell, 19 bajtów

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

Przykład użycia: 45 # 35-> 5.

Znowu Euclid.

PS: oczywiście jest też wbudowany gcd.

Python 3, 31

Zaoszczędzono 3 bajty dzięki Sp3000.

g=lambda a,b:b and g(b,a%b)or a

MATL , 11 9 bajtów

Do tej pory nikt nie używał brutalnej siły, więc oto jest.

ts:\a~f0)

Dane wejściowe to tablica kolumn z dwiema liczbami (używana ;jako separator).

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Wyjaśnienie

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

C, 38 bajtów

g(x,y){while(x^=y^=x^=y%=x);return y;}

C, 28 bajtów

Dość prosta funkcja implementująca algorytm Euclida. Być może można skrócić się stosując alternatywny algorytm.

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

Jeśli ktoś pisze małe opakowanie główne

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])));
}

wtedy można przetestować kilka wartości:

$ ./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

Labirynt , 18 bajtów

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

Kończy się z błędem, ale komunikat o błędzie trafia do STDERR.

Wypróbuj online!

Nie wydaje mi się to jeszcze optymalne, ale w tej chwili nie widzę sposobu na kompresję pętli poniżej 3x3.

Wyjaśnienie

Wykorzystuje to algorytm euklidesowy.

Po pierwsze, istnieje liniowy bit do odczytu danych wejściowych i przejścia do głównej pętli. Wskaźnik instrukcji (IP) zaczyna się w lewym górnym rogu i kieruje się na wschód.

?    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.

Teraz wchodzimy w rodzaj pętli while-do, która oblicza algorytm euklidesowy. Wierzchołki stosów zawierają ai b(na domniemaną nieskończoną liczbę zer, ale nie będziemy ich potrzebować). Będziemy reprezentować stosy obok siebie, rosnąc ku sobie:

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

Pętla kończy się raz, gdy awynosi zero. Iteracja pętli działa w następujący sposób:

=    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 ... ]

Można zobaczyć, jakie otrzymuje ai bz b%ai aodpowiednio.

Wreszcie, gdy b%awynosi zero, adres IP przesuwa się na wschód i wykonuje:

{    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.

Julia, 21 15 bajtów

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

Rekurencyjna implementacja algorytmu euklidesowego. Wypróbuj online!

Gdyby wbudowane nie były zabronione, gcd(3 bajty, wbudowany GCD) osiągnąłby lepszy wynik.

Jak to działa

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.

Cubix , 10 12 bajtów

?v%uII/;O@

Wypróbuj tutaj

Spowalnia to kostkę w następujący sposób:

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

Wykorzystuje metodę euklidesową.

IIDwie liczby są pobierane ze STDIN i umieszczane na stosie
/Odbicie przepływu
%Mod na górze stosu. Resztka pozostawiona na szczycie stosu
?Jeśli TOS 0, to kontynuuj, w przeciwnym razie skręć w prawo
vJeśli nie 0, przekieruj w dół i uskręć dwa razy w prawo na mod
/Jeśli 0 przejdź wokół sześcianu do
;TOS odbicia , Owyślij TOS i @zakończ

C #, 24 bajty

x=(a,b)=>b<1?a:x(b,a%b);

Pakiet Windows, 76 bajtów

Funkcja rekurencyjna. Nazwij to tak jak GCD a bz nazwą pliku gcd.

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

MATL, 7 bajtów

pG1$Zm/

Wypróbuj online!

Wyjaśnienie

Ponieważ nie możemy jednoznacznie użyć wbudowanej funkcji GCD ( Zdw MATL), wykorzystałem fakt, że najmniej wspólna wielokrotność ai brazy największy wspólny mianownik ai bjest równa iloczynowi ai 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

Rakieta (schemat), 44 bajty

Wdrożenie Euclid w Racket (schemat)

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

Edycja: Nie widziałem lol rozwiązania @Numeri. Jakoś otrzymaliśmy dokładnie ten sam kod niezależnie

> <> , 32 bajty

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

Akceptuje dwie wartości ze stosu i stosuje algorytm euklidesowy do wygenerowania GCD.

Możesz spróbować tutaj !

Aby uzyskać znacznie lepszą odpowiedź w> <>, sprawdź Sok's !

ReRegex , 23 bajty

Działa identycznie jak odpowiedź Retina.

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

Wypróbuj online!

GML, 57 bajtów

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

Delphi 7, 148

Myślę, że znalazłem nowy najgorszy język do gry w golfa.

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.

Hoon, 20 bajtów

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

-

Hoon # 2, 39 bajtów

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

Co dziwne, jedyną implementacją w stdlib Hoon dla GCD jest ta używana w jego kryptografii RSA, która zwraca również inne wartości. Muszę zawinąć w funkcję, która bierze tylko ddane wyjściowe.

Druga implementacja to tylko domyślna rekurencyjna definicja GCD.

Python 3.5, 70 82 73 bajty:

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

W nottym przypadku upewni się, że suma wszystkich liczb w *argsmodulo iwynosi zero.

Ponadto, teraz ta funkcja lambda może przyjmować tyle wartości, ile chcesz, pod warunkiem, że ilość wartości jest >=2inna, niż gcdfunkcja modułu matematycznego. Na przykład może przyjmować wartości 2,4,6,8,10i zwracać prawidłowy GCD 2.

Rubinowy, 23 bajty

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

pamiętaj, że ruby ​​są wywoływane za pomocą g [...] lub g.call (...), zamiast g (...)

częściowe kredyty dla gołębia pustki

Kod maszynowy ARM, 12 bajtów:

montaż:

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

Obecnie nie można tego skompilować, ale każda instrukcja w ARM zajmuje 4 bajty. Prawdopodobnie można go zagrać w golfa za pomocą trybu THUMB-2.

TI-Basic, 10 bajtów

Prompt A,B:gcd(A,B

Nie konkuruje z powodu nowej reguły zabraniającej wbudowania gcd

17 bajtowe rozwiązanie bez gcd(wbudowanego

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

Nie konkuruje z powodu nowej reguły zabraniającej wbudowania lcm

27-bajtowe rozwiązanie bez gcd(lub lcm(wbudowane:

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

35-bajtowe rozwiązanie rekurencyjne bez gcd(lub lcm(wbudowane (wymaga systemu operacyjnego 2,53 MP lub nowszego, należy je nazwać prgmG ):

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

Przekazywałbyś argumenty do wariantu rekurencyjnego, ponieważ {A,B}na przykład {1071, 462}:prgmGdałoby to wynik 21.

05AB1E , 10 bajtów

Kod:

EàF¹N%O>iN

Wypróbuj online!

Z wbudowanymi:

¿

Wyjaśnienie:

¿   # Implicit input, computes the greatest common divisor.
    # Input can be in the form a \n b, which computes gcd(a, b)
    # Input can also be a list in the form [a, b, c, ...], which computes the gcd of
      multiple numbers.

Wypróbuj online! lub Wypróbuj z wieloma numerami .

Oracle SQL 11.2, 104 118 bajtów

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;

Naprawiono dla wejścia 0

> <> , 12 + 3 = 15 bajtów

:?!\:}%
;n~/

Oczekuje, że liczby wejściowe będą obecne na stosie, więc +3 bajty dla -vflagi. Wypróbuj online!

Kolejna implementacja algorytmu euklidesowego.