Наибольший общий делитель

40

Ваша задача - вычислить наибольший общий делитель (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
Майк Шланта
источник
1
Если мы разрешаем asm иметь входные данные в любых удобных регистрах, а результат - в любом удобном регистре, мы определенно должны разрешать функции или даже фрагменты кода (т. Е. Просто тело функции). Сделав мой ответ полной функцией, можно было бы добавить около 4B с соглашением о вызовах регистра, таким как 32-битный векторный вызов MS (один xchg eax, один mov и ret), или более с соглашением о вызове стека.
Питер Кордес
@PeterCordes Извините, я должен был быть более конкретным. Вы можете просто написать необходимый код, но если вы будете так любезны, включите способ запуска указанного кода, было бы неплохо.
Майк Шланта
Поэтому считайте только код gcd, но предоставьте окружающий код, чтобы люди могли проверить / поэкспериментировать / улучшить? Кстати, ваши тесты с нулем в качестве одного из двух входов нарушают наши ответы машинного кода x86. div by zero вызывает аппаратное исключение. В Linux ваш процесс получает SIGFPE.
Питер Кордес
3
@CodesInChaos Ограничения памяти и времени обычно игнорируются, поскольку сам алгоритм в принципе может обрабатывать все входные данные. Правило предназначено только для того, чтобы люди не жестко кодировали произвольные ограничения для циклов, что искусственно ограничивает алгоритм меньшим диапазоном входных данных. Я не совсем понимаю, как неизменность входит в это?
Мартин Эндер
1
gcd (0, n) - это ошибка, а не n
RosLuP

Ответы:

37

Сетчатка , 16

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

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

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

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

Сетчатка, 30

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

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

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

Цифровая травма
источник
2
Я хотел бы проголосовать за это больше
MickyT
Теперь должно быть в порядке с диапазоном номеров. Я изменил спецификацию (с разрешением OP), чтобы требовать только диапазон натуральных чисел языка (или [0,255], если это больше). Вы должны будете поддерживать нули, хотя я думаю, что замена ваших +s на *s должна подойти. И вы можете значительно сократить последнюю стадию длинного кода, уменьшив его до 1.
Мартин Эндер
2
Для дальнейшего использования я только что нашел альтернативное 16-байтовое решение, которое работает для произвольного числа входов (включая один), поэтому оно может быть более полезным в других контекстах: retina.tryitonline.net/…
Martin Ender
1
Просто заметил, что ни ваши решения, ни приведенные в моем комментарии выше не нуждаются в этом ^, потому что матч не может потерпеть неудачу со стартовой позиции.
Мартин Эндер
28

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. Не очень полезное наблюдение.

Питер Кордес
источник
2
@MikeShlanta: Спасибо. Если вам нравится оптимизировать asm, взгляните на некоторые мои ответы на stackoverflow. :)
Питер Кордес
2
@MikeShlanta: Я все-таки нашел применение для jrcxzверсии uint64_t :). Кроме того, я не заметил, что вы указали unsigned, поэтому я также включил подсчет байтов.
Питер Кордес
Почему вы не могли использовать jecxzв 32-битной версии с тем же эффектом?
Коди Грэй,
1
@CodyGray: inc/loop3 байта в 32-битной версии, но 4B в 64-битной версии. Это означает, что только в 64-битной версии он не требует дополнительных байтов jrcxzи jmpвместо inc / loop.
Питер Кордес
Не можете ли вы указать на середину в качестве входа?
l4m2
14

Гексагония , 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.
Мартин Эндер
источник
9

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
Майк Шланта
источник
4
Я получил это до 8 байтов, используя cdqи подписанный idiv, и один байт xchg eax, r32вместо mov. Для 32-битного кода: inc/loopвместо test/jnz(я не мог найти способ использовать jecxz, и нет jecxnz). Я опубликовал свою окончательную версию в качестве нового ответа, так как считаю, что изменения достаточно велики, чтобы оправдать это.
Питер Кордес
9

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)
MickyT
источник
1
Иисус это многословно.
Cyoce
9

Желе, 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).
Деннис
источник
Это почти похоже на мошенничество, ха-ха, возможно, мне придется уточнить, что в ответах нельзя использовать буллины ...
Майк Шланта
13
Если вы решили сделать это, вы должны сделать это быстро. В настоящее время это сделает недействительными три ответа.
Деннис
Обратите внимание, что он указал длину в байтах - эти символы в основном> 1 байт в UTF8.
кортикальная
8
@cortices Да, все соревнования по коду в коде по умолчанию оцениваются в байтах. Тем не менее, Jelly не использует UTF-8, а представляет собой пользовательскую кодовую страницу, которая кодирует каждый из 256 символов, которые он понимает как один байт.
Деннис
@ Денис, умница.
корчи
7

Haskell, 19 байтов

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

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

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

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

Ними
источник
Вы должны объяснить трюк, который изменяет порядок ввода, чтобы избежать условной проверки
гордый haskeller
@proudhaskeller: какой трюк? Каждый использует этот алгоритм, то есть останавливается 0или продолжает с модулем.
Ними
Nevrmind, все используют трюк
гордый haskeller
Это, менее гольф, почти точно то, что вPrelude
Майкл Кляйн
6

Python 3, 31

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

