38
\$\begingroup\$

Your task is to compute the greatest common divisor (GCD) of two given integers in as few bytes of code as possible.

You may write a program or function, taking input and returning output via any of our accepted standard methods (including STDIN/STDOUT, function parameters/return values, command-line arguments, etc.).

Input will be two non-negative integers. You should be able to handle either the full range supported by your language's default integer type, or the range [0,255], whichever is greater. You are guaranteed that at least one of the inputs will be non-zero.

You are not allowed to use built-ins that compute either the GCD or the LCM (least common multiple).

Standard rules apply.

Test Cases

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
\$\endgroup\$
  • 1
    \$\begingroup\$ If we're allowing asm to have inputs in whatever registers are convenient, and the result in whatever reg is convenient, we should definitely be allowing functions, or even code fragments (i.e. just a function body). Making my answer a complete function would add about 4B with a register calling convention like MS's 32bit vectorcall (one xchg eax, one mov, and a ret), or more with a stack calling convention. \$\endgroup\$ – Peter Cordes Apr 8 '16 at 23:05
  • \$\begingroup\$ @PeterCordes Sorry, I should have been more specific. You can totally just write the bear necessary code but if you would be so kind as to include a way to run said code it would be nice. \$\endgroup\$ – Mike Shlanta Apr 9 '16 at 18:59
  • \$\begingroup\$ So count just the gcd code, but provide the surrounding code so people can verify / experiment / improve? BTW, your test-cases with zero as one of the two inputs break our x86 machine code answers. div by zero raises a hardware exception. On Linux, your process gets a SIGFPE. \$\endgroup\$ – Peter Cordes Apr 9 '16 at 19:30
  • \$\begingroup\$ @Martin Doesn't your edit make it impossible to implement this in languages where the default integer type is immutable and only limited by the available memory? \$\endgroup\$ – CodesInChaos Apr 10 '16 at 12:24
  • 2
    \$\begingroup\$ @CodesInChaos Memory and time limitations are usually ignored as long as the algorithm itself can in principle handle all inputs. The rule is just meant to avoid people hardcoding arbitrary limits for loops that artificially limits the algorithm to a smaller range of inputs. I don't quite see how immutability comes into this? \$\endgroup\$ – Martin Ender Apr 10 '16 at 14:10

62 Answers 62

35
\$\begingroup\$

Retina, 16

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

This doesn't use Euclid's algorithm at all - instead it finds the GCD using regex matching groups.

Try it online. - This example calculates GCD(8,12).

Input as 2 space-separated integers. Note that the I/O is in unary. If that is not acceptable, then we can do this:

Retina, 30

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

Try it online.

As @MartinBüttner points out, this falls apart for large numbers (as is generally the case for anything unary). At very a minimum, an input of INT_MAX will require allocation of a 2GB string.

