Pembagi Umum Terbesar

40

Tugas Anda adalah untuk menghitung pembagi umum terbesar (GCD) dari dua bilangan bulat yang diberikan dalam kode byte sesedikit mungkin.

Anda dapat menulis program atau fungsi, mengambil input dan mengembalikan output melalui salah satu metode standar kami yang diterima (termasuk STDIN / STDOUT, parameter fungsi / nilai balik, argumen baris perintah, dll.).

Input akan berupa dua bilangan bulat non-negatif. Anda harus dapat menangani rentang penuh yang didukung oleh tipe integer default bahasa Anda, atau rentang [0,255], mana yang lebih besar. Anda dijamin bahwa paling tidak salah satu dari input tidak nol.

Anda tidak diperbolehkan menggunakan built-in yang menghitung GCD atau LCM (multiple paling umum).

Aturan standar berlaku.

Uji Kasus

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
Mike Shlanta
sumber
1
Jika kita membiarkan ASM untuk memiliki input dalam register apa pun yang nyaman, dan hasil dalam reg apa pun nyaman, kita pasti harus mengizinkan fungsi, atau bahkan fragmen kode (yaitu hanya badan fungsi). Menjadikan jawaban saya fungsi yang lengkap akan menambahkan sekitar 4B dengan konvensi pemanggilan register seperti panggilan vektor 32bit MS (satu xchg eax, satu mov, dan ret), atau lebih dengan konvensi pemanggilan tumpukan.
Peter Cordes
@PeterCordes Maaf, saya seharusnya lebih spesifik. Anda benar-benar dapat hanya menulis kode yang diperlukan tetapi jika Anda akan berbaik hati untuk memasukkan cara untuk menjalankan kode itu akan lebih baik.
Mike Shlanta
Jadi hitung saja kode gcd, tetapi berikan kode sekitarnya sehingga orang dapat memverifikasi / bereksperimen / meningkatkan? BTW, kotak uji Anda dengan nol sebagai salah satu dari dua input memecahkan jawaban kode mesin x86 kami. div dengan nol memunculkan eksepsi perangkat keras. Di Linux, proses Anda mendapat a SIGFPE.
Peter Cordes
3
@CodesInChaos Batasan memori dan waktu biasanya diabaikan selama algoritma itu sendiri pada prinsipnya dapat menangani semua input. Aturan ini hanya dimaksudkan untuk menghindari orang-orang melakukan hardcoding batas acak untuk loop yang secara artifisial membatasi algoritma ke kisaran input yang lebih kecil. Saya tidak begitu mengerti bagaimana ketidakberubahan ini terjadi?
Martin Ender
1
gcd (0, n) adalah kesalahan bukan n
RosLuP

Jawaban:

37

Retina , 16

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

Ini tidak menggunakan algoritma Euclid sama sekali - melainkan menemukan GCD menggunakan kelompok pencocokan regex.

Cobalah online. - Contoh ini menghitung GCD (8,12).

Input sebagai 2 bilangan bulat yang dipisahkan spasi. Perhatikan bahwa I / O adalah unary. Jika itu tidak dapat diterima, maka kita dapat melakukan ini:

Retina, 30

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

Cobalah online.

Seperti yang ditunjukkan oleh @ MartinBüttner, ini berantakan untuk sejumlah besar (seperti umumnya untuk apa pun yang unary). Paling tidak, input INT_MAX akan membutuhkan alokasi string 2GB.

Trauma Digital
sumber
2
Saya ingin memilih ini lebih banyak
MickyT
Seharusnya tidak masalah dengan kisaran angka sekarang. Saya telah mengubah spec (dengan izin OPs) untuk hanya memerlukan rentang nomor alami bahasa (atau [0,255] jika itu lebih). Anda harus mendukung nol, meskipun saya pikir mengubah +s Anda *harus dilakukan. Dan Anda dapat secara signifikan mempersingkat tahap terakhir dari kode panjang dengan menguranginya menjadi 1.
Martin Ender
2
Untuk referensi di masa mendatang, saya baru saja menemukan solusi alternatif 16-byte yang berfungsi untuk sejumlah input yang arbitrer (termasuk satu) sehingga mungkin lebih berguna dalam konteks lain: retina.tryitonline.net/…
Martin Ender
1
Hanya perhatikan bahwa solusi Anda maupun yang di komentar saya di atas tidak memerlukannya ^, karena pertandingan tidak mungkin gagal dari posisi awal.
Martin Ender
28

