Ваша задача - вычислить наибольший общий делитель (GCD) из двух заданных целых чисел в минимально возможном количестве байтов кода.

Вы можете написать программу или функцию, получая ввод и возвращая вывод любым из наших общепринятых стандартных методов (включая STDIN / STDOUT, параметры функции / возвращаемые значения, аргументы командной строки и т. Д.).

На входе будут два неотрицательных целых числа. Вы должны иметь возможность обрабатывать либо полный диапазон, поддерживаемый целочисленным типом по умолчанию вашего языка, либо диапазон [0,255], в зависимости от того, что больше. Вам гарантировано, что хотя бы один из входов будет ненулевым.

Вы не можете использовать встроенные модули, которые вычисляют либо GCD, либо LCM (наименьшее общее кратное).

Применяются стандартные правила игры в гольф .

Тестовые случаи

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

Сетчатка , 16

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

Это не использует алгоритм Евклида вообще - вместо этого он находит GCD, используя группы соответствия регулярному выражению.

Попробуйте онлайн. - В этом примере рассчитывается GCD (8,12).

Введите как 2 целых числа через пробел. Обратите внимание, что ввод / вывод в унарном виде. Если это не приемлемо, тогда мы можем сделать это:

Сетчатка, 30

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

Попробуйте онлайн.

Как указывает @ MartinBüttner, это распадается для больших чисел (как это обычно бывает для чего-то унарного). Как минимум, для ввода INT_MAX потребуется выделение строки размером 2 ГБ.

i386 (x86-32) машинный код, 8 байт (9B для без знака)

+1, если нам нужно обработать b = 0ввод.

машинный код amd64 (x86-64), 9 байтов (10B для неподписанных или 14B 13B для 64-целых чисел со знаком или без знака)

10 9B для неподписанного на amd64, который разрывается при любом входе = 0

Входы 32bit ненулевые подписанные целые числа eaxи ecx. Выход в 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