\$\endgroup\$
  • 2
    \$\begingroup\$ I would like to vote for this more \$\endgroup\$ – MickyT Apr 8 '16 at 1:51
  • \$\begingroup\$ Should be fine with the number range now. I've changed the spec (with the OPs permission) to require only the language's natural number range (or [0,255] if that's more). You'll have to support zeroes though, although I think changing your +s to *s should do. And you can significantly shorten the last stage of the long code by reducing it to 1. \$\endgroup\$ – Martin Ender Apr 10 '16 at 9:14
  • 2
    \$\begingroup\$ For future reference, I just found an alternative 16-byte solution that works for an arbitrary number of inputs (including one) so it might be more useful in other contexts: retina.tryitonline.net/… \$\endgroup\$ – Martin Ender Sep 23 '16 at 11:15
  • 1
    \$\begingroup\$ Just noticed that neither your solutions nor the one in my comment above needs the ^, because it's impossible for the match to fail from the starting position. \$\endgroup\$ – Martin Ender Dec 18 '17 at 11:01
28
\$\begingroup\$

i386 (x86-32) machine code, 8 bytes (9B for unsigned)

+1B if we need to handle b = 0 on input.

amd64 (x86-64) machine code, 9 bytes (10B for unsigned, or 14B 13B for 64b integers signed or unsigned)

10 9B for unsigned on amd64 that breaks with either input = 0


Inputs are 32bit non-zero signed integers in eax and ecx. Output 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

This loop structure fails the test-case where ecx = 0. (div causes a #DE hardware execption on divide by zero. (On Linux, the kernel delivers a SIGFPE (floating point exception)). If the loop entry point was right before the inc, we'd avoid the problem. The x86-64 version can handle it for free, see below.

Mike Shlanta's answer was the starting point for this. My loop does the same thing as his, but for signed integers because cdq is one byter shorter than xor edx,edx. And yes, it does work correctly with one or both inputs negative. Mike's version will run faster and take less space in the uop cache (xchg is 3 uops on Intel CPUs, and loop is really slow on most CPUs), but this version wins at machine-code size.

I didn't notice at first that the question required unsigned 32bit. Going back to xor edx,edx instead of cdq would cost one byte. div is the same size as idiv, and everything else can stay the same (xchg for data movement and inc/loop still work.)

Interestingly, for 64bit operand-size (rax and rcx), signed and unsigned versions are the same size. The signed version needs a REX prefix for cqo (2B), but the unsigned version can still use 2B xor edx,edx.

In 64bit code, inc ecx is 2B: the single-byte inc r32 and dec r32 opcodes were repurposed as REX prefixes. inc/loop doesn't save any code-size in 64bit mode, so you might as well test/jnz. Operating on 64bit integers adds another one byte per instruction in REX prefixes, except for loop or jnz. It's possible for the remainder to have all zeros in the low 32b (e.g. gcd((2^32), (2^32 + 1))), so we need to test the whole rcx and can't save a byte with test ecx,ecx. However, the slower jrcxz insn is only 2B, and we can put it at the top of the loop to handle ecx=0 on entry:

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

Full runnable test program including a main that runs printf("...", gcd(atoi(argv[1]), atoi(argv[2])) ); source and asm output on the Godbolt Compiler Explorer, for the 32 and 64b versions. Tested and working for 32bit (-m32), 64bit (-m64), and the x32 ABI (-mx32).

Also included: a version using repeated subtraction only, which is 9B for unsigned, even for x86-64 mode, and can take one of its inputs in an arbitrary register. However, it can't handle either input being 0 on entry (it detect when sub produces a zero, which x - 0 never does).

GNU C inline asm source for the 32bit version (compile with 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;
}

Normally I'd write a whole function in asm, but GNU C inline asm seems to be the best way to include a snippet which can have in/outputs in whatever regs we choose. As you can see, GNU C inline asm syntax makes asm ugly and noisy. It's also a really difficult way to learn asm.

It would actually compile and work in .att_syntax noprefix mode, because all the insns used are either single/no operand or xchg. Not really a useful observation.

\$\endgroup\$
  • 2
    \$\begingroup\$ @MikeShlanta: Thanks. If you like optimizing asm, have a look at some of my answers over on stackoverflow. :) \$\endgroup\$ – Peter Cordes Apr 8 '16 at 3:19
  • 2
    \$\begingroup\$ @MikeShlanta: I found a use for jrcxz after all in the uint64_t version :). Also, didn't notice that you'd specified unsigned, so I included byte counts for that, too. \$\endgroup\$ – Peter Cordes Apr 8 '16 at 22:54
  • \$\begingroup\$ Why couldn't you use jecxz in the 32-bit version to the same effect? \$\endgroup\$ – Cody Gray Aug 13 '16 at 13:32
  • 1
    \$\begingroup\$ @CodyGray: inc/loop is 3 bytes in the 32-bit version, but 4B in the 64-bit version. That means that in the 64-bit version only, it doesn't cost extra bytes to use jrcxz and jmp instead of inc / loop. \$\endgroup\$ – Peter Cordes Aug 13 '16 at 14:43
  • \$\begingroup\$ Can't you point to the middle as entry? \$\endgroup\$ – l4m2 Dec 18 '17 at 20:31
14
\$\begingroup\$

Hexagony, 17 bytes

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

Unfolded:

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

Try it online!