kode mesin i386 (x86-32), 8 byte (9B untuk unsigned)

+1 1 jika kita perlu menangani b = 0input.

kode mesin amd64 (x86-64), 9 byte (10B untuk unsigned, atau 14B 13B untuk 64b bilangan bulat ditandatangani atau tidak ditandatangani)

10 9B untuk unsigned pada amd64 yang rusak dengan input = 0


Input adalah bilangan bulat bertanda 32-bit bukan-nol di eaxdan ecx. Output dalam 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

Struktur loop ini gagal dalam test case ecx = 0. ( divmenyebabkan #DEeksekusi perangkat keras divide by zero. (Di Linux, kernel memberikan a SIGFPE(floating point exception)). Jika titik entri loop tepat sebelum inc, kita akan menghindari masalah. Versi x86-64 dapat menanganinya gratis, lihat di bawah.

Jawaban Mike Shlanta adalah titik awal untuk ini . Loop saya melakukan hal yang sama seperti miliknya, tetapi untuk bilangan bulat yang ditandatangani karena cdqsatu byter lebih pendek dari xor edx,edx. Dan ya, itu berfungsi dengan benar dengan satu atau kedua input negatif. Versi Mike akan berjalan lebih cepat dan mengambil lebih sedikit ruang di cache uop ( xchgadalah 3 uops pada CPU Intel, dan loopsangat lambat pada kebanyakan CPU ), tetapi versi ini menang pada ukuran kode mesin.

Saya tidak memperhatikan pada awalnya bahwa pertanyaan itu membutuhkan 32bit tanpa tanda tangan . Kembali ke xor edx,edxbukan cdqakan biaya satu byte. divadalah ukuran yang sama dengan idiv, dan yang lainnya bisa tetap sama ( xchguntuk pergerakan data dan inc/loopmasih berfungsi.)

Menariknya, untuk ukuran operan 64bit ( raxdan rcx), versi yang ditandatangani dan tidak ditandatangani memiliki ukuran yang sama. Versi yang ditandatangani membutuhkan awalan REX untuk cqo(2B), tetapi versi yang tidak ditandatangani masih dapat menggunakan 2B xor edx,edx.

Dalam kode 64bit, inc ecxadalah 2B: byte-tunggal inc r32dan dec r32opcodes repurposed sebagai awalan REX. inc/looptidak menyimpan ukuran kode dalam mode 64bit, jadi Anda mungkin juga test/jnz. Beroperasi pada bilangan bulat 64bit menambahkan satu byte per instruksi dalam awalan REX, kecuali untuk loopatau jnz. Mungkin untuk sisanya memiliki semua nol di 32b rendah (misalnya gcd((2^32), (2^32 + 1))), jadi kita perlu menguji seluruh rcx dan tidak dapat menyimpan byte dengan test ecx,ecx. Namun, jrcxzinsn yang lebih lambat hanya 2B, dan kita bisa meletakkannya di atas loop untuk menangani ecx=0entri :

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

Program uji runnable penuh termasuk mainyang menjalankan printf("...", gcd(atoi(argv[1]), atoi(argv[2])) ); sumber dan asm output pada Godbolt Compiler Explorer , untuk versi 32 dan 64b. Diuji dan berfungsi untuk 32bit ( -m32), 64bit ( -m64), dan ABI x32 ( -mx32) .

Juga termasuk: versi yang menggunakan pengurangan yang diulang saja , yaitu 9B untuk yang tidak ditandatangani, bahkan untuk mode x86-64, dan dapat mengambil salah satu inputnya dalam register sewenang-wenang. Namun, ia tidak dapat menangani input menjadi 0 pada entri (ia mendeteksi kapan submenghasilkan nol, yang x - 0 tidak pernah lakukan).

GNU C inline asm source untuk versi 32bit (kompilasi dengan 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;
}

Biasanya saya akan menulis seluruh fungsi dalam asm, tetapi GNU C inline asm tampaknya menjadi cara terbaik untuk memasukkan potongan yang dapat memiliki / output dalam regs apa pun yang kita pilih. Seperti yang Anda lihat, GNU C inline asm syntax membuat asm jelek dan berisik. Ini juga merupakan cara yang sangat sulit untuk belajar asm .

Ini sebenarnya akan mengkompilasi dan bekerja dalam .att_syntax noprefixmode, karena semua insns yang digunakan adalah operan tunggal / tidak ada atau xchg. Bukan observasi yang bermanfaat.

Peter Cordes
sumber
2
@MikeShlanta: Terima kasih. Jika Anda suka mengoptimalkan asm, lihat beberapa jawaban saya di atas stackoverflow. :)
Peter Cordes
2
@ MikeShlanta: Saya menemukan gunanya jrcxzsetelah semua dalam versi uint64_t :). Juga, tidak melihat bahwa Anda telah menentukan tidak ditandatangani, jadi saya juga memasukkan jumlah byte untuk itu.
Peter Cordes
Mengapa Anda tidak bisa menggunakan jecxzdalam versi 32-bit untuk efek yang sama?
Cody Grey
1
@CodyGray: inc/loopadalah 3 byte dalam versi 32-bit, tetapi 4B dalam versi 64-bit. Itu berarti bahwa dalam versi 64-bit saja, itu tidak memerlukan biaya byte tambahan untuk digunakan jrcxzdan jmpbukan inc / loop.
Peter Cordes
Tidak bisakah Anda menunjuk ke tengah sebagai entri?
14m2
14