g=lambda a,b:b and g(b,a%b)or a
Морган Трепп
источник
3
В Python 3.5+:from math import*;gcd
Sp3000
@ Sp3000 Хорошо, я не знал, что они перешли на математику.
Морган Трепп
1
Пока вы на нем:g=lambda a,b:b and g(b,a%b)or a
Sp3000
@ Sp3000 Спасибо! Я только что закончил рекурсивное решение, но это даже лучше, чем у меня было.
Морган Трепп
Встроенные модули для GCD и LCM запрещены, поэтому 2-е решение будет недействительным.
mbomb007
6

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
Луис Мендо
источник
5

C, 38 байт

g(x,y){while(x^=y^=x^=y%=x);return y;}
Как Чен
источник
1
Вы должны включить определение функции в свой счет.
Rɪᴋᴇʀ
1
@Riker извините за это, я добавляю определение и обновляю счет
как Чен
Вы можете сохранить два байта, назвав функцию просто gвместо gcd.
Steadybox
@Steadybox хорошо, да, впервые присоединиться к этому сообществу :)
Как Чен
1
Добро пожаловать в PPCG!
Rɪᴋᴇʀ
4

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
CL-
источник
4

Лабиринт , 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.
Мартин Эндер
источник
4

Юлия, 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.
Деннис
источник
4

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 и @завершить

MickyT
источник
Я просто написал 12-байтовый ответ Cubix, затем начал просматривать ответы, чтобы узнать, нужно ли мне обрабатывать оба, 0,xи x,0... потом я наткнулся на это. Хороший!
ETHproductions
4

C #, 24 байта

x=(a,b)=>b<1?a:x(b,a%b);
Морган Трепп
источник
3

Пакет 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%
Timtech
источник
3

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
Suever
источник
Вы можете сохранить один байт с двумя отдельными входами:*1MZm/
Луис Мендо
3

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

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

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

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

kronicmage
источник
Это работает в обоих?
NoOneIsHere
@NoOneIsHere да, это работает в обоих
kronicmage
3

> <> , 32 байта

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

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

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

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

Аарон
источник
1
Я нашел новый язык сегодня :)
nsane
2

GML, 57 байт

a=argument0
b=argument1
while b{t=b;b=a mod b;a=t}return a
Timtech
источник
2

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.
Морган Трепп
источник
О, я не знаю, в скобках довольно плохо для игры в гольф
MickyT
2

Хун, 20 байт

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

-

Хун №2, 39 байт

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

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

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

RenderSettings
источник
2

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.

Р. Кап
источник
1
Вы арестованы за многозначные имена переменных. (Или аргументы функции, но неважно)
CalculatorFeline
2

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

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

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

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

Луис Масуэлли
источник
2
Вместо g.call(a,b)тебя можно использовать g[a,b]. Вместо proc{|a,b|, вы можете использовать ->a,b{.
afuous
1
Вы также можете сохранить один байт, используя b>0вместо b<=0и переключая порядок других операндов.
afuous
2

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

монтаж:

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

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

пенополистирол летать
источник
Хорошая работа, любой, кто делает это в машинном коде, получает от меня серьезные реквизиты.
Майк Шланта
Похоже, что это попытка алгоритма Евклида с использованием только вычитания , но я не думаю, что это работает. Если r0 > r1затем subltничего не будет делать ( ltпредикат ложен) и bneбудет бесконечный цикл. Я думаю, что вам нужен обмен, если нет lt, поэтому тот же цикл можно сделать b-=aили по a-=bмере необходимости. Или отрицание, если субпроизводитель нести (иначе заимствовать).
Питер Кордес
Это руководство по набору команд ARM фактически использует алгоритм GCD вычитания в качестве примера предикации. (стр. 25). Они используют cmp r0, r1/ subgt r0, r0, r1/ sublt r1, r1, r0/ bne gcd. Это 16B в инструкциях ARM, может быть 12 в инструкциях thumb2?
Питер Кордес
1
На x86 я управлял 9 байтами с: sub ecx, eax/ jae .no_swap/ add ecx,eax/ xchg ecx,eax/ jne. Таким образом, вместо cmp, я просто саб, затем отменить и заменить, если саб должен был пойти другим путем. Я проверил это, и это работает. ( addне выполнит jneвыход в неправильное время, потому что он не может произвести ноль, если только один из входов не был нулевым для начала, и мы не поддерживаем это. Обновление: нам нужно, чтобы любой вход был нулевым: /)
Питер Кордес
Для Thumb2 есть iteинструкция: если-то-еще. Должно быть идеально подходит для cmp / sub в одну сторону / sub в другую сторону.
Питер Кордес
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.

Timtech
источник
Цвет меня впечатлил.
Майк Шланта
Вы, вероятно, должны упомянуть, что последний должен быть сохранен как prgmG.
спагетто
2

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.

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

Аднан
источник
2

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

школа для водителей
источник
Не работает правильно, если один из входов равен нулю.
Егор Скриптунов
Это должно сэкономить вам немногоSELECT MAX(LEVEL)FROM DUAL WHERE MOD(:1,LEVEL)+MOD(:2,LEVEL)=0 CONNECT BY LEVEL<=:1+:2;
MickyT
2

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

:?!\:}%
;n~/

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

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

Sok
источник