Su tarea es calcular el máximo común divisor (GCD) de dos enteros dados en el menor número de bytes posible.

Puede escribir un programa o función, tomando entradas y devolviendo salidas a través de cualquiera de nuestros métodos estándar aceptados (incluidos STDIN / STDOUT, parámetros de función / valores de retorno, argumentos de línea de comandos, etc.).

La entrada será dos enteros no negativos. Debería poder manejar el rango completo compatible con el tipo entero predeterminado de su idioma, o el rango [0,255], el que sea mayor. Se le garantiza que al menos una de las entradas será distinta de cero.

No está autorizado a utilizar elementos integrados que calculen el GCD o el LCM (mínimo común múltiplo).

Se aplican reglas estándar de código de golf .

Casos de prueba

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

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

Esto no usa el algoritmo de Euclides en absoluto; en cambio, encuentra el GCD usando grupos de coincidencia de expresiones regulares.

Pruébalo en línea. - Este ejemplo calcula el MCD (8,12).

Ingrese como 2 enteros separados por espacios. Tenga en cuenta que la E / S está en unario. Si eso no es aceptable, entonces podemos hacer esto:

Retina, 30

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

Pruébalo en línea.

Como señala @ MartinBüttner, esto se desmorona para un gran número (como suele ser el caso de cualquier cosa unaria). Como mínimo, una entrada de INT_MAX requerirá la asignación de una cadena de 2GB.

Código de máquina i386 (x86-32), 8 bytes (9B para sin firmar)

+ 1B si necesitamos manejar la b = 0entrada.

Código de máquina amd64 (x86-64), 9 bytes (10B para sin signo, o 14B 13B para enteros de 64b con signo o sin signo)

10 9B para unsigned en amd64 que se rompe con input = 0

Las entradas son enteros con signo distinto de cero de 32 bits en eaxy ecx. La producción en 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

Esta estructura de bucle falla el caso de prueba donde ecx = 0. ( divprovoca una #DEejecución de hardware en dividir entre cero. (En Linux, el kernel entrega una SIGFPE(excepción de punto flotante)). Si el punto de entrada del bucle estaba justo antes delinc , evitaríamos el problema. La versión x86-64 puede manejarlo gratis, ver abajo.

La respuesta de Mike Shlanta fue el punto de partida para esto . Mi bucle hace lo mismo que el suyo, pero para enteros con signo porque cdqes un byte más corto que xor edx,edx. Y sí, funciona correctamente con una o ambas entradas negativas. La versión de Mike se ejecutará más rápido y ocupará menos espacio en la caché de UOP ( xchges de 3 uops en las CPU de Intel, y loopes realmente lenta en la mayoría de las CPU ), pero esta versión gana en tamaño de código de máquina.

Al principio no me di cuenta de que la pregunta requería 32 bits sin firmar . Volver a en xor edx,edxlugar de cdqcostaría un byte. dives del mismo tamaño que idiv, y todo lo demás puede permanecer igual ( xchgpara el movimiento de datos yinc/loop seguir funcionando).

Curiosamente, para el tamaño de operando de 64 bits ( raxy rcx), las versiones firmadas y sin firmar son del mismo tamaño. La versión firmada necesita un prefijo REX para cqo(2B), pero la versión sin firmar aún puede usar 2B xor edx,edx.

En el código de 64 bits, inc ecxes 2B: el byte único inc r32y los códigos de dec r32operación se reutilizaron como prefijos REX. inc/loopno guarda ningún tamaño de código en modo de 64 bits, por lo que también podría hacerlo test/jnz. Operar en enteros de 64 bits agrega otro byte por instrucción en los prefijos REX, excepto para loopo jnz. Es posible que el resto tenga todos los ceros en los bajos 32b (por ejemplo gcd((2^32), (2^32 + 1))), por lo que debemos probar todo el rcx y no podemos guardar un byte con test ecx,ecx. Sin embargo, el jrcxzinsn más lento es solo 2B, y podemos ponerlo en la parte superior del ciclo para manejarlo ecx=0en la entrada :

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

Programa de prueba ejecutable completo, incluyendo una mainque corre printf("...", gcd(atoi(argv[1]), atoi(argv[2])) ); la fuente y la salida de ASM en el Godbolt Compilador Explorador , para los 32 y 64b versiones. Probado y funcionando para 32bit ( -m32), 64bit ( -m64) y el x32 ABI ( -mx32) .

También se incluye: una versión que usa solo resta repetida , que es 9B para sin signo, incluso para el modo x86-64, y puede tomar una de sus entradas en un registro arbitrario. Sin embargo, no puede manejar que ninguna entrada sea 0 en la entrada (detecta cuandosub produce un cero, que x - 0 nunca lo hace).

Fuente asm en línea de GNU C para la versión de 32 bits (compilar con 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;
}

Normalmente escribiría una función completa en asm, pero GNU C inline asm parece ser la mejor manera de incluir un fragmento que puede tener entradas / salidas en cualquier reg que elijamos. Como puede ver, la sintaxis asm en línea de GNU C hace que sea feo y ruidoso. También es una forma realmente difícil de aprender asm .

En realidad, se compilaría y funcionaría en .att_syntax noprefixmodo, ya que todas las entradas utilizadas son de un solo operando o no xchg. No es realmente una observación útil.

Hexagonía , 17 bytes.

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

Desplegado:

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

Pruébalo en línea!

Encajarlo en la longitud lateral 3 fue muy fácil. Limitar esos dos bytes al final no fue ... Tampoco estoy convencido de que sea óptimo, pero estoy seguro de que creo que está cerca.

Explicación

Otra implementación del algoritmo euclidiano.

El programa usa tres bordes de memoria, que llamaré A , B y C , con el puntero de memoria (MP) comenzando como se muestra:

Aquí está el diagrama de flujo de control:

El flujo de control comienza en la ruta gris con un bit lineal corto para la entrada:

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

Tenga en cuenta que el código ahora se ajusta alrededor de los bordes al < en la esquina izquierda. Esto <actúa como una rama. Si el borde actual es cero (es decir, el algoritmo euclidiano termina), la IP se desvía hacia la izquierda y toma el camino rojo. De lo contrario, se calcula una iteración del algoritmo euclidiano en el camino verde.

Primero consideraremos el camino verde. Tenga en cuenta que >y \todos actúan como espejos que simplemente desvían el puntero de instrucciones. También tenga en cuenta que el flujo de control se envuelve alrededor de los bordes tres veces, una vez desde abajo hacia arriba, una vez desde la esquina derecha a la fila inferior y finalmente desde la esquina inferior derecha a la esquina izquierda para volver a verificar la condición. También tenga en cuenta que. son no-ops.

Eso deja el siguiente código lineal para una sola iteración:

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

Ahora estamos de vuelta donde comenzamos, excepto que los tres bordes han cambiado sus roles cíclicamente (el C original ahora toma el rol de B y el B original el rol de A ...). En efecto, hemos reequilibrado las entradas Ay Bcon ByA % B , respectivamente.

Una vez A % B(en el borde C ) es cero, el GCD se puede encontrar en el borde B . Nuevamente, el >solo desvía la IP, por lo que en el camino rojo ejecutamos:

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

Código de máquina x86 little-endian de 32 bits, 14 bytes

Generado usando 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 bytes

Alguien mencionó el peor idioma para jugar al golf?

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

Crea una función con valores de tabla que utiliza una consulta recursiva para resolver los divisores comunes. Luego devuelve el máximo . Ahora usa el algoritmo euclidiano para determinar el MCD derivado de mi respuesta aquí .

Ejemplo de uso

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)