Hexagony , 17 byte

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

Dibuka:

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

Cobalah online!

Memasukkannya ke dalam sisi-panjang 3 sangat mudah. Mencukur dua byte pada akhirnya tidak ... Saya juga tidak yakin itu optimal, tapi saya yakin saya pikir sudah dekat.

Penjelasan

Implementasi algoritma Euclidean lainnya.

Program ini menggunakan tiga tepi memori, yang saya sebut A , B dan C , dengan penunjuk memori (MP) dimulai seperti yang ditunjukkan:

masukkan deskripsi gambar di sini

Berikut adalah diagram alir kendali:

masukkan deskripsi gambar di sini

Aliran kontrol dimulai pada jalur abu-abu dengan bit linear pendek untuk input:

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

Perhatikan bahwa kode sekarang membungkus di sekitar tepi ke <di sudut kiri. Ini <bertindak sebagai cabang. Jika tepi saat ini adalah nol (yaitu algoritma Euclidean berakhir), IP dibelokkan ke kiri dan mengambil jalur merah. Jika tidak, iterasi dari algoritma Euclidean dihitung pada jalur hijau.

Kami pertama-tama akan mempertimbangkan jalur hijau. Perhatikan itu >dan \semua bertindak sebagai mirror yang hanya membelokkan pointer instruksi. Perhatikan juga bahwa aliran kontrol membungkus di sekitar tepi tiga kali, sekali dari bawah ke atas, sekali dari sudut kanan ke baris bawah dan akhirnya dari sudut kanan bawah ke sudut kiri untuk memeriksa kembali kondisi. Perhatikan juga bahwa .tidak ada op.

Itu meninggalkan kode linier berikut untuk satu iterasi:

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

Sekarang kita kembali ke tempat kita mulai, kecuali bahwa ketiga sisi telah mengubah peran mereka secara siklis ( C asli sekarang mengambil peran B dan B asli peran A ...). Akibatnya, kami telah merelokasi input Adan Bdengan Bdan A % B, masing-masing.

Setelah A % B(di tepi C ) adalah nol, GCD dapat ditemukan di tepi B . Sekali lagi >hanya membelokkan IP, jadi pada jalur merah kita jalankan:

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

Kode mesin x86 32 bit bit-endian, 14 byte

Dihasilkan menggunakan 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
Mike Shlanta
sumber
4
Saya mendapatkan ini hingga 8 byte dengan menggunakan cdqdan menandatangani idiv, dan xchg eax, r32bukannya satu byte mov. Untuk kode 32bit: inc/loopalih-alih test/jnz(saya tidak bisa melihat cara untuk menggunakan jecxz, dan tidak ada jecxnz). Saya memposting versi final saya sebagai jawaban baru karena saya pikir perubahannya cukup besar untuk membenarkannya.
Peter Cordes
9

T-SQL, 153 169 byte

Seseorang menyebutkan bahasa terburuk untuk bermain 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

Membuat fungsi bernilai tabel yang menggunakan kueri rekursif untuk mencari pembagi umum. Kemudian mengembalikan maksimum . Sekarang menggunakan algoritma euclidean untuk menentukan GCD yang berasal dari jawaban saya di sini .

Contoh penggunaan

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
sumber
1
Yesus yang verbose.
Cyoce
9

Jelly, 7 byte

ṛß%ðḷṛ?

Implementasi rekursif dari algoritma Euclidean. Cobalah online!

Jika built-in tidak dilarang, g(1 byte, GCD built-in) akan mencapai skor yang lebih baik.

Bagaimana itu bekerja