Эта структура цикла не проходит тестовый случай, где ecx = 0. ( divвызывает #DEаппаратное выполнение при делении на ноль. (В Linux ядро ​​выдает SIGFPE(исключение с плавающей запятой).) Если бы точка входа в цикл была прямо перед inc, мы бы избежали этой проблемы. Версия x86-64 может справиться с этим бесплатно смотрите ниже.

Ответ Майка Шланты был отправной точкой для этого . Мой цикл делает то же самое, что и его, но для целых чисел со cdqзнаком, потому что он на один байт короче xor edx,edx. И да, он работает правильно с одним или обоими входами отрицательными. Версия Майка будет работать быстрее и занимать меньше места в кэше UOP ( xchgна процессорах Intel это 3 мопа, а loopна большинстве процессоров она очень медленная ), но эта версия выигрывает при размере машинного кода.

Сначала я не заметил, что вопрос требует 32-разрядного без знака . Возвращение к xor edx,edxвместо cdqбудет стоить один байт. divимеет такой же размер, как idivи все остальное, может оставаться неизменным ( xchgдля перемещения данных и при inc/loopэтом работы).

Интересно, что для 64-битного размера операнда ( raxи rcx) версии со знаком и без знака имеют одинаковый размер. Подписанная версия нуждается в префиксе REX для cqo(2B), но неподписанная версия все еще может использовать 2B xor edx,edx.

В 64-битном коде inc ecxэто 2B: однобайтовые inc r32и dec r32коды операций были переназначены как префиксы REX. inc/loopне сохраняет размер кода в 64-битном режиме, так что вы тоже можете test/jnz. Работа с 64-битными целыми числами добавляет еще один байт на инструкцию в префиксах REX, за исключением loopили jnz. Остальные могут иметь все нули в младшем 32b (например gcd((2^32), (2^32 + 1))), поэтому мы должны протестировать весь rcx и не можем сохранить байт с помощью test ecx,ecx. Однако более медленный jrcxzinsn составляет всего 2B, и мы можем поместить его в верхнюю часть цикла для обработки ecx=0при входе :

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

Полная работоспособная программа испытаний , включающие в себя , mainчто работает printf("...", gcd(atoi(argv[1]), atoi(argv[2])) ); источник и выход ASM на Godbolt Compiler проводнике , для 32 и 64b версий. Протестировано и работает для 32bit ( -m32), 64bit ( -m64) и x32 ABI ( -mx32) .

Также включены: версия, использующая только повторное вычитание , которая составляет 9B для без знака, даже для режима x86-64, и может принимать один из своих входов в произвольном регистре. Тем не менее, он не может обрабатывать ни один из входов, subравный 0 на входе (он обнаруживает, когда выдает ноль, чего никогда не делает x - 0).

Встроенный источник GNU C для 32-битной версии (скомпилировать с 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;
}

Обычно я пишу целую функцию в asm, но встроенный asm в GNU C кажется лучшим способом включить фрагмент, который может иметь входы / выходы в любых регистрах, которые мы выберем. Как вы можете видеть, встроенный синтаксис GNU C делает asmd уродливым и шумным. Это также очень сложный способ изучения асма .

На самом деле он будет компилироваться и работать в .att_syntax noprefixрежиме, потому что все используемые insns являются либо одиночным / без операнда, либо xchg. Не очень полезное наблюдение.

Гексагония , 17 байт

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

Развернутая:

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

Попробуйте онлайн!

Установка его в сторону длины 3 была на одном дыхании. Срезать эти два байта в конце не было ... Я также не уверен, что это оптимально, но я уверен, что думаю, что это близко.

объяснение

Еще одна реализация евклидова алгоритма.

Программа использует три края памяти, которые я назову A , B и C , с указателем памяти (MP), начинающимся как показано:

Вот схема потока управления:

Поток управления начинается на сером пути с короткого линейного бита для ввода:

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

Обратите внимание, что код теперь оборачивается по краям <в левом углу. Это <действует как ветвь. Если текущий фронт равен нулю (т. Е. Завершается евклидов алгоритм), IP отклоняется влево и выбирает красный путь. В противном случае итерация евклидова алгоритма вычисляется на зеленом пути.

Сначала рассмотрим зеленый путь. Обратите внимание, что >и \все действует как зеркала, которые просто отклоняют указатель инструкции. Также обратите внимание, что поток управления оборачивается по краям три раза, один раз снизу вверх, один раз из правого угла в нижний ряд и, наконец, из нижнего правого угла в левый угол, чтобы повторно проверить условие. Также обратите внимание, что .нет опс.

Это оставляет следующий линейный код для одной итерации:

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

Теперь мы вернулись к тому, с чего начали, за исключением того, что три ребра циклически меняли свои роли (исходный C теперь принимает роль B, а исходный B - роль A ...). По сути, мы перераспределили входные данные Aи Bс Bи A % B, соответственно.

После того, как A % B(по краю C ) равен нулю, то НОД можно найти на кромке B . Опять же >просто отклоняет IP, поэтому на красном пути мы выполняем:

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

32-битный машинный код с прямым порядком байтов x86, 14 байтов

Создано с помощью 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 байт

Кто-то упомянул худший язык для игры в гольф?

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

Создает табличную функцию, которая использует рекурсивный запрос для определения общих делителей. Тогда он возвращает максимум . Теперь использует евклидов алгоритм для определения GCD, полученного из моего ответа здесь .

Пример использования

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)

Желе, 7 байт

ṛß%ðḷṛ?

Рекурсивная реализация евклидова алгоритма. Попробуйте онлайн!

Если бы встроенные модули не были запрещены, g(1 байт, встроенный GCD) достиг бы лучшего результата.

Как это работает

ṛß%ðḷṛ?  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 байтов

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

Пример использования: 45 # 35-> 5.

Евклид, снова.

PS: конечно есть и встроенная gcdтоже.

Python 3, 31

Сохранено 3 байта благодаря Sp3000.

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

MATL , 11 9 байт

Кажется, никто до сих пор не использовал грубую силу, так что вот она.

ts:\a~f0)

Ввод представляет собой массив столбцов с двумя числами (используется в ;качестве разделителя).

Попробуйте онлайн! или проверьте все контрольные примеры .

объяснение

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 байт

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

C, 28 байтов

Довольно простая функция, реализующая алгоритм Евклида. Возможно, можно стать короче, используя альтернативный алгоритм.

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

Если кто-то пишет небольшую главную обертку

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

тогда можно проверить несколько значений:

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

Лабиринт , 18 байт

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

Завершается с ошибкой, но сообщение об ошибке отправляется на STDERR.

Попробуйте онлайн!

Это пока не совсем оптимально, но я не вижу способа сжать цикл ниже 3х3 в этой точке.

объяснение

Это использует евклидов алгоритм.

Во-первых, есть линейный бит для чтения ввода и попадания в основной цикл. Указатель инструкций (IP) начинается в верхнем левом углу и идет на восток.

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

Теперь мы вводим своего рода цикл while-do, который вычисляет евклидов алгоритм. Вершины стеков содержат aиb (поверх неявного бесконечного количества нулей, но они нам не понадобятся). Мы будем представлять стеки из стороны в сторону, растущие навстречу друг другу:

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