Jalea, 7 bytes

ṛß%ðḷṛ?

Implementación recursiva del algoritmo euclidiano. Pruébalo en línea!

Si las incorporaciones no estuvieran prohibidas, g(1 byte, GCD incorporado) obtendría una mejor puntuación.

Cómo funciona

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

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

Ejemplo de uso: 45 # 35->5 .

Euclides, otra vez.

PD: por supuesto, también hay un incorporado gcd.

Pitón 3, 31

Guardado 3 bytes gracias a Sp3000.

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

MAT , 11 9 bytes

Nadie parece haber usado la fuerza bruta hasta ahora, así que aquí está.

ts:\a~f0)

La entrada es una matriz de columnas con los dos números (usando ; como separador).

Pruébalo en línea! o verificar todos los casos de prueba .

Explicación

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 bytes

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

C, 28 bytes

Una función bastante sencilla que implementa el algoritmo de Euclides. Quizás uno puede acortarse usando un algoritmo alternativo.

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

Si uno escribe un pequeño contenedor principal

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

entonces uno puede probar algunos valores:

$ ./gcd 6 21
mcd (6, 21) = 3
$ ./gcd 21 6
mcd (21, 6) = 3
$ ./gcd 6 8
mcd (6, 8) = 2
$ ./gcd 1 1
mcd (1, 1) = 1
$ ./gcd 6 16
mcd (6, 16) = 2
$ ./gcd 27 244
mcd (27, 244) = 1

Laberinto , 18 bytes

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

Termina con un error, pero el mensaje de error va a STDERR.

Pruébalo en línea!

Esto todavía no se siente óptimo, pero no estoy viendo una forma de comprimir el ciclo por debajo de 3x3 en este momento.

Explicación

Esto usa el algoritmo euclidiano.

Primero, hay un bit lineal para leer la entrada y entrar en el bucle principal. El puntero de instrucciones (IP) comienza en la esquina superior izquierda, hacia el este.

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