ṛß%ðḷṛ?  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).
Dennis
sumber
Itu hampir terasa seperti menipu haha, saya mungkin harus menentukan bahwa jawaban tidak dapat menggunakan butlins ...
Mike Shlanta
13
Jika Anda memutuskan untuk melakukannya, Anda harus melakukannya dengan cepat. Saat ini akan membatalkan tiga jawaban.
Dennis
Perhatikan bahwa panjang yang ditentukan adalah dalam byte - karakter tersebut sebagian besar> 1 byte di UTF8.
cortices
8
@cortices Ya, semua kontes kode golf dinilai dalam byte secara default. Namun, Jelly tidak menggunakan UTF-8, tetapi halaman kode khusus yang mengkodekan masing-masing 256 karakter yang dimengerti sebagai satu byte.
Dennis
@Dennis ah, pintar.
cortices
7

Haskell, 19 byte

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

Contoh penggunaan: 45 # 35-> 5.

Euclid, lagi.

PS: tentu saja ada built-in gcdjuga.

nimi
sumber
Anda harus menjelaskan trik yang membalik urutan input untuk menghindari pemeriksaan bersyarat
bangga haskeller
@proudhaskeller: trik apa? Semua orang menggunakan algoritma ini, yaitu berhenti 0atau melanjutkan modulus.
nimi
Nevrmind, semua orang menggunakan trik
haskeller bangga
Ini, kurang golf, hampir persis apa yang ada diPrelude
Michael Klein
6

Python 3, 31

Disimpan 3 byte berkat Sp3000.

g=lambda a,b:b and g(b,a%b)or a
Morgan Thrapp
sumber
3
Dalam Python 3.5+:from math import*;gcd
Sp3000
@ Sp3000 Bagus, saya tidak tahu mereka telah pindah ke matematika.
Morgan Thrapp
1
Sementara Anda melakukannya:g=lambda a,b:b and g(b,a%b)or a
Sp3000
@ Sp3000 Terima kasih! Saya baru saja menyelesaikan solusi rekursif, tetapi itu bahkan lebih baik daripada yang saya miliki.
Morgan Thrapp
Built-in untuk GCD dan LCM tidak diizinkan, sehingga solusi kedua tidak akan valid.
mbomb007
6

MATL , 11 9 byte

Tidak ada yang tampaknya telah menggunakan kekerasan sampai sekarang, jadi ini dia.

ts:\a~f0)

Input adalah array kolom dengan dua angka (menggunakan ;sebagai pemisah).

Cobalah online! atau verifikasi semua kasus uji .

Penjelasan

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
Luis Mendo
sumber
5

C, 38 byte

g(x,y){while(x^=y^=x^=y%=x);return y;}
Bagaimana Chen
sumber
1
Anda harus memasukkan definisi fungsi dalam bytecount Anda.
Rɪᴋᴇʀ
1
@Riker minta maaf untuk itu, saya tambahkan definisi dan perbarui hitungan
How Chen
Anda dapat menyimpan dua byte dengan memberi nama fungsi galih-alih gcd.
Steadybox
@Steadybox ok, ya, pertama kali bergabung dengan komunitas ini :)
How Chen
1
Selamat datang di PPCG!
Rɪᴋᴇʀ
4

C, 28 byte

Fungsi yang agak mudah menerapkan algoritma Euclid. Mungkin seseorang bisa menjadi lebih pendek menggunakan algoritma alternatif.

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

Jika seseorang menulis bungkus utama kecil

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

maka seseorang dapat menguji beberapa nilai:

$ ./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
CL-
sumber
4

Labirin , 18 byte

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

Hentikan dengan kesalahan, tetapi pesan kesalahan pergi ke STDERR.

Cobalah online!

Ini belum terasa cukup optimal, tapi saya belum melihat cara untuk menekan loop di bawah 3x3 pada saat ini.

Penjelasan

Ini menggunakan algoritma Euclidean.

Pertama, ada bit linear untuk membaca input dan masuk ke loop utama. Pointer instruksi (IP) dimulai di sudut kiri atas, menuju ke timur.

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

Kita sekarang memasukkan semacam while-do loop yang menghitung algoritma Euclidean. Bagian atas tumpukan berisi adan b(di atas jumlah nol tak terbatas yang tersirat, tetapi kita tidak akan membutuhkannya). Kami akan mewakili tumpukan sisi ke sisi, tumbuh satu sama lain:

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

Loop berakhir sekali aadalah nol. Iterasi loop berfungsi sebagai berikut:

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