Fitting it into side-length 3 was a breeze. Shaving off those two bytes at the end wasn't... I'm also not convinced it's optimal, but I'm sure I think it's close.

Explanation

Another Euclidean algorithm implementation.

The program uses three memory edges, which I'll call A, B and C, with the memory pointer (MP) starting out as shown:

enter image description here

Here is the control flow diagram:

enter image description here

Control flow starts on the grey path with a short linear bit for input:

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

Note that the code now wraps around the edges to the < in the left corner. This < acts as a branch. If the current edge is zero (i.e. the Euclidean algorithm terminates), the IP is deflected to the left and takes the red path. Otherwise, an iteration of the Euclidean algorithm is computed on the green path.

We'll first consider the green path. Note that > and \ all acts as mirrors which simply deflect the instruction pointer. Also note that control flow wraps around the edges three times, once from the bottom to the top, once from the right corner to the bottom row and finally from the bottom right corner to the left corner to re-check the condition. Also note that . are no-ops.

That leaves the following linear code for a single iteration:

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

Now we're back where we started, except that the three edges have changed their roles cyclically (the original C now takes the role of B and the original B the role of A...). In effect, we've relpaced inputs A and B with B and A % B, respectively.

Once A % B (on edge C) is zero, the GCD can be found on edge B. Again the > just deflects the IP, so on the red path we execute:

}    Move MP to edge B.
!    Print its value as an integer.
@    Terminate the program.
\$\endgroup\$
9
\$\begingroup\$

32-bit little-endian x86 machine code, 14 bytes

Generated using 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
\$\endgroup\$
  • 4
    \$\begingroup\$ I got this down to 8 bytes by using cdq and signed idiv, and one-byte xchg eax, r32 instead of mov. For 32bit code: inc/loop instead of test/jnz (I couldn't see a way to use jecxz, and there's no jecxnz). I posted my final version as a new answer since I think the changes are big enough to justify it. \$\endgroup\$ – Peter Cordes Apr 8 '16 at 2:05
9
\$\begingroup\$

T-SQL, 153 169 bytes

Someone mentioned worst language for golfing?

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

Creates a table valued function that uses a recursive query to work out the common divisors. Then it returns the maximum. Now uses the euclidean algorithm to determine the GCD derived from my answer here.

Example usage

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Jesus that is verbose. \$\endgroup\$ – Cyoce Apr 9 '16 at 7:46
9
\$\begingroup\$

Jelly, 7 bytes

ṛß%ðḷṛ?

Recursive implementation of the Euclidean algorithm. Try it online!

If built-ins weren't forbidden, g (1 byte, built-in GCD) would achieve a better score.

How it works

ṛß%ðḷṛ?  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).
\$\endgroup\$
  • \$\begingroup\$ That almost feels like cheating haha, I may have to specify that answers can't use butlins... \$\endgroup\$ – Mike Shlanta Apr 7 '16 at 18:14
  • 13
    \$\begingroup\$ If you decide to do so, you should do it quickly. It would currently invalidate three of the answers. \$\endgroup\$ – Dennis Apr 7 '16 at 18:16
  • \$\begingroup\$ Notice he specified length is in bytes -- those characters are mostly > 1 byte in UTF8. \$\endgroup\$ – cortices Apr 8 '16 at 3:45
  • 8
    \$\begingroup\$ @cortices Yes, all code golf contests are scored in bytes by default. However, Jelly doesn't use UTF-8, but a custom code page that encodes each of the 256 characters it understands as a single byte. \$\endgroup\$ – Dennis Apr 8 '16 at 4:31
  • \$\begingroup\$ @Dennis ah, clever. \$\endgroup\$ – cortices Apr 9 '16 at 1:06
7
\$\begingroup\$

Haskell, 19 bytes

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

Usage example: 45 # 35-> 5.

Euclid, again.

PS: of course there's a built-in gcd, too.