Цикл заканчивается один раз a ноль. Итерация цикла работает следующим образом:

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

Вы можете видеть, мы заменили aиb на b%aи aсоответственно.

Наконец, когда b%aноль, IP продолжает двигаться на восток и выполняет:

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

Юлия, 21 15 байт

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

Рекурсивная реализация евклидова алгоритма. Попробуйте онлайн!

Если встроенные модули не были запрещены, gcd (3 байта, встроенный GCD) добились бы лучшего результата.

Как это работает

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 байт

?v%uII/;O@

Попробуй здесь

Это оборачивает куб следующим образом:

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

Использует евклидов метод.

IIДва числа берутся из STDIN и помещают в стек.
/Поток отражается до
%Mod of Top of Stack. Остаток слева на вершине стека.
?Если TOS 0, то продолжить, в противном случае повернуть направо.
vЕсли нет 0, тогда перенаправить вниз и uповернуть направо дважды назад на мод.
/Если 0 обойти куб,
;отбросить TOS отражателя , Oвывести TOS и @завершить

C #, 24 байта

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

Пакет Windows, 76 байт

Рекурсивная функция. Назовите это как GCD a bс именем файла 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 байт

pG1$Zm/

Попробуйте онлайн!

объяснение

Поскольку мы не можем явно использовать встроенную функцию GCD ( Zdв MATL), я использовал тот факт, что наименьшее общее кратное aи bкратное наибольшему общему знаменателю aи bравно произведению aи 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

Ракетка (схема), 44 байта

Реализация Евклида в Ракетке (Схема)

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

Изменить: не видел решение @Numeri лол. Каким-то образом мы получили один и тот же код независимо друг от друга

> <> , 32 байта

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

Принимает два значения из стека и применяет евклидовый алгоритм для создания их GCD.

Вы можете попробовать это здесь !

Чтобы получить лучший ответ в> <>, посмотрите Sok's !

ReRegex , 23 байта

Работает идентично ответу Retina.

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

Попробуйте онлайн!

GML, 57 байт

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

Delphi 7, 148

Ну, я думаю, что нашел новый худший язык для игры в гольф.

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.

Хун, 20 байт

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

-

Хун №2, 39 байт

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

Как ни странно, единственной реализацией в stdlib Хуна для GCD является та, которая используется для ее криптографии RSA, которая также возвращает некоторые другие значения. Я должен обернуть его в функцию, которая занимает толькоd из вывода.

Другая реализация - просто рекурсивное определение GCD по умолчанию.

Python 3,5, 70, 82, 73 байта:

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

В notэтом случае убедитесь, что сумма всех чисел по *argsмодулюi равна нулю.

Кроме того, теперь эта лямбда-функция может принимать столько значений, сколько вы хотите, при условии, что количество значений в >=2отличие от gcdфункции математического модуля. Например, он может принимать значения 2,4,6,8,10и возвращать правильный GCD, равный 2.

Рубин, 23 байта

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

помните, что рубиновые блоки вызываются с помощью g [...] или g.call (...) вместо g (...)

частичные кредиты voidpigeon

Машинный код ARM, 12 байт:

монтаж:

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

В настоящее время не может скомпилировать это, но каждая инструкция в ARM занимает 4 байта. Вероятно, это можно было бы проиграть, используя режим THUMB-2.

TI-Basic, 10 байтов

Prompt A,B:gcd(A,B

Не конкурирует из-за нового правила, запрещающего встроенные функции gcd

17-байтовое решение без gcd(встроенного

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

Не конкурирует из-за нового правила, запрещающего встроенные модули lcm

27-байтовое решение без gcd(или со lcm(встроенным:

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

35 байт рекурсивное решение без gcd(или lcm(встроенных модулей (требуется 2,53 операционной системы MP или выше, должны быть названы prgmG ):

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

Вы передадите аргументы в рекурсивный вариант, как, {A,B}например {1071, 462}:prgmG, в результате 21.

05AB1E , 10 байтов

Код:

EàF¹N%O>iN

Попробуйте онлайн!

Со встроенными модулями:

¿

Объяснение:

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

Попробуйте онлайн! или попробуйте с несколькими номерами .

Oracle SQL 11.2, 104 118 байт

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;

Исправлено для ввода 0

> <> , 12 + 3 = 15 байт

:?!\:}%
;n~/

Ожидает, что входные числа будут присутствовать в стеке, поэтому +3 байта для -vфлага.Попробуйте онлайн!

Еще одна реализация евклидова алгоритма.