Anda dapat melihat, kami telah mengganti adan bdengan masing b%a- amasing.

Akhirnya, sekali b%anol, IP terus bergerak ke timur dan menjalankan:

{    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.
Martin Ender
sumber
4

Julia, 21 15 byte

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

Implementasi rekursif dari algoritma Euclidean. Cobalah online!

Jika built-in tidak dilarang, gcd(3 byte, GCD built-in) akan mencapai skor yang lebih baik.

Bagaimana itu bekerja

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.
Dennis
sumber
4

Cubix , 10 12 byte

?v%uII/;O@

Coba di sini

Ini membungkus ke kubus sebagai berikut:

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

Menggunakan Metode Euclidean.

IIDua angka diambil dari STDIN dan diletakkan di tumpukan
/Flow yang memantulkan
%Mod the Top of Stack. Sisanya ditinggalkan di atas tumpukan
?Jika TOS 0 kemudian melanjutkan, jika belok kanan
vJika tidak 0 kemudian mengarahkan ke bawah dan uberbelok ke kanan dua kali kembali ke mod
/Jika 0 go sekitar kubus dengan reflektor
;TOS drop, Okeluaran KL dan @akhir

MickyT
sumber
Saya baru saja menulis jawaban Cubix 12-byte, kemudian mulai mencari-cari jawaban untuk melihat apakah saya perlu menangani keduanya 0,xdan x,0... kemudian saya menemukan ini. Yang bagus!
ETHproduk
4

C #, 24 byte

x=(a,b)=>b<1?a:x(b,a%b);
Morgan Thrapp
sumber
3

Windows Batch, 76 byte

Fungsi rekursif. Sebut saja suka GCD a bdengan nama file gcd.

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

MATL, 7 byte

pG1$Zm/

Cobalah secara Online!

Penjelasan

Karena kita tidak dapat secara eksplisit menggunakan fungsi GCD Zdbawaan ( dalam MATL), saya telah mengeksploitasi fakta bahwa kelipatan paling umum adan bkali penyebut umum terbesar adan bsama dengan produk dari adan 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
sumber
Anda dapat menyimpan satu byte dengan dua input terpisah:*1MZm/
Luis Mendo
3

Racket (Skema), 44 byte

Implementasi Euclid dalam Racket (Skema)

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

Sunting: Tidak melihat solusi @Numeri lol. Entah bagaimana kami mendapat kode yang sama persis secara mandiri

Kronismage
sumber
Apakah ini bekerja di keduanya?
NoOneIsHere
@NoOneIsHere ya itu bekerja di keduanya
kronicmage
3

> <> , 32 byte

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

Menerima dua nilai dari tumpukan dan menerapkan algoritma euclidian untuk menghasilkan GCD mereka.

Anda bisa mencobanya di sini !

Untuk jawaban yang jauh lebih baik di> <>, lihat Sok !

Harun
sumber
1
Saya menemukan bahasa baru hari ini :)
nsane
3

ReRegex , 23 byte

Bekerja identik dengan jawaban Retina.

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

Cobalah online!

ATaco
sumber
2

GML, 57 byte

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

Delphi 7, 148

Yah, saya pikir saya telah menemukan bahasa terburuk baru untuk bermain 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.
Morgan Thrapp
sumber
Oh saya tidak tahu, tanda kurung cukup buruk untuk bermain golf
MickyT
2

Hoon, 20 byte

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

-

Hoon # 2, 39 byte

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

Anehnya, satu-satunya implementasi di stdlib Hoon untuk GCD adalah implementasi yang digunakan untuk kripto RSA, yang juga mengembalikan beberapa nilai lainnya. Saya harus membungkusnya dalam fungsi yang hanya mengambil ddari output.

Implementasi lainnya hanyalah definisi GCD rekursif default.

Pengaturan rendering
sumber
2

Python 3.5, 70 82 73 byte:

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

Dalam nothal ini akan memastikan jumlah semua angka dalam *argsmodulo iadalah nol.

Juga, sekarang fungsi lambda ini dapat mengambil nilai sebanyak yang Anda inginkan, asalkan jumlah nilainya >=2, tidak seperti gcdfungsi modul matematika. Misalnya, dapat mengambil nilai 2,4,6,8,10dan mengembalikan GCD 2 yang benar.

R. Kap
sumber
1
Anda ditahan karena nama variabel multichar. (Atau argumen fungsi, tapi apa pun)
CalculatorFeline
2

Ruby, 23 byte

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