\$\endgroup\$
  • \$\begingroup\$ you should explain the trick that reverses the input order to avoid the conditional check \$\endgroup\$ – proud haskeller Apr 9 '16 at 1:13
  • \$\begingroup\$ @proudhaskeller: what trick? Everybody uses this algorithm, i.e. stopping on 0 or going on with the modulus. \$\endgroup\$ – nimi Apr 9 '16 at 23:59
  • \$\begingroup\$ Nevrmind, everybody is using the trick \$\endgroup\$ – proud haskeller Apr 10 '16 at 7:10
  • \$\begingroup\$ This, less golfed, is almost exactly what's in Prelude \$\endgroup\$ – Michael Klein Jun 1 '16 at 5:21
6
\$\begingroup\$

Python 3, 31

Saved 3 bytes thanks to Sp3000.

g=lambda a,b:b and g(b,a%b)or a
\$\endgroup\$
  • 3
    \$\begingroup\$ In Python 3.5+: from math import*;gcd \$\endgroup\$ – Sp3000 Apr 7 '16 at 18:11
  • \$\begingroup\$ @Sp3000 Nice, I didn't know they had moved it to math. \$\endgroup\$ – Morgan Thrapp Apr 7 '16 at 18:12
  • 1
    \$\begingroup\$ While you're at it: g=lambda a,b:b and g(b,a%b)or a \$\endgroup\$ – Sp3000 Apr 7 '16 at 18:15
  • \$\begingroup\$ @Sp3000 Thanks! I just finished a recursive solution, but that's even better than what I had. \$\endgroup\$ – Morgan Thrapp Apr 7 '16 at 18:16
  • \$\begingroup\$ Built-ins for GCD and LCM are disallowed, so the 2nd solution wouldn't be valid. \$\endgroup\$ – mbomb007 Oct 4 '16 at 14:38
6
\$\begingroup\$

MATL, 11 9 bytes

No one seems to have used brute force up to now, so here it is.

ts:\a~f0)

Input is a column array with the two numbers (using ; as separator).

Try it online! or verify all test cases.

Explanation

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
\$\endgroup\$
5
\$\begingroup\$

C, 38 bytes

g(x,y){while(x^=y^=x^=y%=x);return y;}
\$\endgroup\$
  • 1
    \$\begingroup\$ You need to include the definition of the function in your bytecount. \$\endgroup\$ – Rɪᴋᴇʀ Dec 29 '17 at 0:24
  • 1
    \$\begingroup\$ @Riker sorry for that, I add the definition and update the count \$\endgroup\$ – How Chen Dec 29 '17 at 0:32
  • \$\begingroup\$ You can save two bytes by naming the function just g instead of gcd. \$\endgroup\$ – Steadybox Dec 29 '17 at 0:37
  • \$\begingroup\$ @Steadybox ok, yes, first time join this community:) \$\endgroup\$ – How Chen Dec 29 '17 at 0:38
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Rɪᴋᴇʀ Dec 29 '17 at 0:38
4
\$\begingroup\$

C, 28 bytes

A rather straightforward function implementing Euclid's algorithm. Perhaps one can get shorter using an alternate algorithm.

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

If one writes a little main wrapper

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

then one can test a few values:

$ ./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
\$\endgroup\$
4
\$\begingroup\$

Labyrinth, 18 bytes

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

Terminates with an error, but the error message goes to STDERR.

Try it online!

This doesn't feel quite optimal yet, but I'm not seeing a way to compress the loop below 3x3 at this point.

Explanation

This uses the Euclidean algorithm.

First, there's a linear bit to read input and get into the main loop. The instruction pointer (IP) starts in the top left corner, going east.

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