Ahora ingresamos una especie de ciclo while-do que calcula el algoritmo euclidiano. La parte superior de las pilas contiene ay b(además de una cantidad infinita implícita de ceros, pero no los necesitaremos). Representaremos las pilas de lado a lado, creciendo unas hacia otras:

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

El ciclo termina una vez que aes cero. Una iteración de bucle funciona de la siguiente manera:

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

Puedes ver, hemos reemplazado ay bcon b%aya respectivamente.

Finalmente, una vez que b%aes cero, la IP sigue moviéndose hacia el este y ejecuta:

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

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

Implementación recursiva del algoritmo euclidiano. Pruébalo en línea!

Si los complementos no estuvieran prohibidos, gcd (3 bytes, GCD incorporado) obtendría una mejor puntuación.

Cómo funciona

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 bytes

?v%uII/;O@

Pruébalo aquí

Esto se envuelve en el cubo de la siguiente manera:

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

Utiliza el método euclidiano.

IISe toman dos números de STDIN y se colocan en la pila.
/Flow se refleja en
%Mod the Top of Stack. Resto que queda en la parte superior de la pila
?Si TOS 0 entonces continuar, de lo contrario gire a la derecha
vSi no es 0, entonces redirigir hacia abajo y ugire a la derecha dos veces de nuevo en el mod
/Si 0 dar la vuelta al cubo para el reflector
;TOS gota, Ola salida de TOS y @finales

C #, 24 bytes

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

Lote de Windows, 76 bytes

Función recursiva. Llámalo como GCD a bcon el nombre del archivo 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 bytes

pG1$Zm/

Pruébalo en línea!

Explicación

Como no podemos usar explícitamente la función incorporada de GCD ( Zden MATL), he explotado el hecho de que el mínimo común múltiplo de ay bel mayor común denominador de ay bes igual al producto de ay 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

Raqueta (esquema), 44 bytes

Implementación de Euclides en Raqueta (Esquema)

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

Editar: No vi la solución de @Numeri jajaja. De alguna manera obtuvimos exactamente el mismo código independientemente

> <> , 32 bytes

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

Acepta dos valores de la pila y aplica el algoritmo euclidiano para producir su GCD.

Puedes probarlo aquí !

Para una respuesta mucho mejor en> <>, ¡echa un vistazo a Sok's !

ReRegex , 23 bytes

Funciona de manera idéntica a la respuesta Retina.

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

Pruébalo en línea!

GML, 57 bytes

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

Delfos 7, 148

Bueno, creo que he encontrado el nuevo peor idioma para el golf.

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 bytes

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

-

Hoon # 2, 39 bytes

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

Curiosamente, la única implementación en stdlib de Hoon para GCD es la que se usa para su criptografía RSA, que también devuelve algunos otros valores. Tengo que envolverlo en una función que solo toma dde la salida.

La otra implementación es solo la definición GCD recursiva predeterminada.

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

En noteste caso, se asegurará de que la suma de todos los números en el *argsmódulo isea ​​cero.

Además, ahora esta función lambda puede tomar tantos valores como desee, siempre que la cantidad de valores sea >=2diferente a la gcdfunción del módulo matemático. Por ejemplo, puede tomar los valores 2,4,6,8,10y devolver el MCD correcto de 2.

Ruby, 23 bytes

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

recuerde que los bloques de rubí se llaman con g [...] o g.call (...), en lugar de g (...)

créditos parciales a voidpigeon

Código de máquina ARM, 12 bytes:

montaje:

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

Actualmente no se puede compilar esto, pero cada instrucción en ARM toma 4 bytes. Probablemente podría jugar golf usando el modo THUMB-2.

TI-Basic, 10 bytes

Prompt A,B:gcd(A,B

No competir debido a la nueva regla que prohíbe las incorporaciones de gcd

Solución de 17 bytes sin gcd(incorporado

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

No competir debido a la nueva regla que prohíbe los mcm incorporados

Solución de 27 bytes sin gcd(o lcm(incorporada:

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

Solución recursiva de 35 bytes sin gcd(o lcm(incorporada (se debe nombrar un sistema operativo de 2.53 MP o superior prgmG):

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

Pasarías argumentos a la variante recursiva como {A,B} por ejemplo {1071, 462}:prgmG, produciría 21.

05AB1E , 10 bytes

Código:

EàF¹N%O>iN

Pruébalo en línea!

Con incorporados:

¿

Explicación:

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

Pruébalo en línea! o Prueba con varios números .

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;

Fijo para entrada de 0

> <> , 12 + 3 = 15 bytes

:?!\:}%
;n~/

Espera que los números de entrada estén presentes en la pila, por lo que +3 bytes para el -v indicador. Pruébalo en línea!

Otra implementación del algoritmo euclidiano.