ingat bahwa blok ruby ​​disebut dengan g [...] atau g.call (...), bukan g (...)

kredit parsial untuk voidpigeon

Luis Masuelli
sumber
2
Alih-alih g.call(a,b)bisa Anda gunakan g[a,b]. Alih-alih proc{|a,b|, Anda bisa menggunakan ->a,b{.
Berlangsung
1
Anda juga dapat menyimpan satu byte dengan menggunakan b>0alih-alih b<=0dan mengalihkan urutan operan lainnya.
Afiliasi
2

Kode mesin ARM, 12 byte:

majelis:

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

Saat ini tidak dapat mengkompilasi ini, tetapi setiap instruksi dalam ARM membutuhkan 4 byte. Mungkin itu bisa diturunkan menggunakan mode THUMB-2.

styrofoam terbang
sumber
Pekerja yang baik, siapa pun yang melakukan ini dalam kode mesin mendapat alat peraga serius dari saya.
Mike Shlanta
Ini tampaknya merupakan upaya pada Euclid's algo hanya menggunakan pengurangan , tapi saya pikir itu tidak berhasil. Jika r0 > r1kemudian subltakan melakukan apa-apa ( ltpredikat salah) dan bneakan menjadi loop tak terbatas. Saya pikir Anda perlu swap jika tidak lt, sehingga loop yang sama dapat dilakukan b-=aatau a-=bsesuai kebutuhan. Atau meniadakan jika sub diproduksi membawa (alias meminjam).
Peter Cordes
Panduan set instruksi ARM ini sebenarnya menggunakan algoritme pengurangan GCD sebagai contoh untuk predikasi. (hal 25). Mereka menggunakan cmp r0, r1/ subgt r0, r0, r1/ sublt r1, r1, r0/ bne gcd. Itu 16B dalam instruksi ARM, mungkin 12 dalam instruksi thumb2?
Peter Cordes
1
Pada x86, saya mengatur 9 byte dengan: sub ecx, eax/ jae .no_swap/ add ecx,eax/ xchg ecx,eax/ jne. Jadi alih-alih cmp, saya hanya sub, lalu undo dan tukar jika sub seharusnya sebaliknya. Saya menguji ini, dan itu berhasil. ( addtidak akan jnekeluar pada waktu yang salah, karena tidak dapat menghasilkan nol kecuali salah satu input nol untuk memulai, dan kami tidak mendukungnya. Pembaruan: kami perlu mendukung salah satu input menjadi nol: /)
Peter Cordes
Untuk Thumb2, ada iteinstruksi: if-then-else. Harus sempurna untuk cmp / sub cara satu / sub cara lain.
Peter Cordes
2

TI-Basic, 10 byte

Prompt A,B:gcd(A,B

Non-bersaing karena aturan baru yang melarang built-in gcd


Solusi 17 byte tanpa gcd(built-in

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

Non-bersaing karena aturan baru yang melarang built-in lcm


Solusi 27 byte tanpa gcd(atau lcm(built-in:

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

Solusi rekursif 35 byte tanpa gcd(atau lcm(built-in (membutuhkan sistem operasi 2,53 MP atau lebih tinggi, harus dinamai prgmG ):

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

Anda akan meneruskan argumen ke varian rekursif {A,B}sehingga misalnya {1071, 462}:prgmGakan menghasilkan 21.

Timtech
sumber
Warna saya terkesan.
Mike Shlanta
Anda mungkin harus menyebutkan bahwa yang terakhir harus disimpan sebagai prgmG.
spaghetto
2

05AB1E , 10 byte

Kode:

EàF¹N%O>iN

Cobalah online!


Dengan built-in:

¿

Penjelasan:

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

Cobalah online! atau Coba dengan beberapa nomor .

Adnan
sumber
2

Oracle SQL 11.2, 104 118 byte

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;

Diperbaiki untuk input 0

Jeto
sumber
Tidak berfungsi dengan benar jika salah satu input bernilai nol.
Egor Skriptunoff
Ini akan menghemat sedikitSELECT MAX(LEVEL)FROM DUAL WHERE MOD(:1,LEVEL)+MOD(:2,LEVEL)=0 CONNECT BY LEVEL<=:1+:2;
MickyT
2

> <> , 12 + 3 = 15 byte

:?!\:}%
;n~/

Mengharapkan angka-angka input untuk hadir pada tumpukan, jadi +3 byte untuk -vbendera. Cobalah online!

Implementasi lain dari algoritma Euclidean.

Sok
sumber