We now enter a sort of while-do loop which computes the Euclidean algorithm. The tops of the stacks contain a and b (on top of an implicit infinite amount of zeros, but we won't need those). We'll represent the stacks side to side, growing towards each other:

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

The loop terminates once a is zero. A loop iteration works as follows:

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

You can see, we've replaced a and b with b%a and a respectively.

Finally, once b%a is zero, the IP keeps moving east and executes:

{    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.
\$\endgroup\$
4
\$\begingroup\$

Julia, 21 15 bytes

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

Recursive implementation of the Euclidean algorithm. Try it online!

If built-ins weren't forbidden, gcd (3 bytes, built-in GCD) would achieve a better score.

How it works

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.
\$\endgroup\$
4
\$\begingroup\$

Cubix, 10 12 bytes

?v%uII/;O@

Try it here

This wraps onto the cube as follows:

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

Uses the Euclidean Method.

II Two numbers are grabbed from STDIN and put on the stack
/ Flow reflected up
% Mod the Top of Stack. Remainder left on top of stack
? If TOS 0 then carry on, otherwise turn right
v If not 0 then redirect down and u turn right twice back onto the mod
/ If 0 go around the cube to the reflector
; drop TOS, O output TOS and @ end

\$\endgroup\$
  • \$\begingroup\$ I just wrote up a 12-byte Cubix answer, then started scrolling through the answers to see if I needed to handle both 0,x and x,0... then I came across this. Nice one! \$\endgroup\$ – ETHproductions Oct 4 '16 at 15:05
4
\$\begingroup\$

C#, 24 bytes

x=(a,b)=>b<1?a:x(b,a%b);
\$\endgroup\$
3
\$\begingroup\$

Windows Batch, 76 bytes

Recursive function. Call it like GCD a b with file name gcd.

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

MATL, 7 bytes

pG1$Zm/

Try it Online!

Explanation

Since we can't explicitly use the builtin GCD function (Zd in MATL), I have exploited the fact that the least common multiple of a and b times the greatest common denominator of a and b is equal to the product of a and 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
\$\endgroup\$
  • \$\begingroup\$ You can save one byte with two separate inputs: *1MZm/ \$\endgroup\$ – Luis Mendo Apr 8 '16 at 18:59
3
\$\begingroup\$

Racket (Scheme), 44 bytes

Euclid implementation in Racket (Scheme)

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

Edit: Didn't see @Numeri 's solution lol. Somehow we got the exact same code independently

\$\endgroup\$
  • \$\begingroup\$ Does this work in both? \$\endgroup\$ – NoOneIsHere Jun 2 '16 at 15:42
  • \$\begingroup\$ @NoOneIsHere yeah it works in both \$\endgroup\$ – kronicmage Jun 3 '16 at 12:53
3
\$\begingroup\$

><>, 32 bytes

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

Accepts two values from the stack and apply the euclidian algorithm to produce their GCD.

You can try it here!

For a much better answer in ><>, check out Sok's !

\$\endgroup\$
  • 1
    \$\begingroup\$ I found a new language today :) \$\endgroup\$ – nsane Oct 1 '16 at 20:19
3
\$\begingroup\$

ReRegex, 23 bytes

Works identically to the Retina answer.

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

GML, 57 bytes

a=argument0
b=argument1
while b{t=b;b=a mod b;a=t}return a
\$\endgroup\$
2
\$\begingroup\$

Delphi 7, 148

Well, I think I've found the new worst language for golfing.

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.
\$\endgroup\$
  • \$\begingroup\$ Oh I don't know, parenthetic is pretty poor for golfing \$\endgroup\$ – MickyT Apr 7 '16 at 20:00
2
\$\begingroup\$

Hoon, 20 bytes

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

--

Hoon #2, 39 bytes

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

Oddly, the only implementation in Hoon's stdlib for GCD is the one in use for its RSA crypto, which also returns some other values. I have to wrap it in a function that takes only d from the output.

The other implementation is just the default recursive GCD definition.

\$\endgroup\$
2
\$\begingroup\$

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

The not in this case will make sure the sum all the numbers in *args modulo i are zero.

Also, now this lambda function can take in as many values as you want it to, as long as the amount of values is >=2, unlike the gcd function of the math module. For instance, it can take in the values 2,4,6,8,10 and return the correct GCD of 2.

\$\endgroup\$
  • 1
    \$\begingroup\$ You're under arrest for multichar variable names. (Or function arguments, but whatever) \$\endgroup\$ – CalculatorFeline Apr 8 '16 at 2:32
2
\$\begingroup\$

Ruby, 23 bytes

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

remember that ruby blocks are called with g[...] or g.call(...), instead of g(...)

partial credits to voidpigeon

\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of g.call(a,b) you can use g[a,b]. Instead of proc{|a,b|, you can use ->a,b{. \$\endgroup\$ – afuous Apr 7 '16 at 23:33
  • 1
    \$\begingroup\$ You can also save one byte by using b>0 instead of b<=0 and switching the order of the other operands. \$\endgroup\$ – afuous Apr 7 '16 at 23:35
2
\$\begingroup\$

ARM machine code, 12 bytes:

assembly:

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

Currently can't compile this, but each instruction in ARM takes 4 bytes. Probably it could be golfed down using THUMB-2 mode.

\$\endgroup\$
  • \$\begingroup\$ Nice job man anyone who does this in machine code gets serious props from me. \$\endgroup\$ – Mike Shlanta Apr 8 '16 at 20:15
  • \$\begingroup\$ This appears to be an attempt at Euclid's algo using only subtraction, but I don't think it works. If r0 > r1 then sublt will do nothing (lt predicate is false) and bne will be an infinite loop. I think you need a swap if not lt, so the same loop can do b-=a or a-=b as needed. Or a negate if the sub produced carry (aka borrow). \$\endgroup\$ – Peter Cordes Apr 9 '16 at 18:55
  • \$\begingroup\$ This ARM instruction set guide actually uses a subtraction GCD algorithm as an example for predication. (pg 25). They use cmp r0, r1 / subgt r0, r0, r1 / sublt r1, r1, r0 / bne gcd. That's 16B in ARM instructions, maybe 12 in thumb2 instructions? \$\endgroup\$ – Peter Cordes Apr 9 '16 at 19:21
  • 1
    \$\begingroup\$ On x86, I managed 9 bytes with: sub ecx, eax / jae .no_swap / add ecx,eax / xchg ecx,eax / jne. So instead of a cmp, I just sub, then undo and swap if the sub should have gone the other way. I tested this, and it works. (add won't make jne exit at the wrong time, because it can't produce a zero unless one of the inputs was zero to start with, and we don't support that. Update: we do need to support either input being zero :/) \$\endgroup\$ – Peter Cordes Apr 9 '16 at 19:25
  • \$\begingroup\$ For Thumb2, there's an ite instruction: if-then-else. Should be perfect for cmp / sub one way / sub the other way. \$\endgroup\$ – Peter Cordes Apr 9 '16 at 23:23
2
\$\begingroup\$

TI-Basic, 10 bytes

Prompt A,B:gcd(A,B

Non-competing due to new rule forbidding gcd built-ins


17 byte solution without gcd( built-in

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

Non-competing due to new rule forbidding lcm built-ins


27 byte solution without gcd( or lcm( built-in:

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

35 byte recursive solution without gcd( or lcm( built-ins (requires 2.53 MP operating system or higher, must be named prgmG):

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

You would pass arguments to the recursive variant as {A,B} so for example {1071, 462}:prgmG would yield 21.

\$\endgroup\$
  • \$\begingroup\$ Color me impressed. \$\endgroup\$ – Mike Shlanta Apr 7 '16 at 18:57
  • \$\begingroup\$ You should probably mention that the last one needs to be saved as prgmG. \$\endgroup\$ – a spaghetto Apr 7 '16 at 19:48
2
\$\begingroup\$

05AB1E, 10 bytes

Code:

EàF¹N%O>iN

Try it online!


With built-ins:

¿

Explanation:

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

Try it online! or Try with multiple numbers.

\$\endgroup\$
2
\$\begingroup\$

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;

Fixed for input of 0

\$\endgroup\$
  • \$\begingroup\$ Does not work correctly if one of inputs is zero. \$\endgroup\$ – Egor Skriptunoff Apr 10 '16 at 14:05
  • \$\begingroup\$ This should save you a few SELECT MAX(LEVEL)FROM DUAL WHERE MOD(:1,LEVEL)+MOD(:2,LEVEL)=0 CONNECT BY LEVEL<=:1+:2; \$\endgroup\$ – MickyT Apr 10 '16 at 23:50
2
\$\begingroup\$

><>, 12+3 = 15 bytes

:?!\:}%
;n~/

Expects the input numbers to be present on the stack, so +3 bytes for the -v flag. Try it online!

Another implementation of the Euclidean algorithm.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.