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 kode-golf 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
code-golf
math
arithmetic
number-theory
Mike Shlanta
sumber
sumber
SIGFPE
.Jawaban:
Retina , 16
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
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.
sumber
+
s Anda*
harus dilakukan. Dan Anda dapat secara signifikan mempersingkat tahap terakhir dari kode panjang dengan menguranginya menjadi1
.^
, karena pertandingan tidak mungkin gagal dari posisi awal.kode mesin i386 (x86-32), 8 byte (9B untuk unsigned)
+1 1 jika kita perlu menangani
b = 0
input.kode mesin amd64 (x86-64), 9 byte (10B untuk unsigned, atau
14B13B untuk 64b bilangan bulat ditandatangani atau tidak ditandatangani)109B untuk unsigned pada amd64 yang rusak dengan input = 0Input adalah bilangan bulat bertanda 32-bit bukan-nol di
eax
danecx
. Output dalameax
.Struktur loop ini gagal dalam test case
ecx = 0
. (div
menyebabkan#DE
eksekusi perangkat keras divide by zero. (Di Linux, kernel memberikan aSIGFPE
(floating point exception)). Jika titik entri loop tepat sebeluminc
, 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
cdq
satu byter lebih pendek darixor 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 (xchg
adalah 3 uops pada CPU Intel, danloop
sangat 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,edx
bukancdq
akan biaya satu byte.div
adalah ukuran yang sama denganidiv
, dan yang lainnya bisa tetap sama (xchg
untuk pergerakan data daninc/loop
masih berfungsi.)Menariknya, untuk ukuran operan 64bit (
rax
danrcx
), versi yang ditandatangani dan tidak ditandatangani memiliki ukuran yang sama. Versi yang ditandatangani membutuhkan awalan REX untukcqo
(2B), tetapi versi yang tidak ditandatangani masih dapat menggunakan 2Bxor edx,edx
.Dalam kode 64bit,
inc ecx
adalah 2B: byte-tunggalinc r32
dandec r32
opcodes repurposed sebagai awalan REX.inc/loop
tidak menyimpan ukuran kode dalam mode 64bit, jadi Anda mungkin jugatest/jnz
. Beroperasi pada bilangan bulat 64bit menambahkan satu byte per instruksi dalam awalan REX, kecuali untukloop
ataujnz
. Mungkin untuk sisanya memiliki semua nol di 32b rendah (misalnyagcd((2^32), (2^32 + 1))
), jadi kita perlu menguji seluruh rcx dan tidak dapat menyimpan byte dengantest ecx,ecx
. Namun,jrcxz
insn yang lebih lambat hanya 2B, dan kita bisa meletakkannya di atas loop untuk menanganiecx=0
entri :Program uji runnable penuh termasuk
main
yang menjalankanprintf("...", 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
sub
menghasilkan nol, yang x - 0 tidak pernah lakukan).GNU C inline asm source untuk versi 32bit (kompilasi dengan
gcc -m32 -masm=intel
)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 noprefix
mode, karena semua insns yang digunakan adalah operan tunggal / tidak ada atauxchg
. Bukan observasi yang bermanfaat.sumber
jrcxz
setelah semua dalam versi uint64_t :). Juga, tidak melihat bahwa Anda telah menentukan tidak ditandatangani, jadi saya juga memasukkan jumlah byte untuk itu.jecxz
dalam versi 32-bit untuk efek yang sama?inc/loop
adalah 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 digunakanjrcxz
danjmp
bukaninc / loop
.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:
Berikut adalah diagram alir kendali:
Aliran kontrol dimulai pada jalur abu-abu dengan bit linear pendek untuk input:
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:
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
A
danB
denganB
danA % 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:sumber
Kode mesin x86 32 bit bit-endian, 14 byte
Dihasilkan menggunakan
nasm -f bin
d231 f3f7 d889 d389 db85 f475
sumber
cdq
dan menandatanganiidiv
, danxchg eax, r32
bukannya satu bytemov
. Untuk kode 32bit:inc/loop
alih-alihtest/jnz
(saya tidak bisa melihat cara untuk menggunakanjecxz
, dan tidak adajecxnz
). Saya memposting versi final saya sebagai jawaban baru karena saya pikir perubahannya cukup besar untuk membenarkannya.T-SQL, 153
169byteSeseorang menyebutkan bahasa terburuk untuk bermain golf?
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
sumber
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
sumber
Haskell, 19 byte
Contoh penggunaan:
45 # 35
->5
.Euclid, lagi.
PS: tentu saja ada built-in
gcd
juga.sumber
0
atau melanjutkan modulus.Prelude
Python 3, 31
Disimpan 3 byte berkat Sp3000.
sumber
from math import*;gcd
g=lambda a,b:b and g(b,a%b)or a
MATL ,
119 byteTidak ada yang tampaknya telah menggunakan kekerasan sampai sekarang, jadi ini dia.
Input adalah array kolom dengan dua angka (menggunakan
;
sebagai pemisah).Cobalah online! atau verifikasi semua kasus uji .
Penjelasan
sumber
C, 38 byte
sumber
g
alih-alihgcd
.C, 28 byte
Fungsi yang agak mudah menerapkan algoritma Euclid. Mungkin seseorang bisa menjadi lebih pendek menggunakan algoritma alternatif.
Jika seseorang menulis bungkus utama kecil
maka seseorang dapat menguji beberapa nilai:
sumber
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.
Kita sekarang memasukkan semacam while-do loop yang menghitung algoritma Euclidean. Bagian atas tumpukan berisi
a
danb
(di atas jumlah nol tak terbatas yang tersirat, tetapi kita tidak akan membutuhkannya). Kami akan mewakili tumpukan sisi ke sisi, tumbuh satu sama lain:Loop berakhir sekali
a
adalah nol. Iterasi loop berfungsi sebagai berikut:Anda dapat melihat, kami telah mengganti
a
danb
dengan masingb%a
-a
masing.Akhirnya, sekali
b%a
nol, IP terus bergerak ke timur dan menjalankan:sumber
Julia,
2115 byteImplementasi 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
sumber
Cubix , 10
12byteCoba di sini
Ini membungkus ke kubus sebagai berikut:
Menggunakan Metode Euclidean.
II
Dua 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 kananv
Jika tidak 0 kemudian mengarahkan ke bawah danu
berbelok ke kanan dua kali kembali ke mod/
Jika 0 go sekitar kubus dengan reflektor;
TOS drop,O
keluaran KL dan@
akhirsumber
0,x
danx,0
... kemudian saya menemukan ini. Yang bagus!C #, 24 byte
sumber
Windows Batch, 76 byte
Fungsi rekursif. Sebut saja suka
GCD a b
dengan nama filegcd
.sumber
MATL, 7 byte
Cobalah secara Online!
Penjelasan
Karena kita tidak dapat secara eksplisit menggunakan fungsi GCD
Zd
bawaan ( dalam MATL), saya telah mengeksploitasi fakta bahwa kelipatan paling umuma
danb
kali penyebut umum terbesara
danb
sama dengan produk daria
danb
.sumber
*1MZm/
Racket (Skema), 44 byte
Implementasi Euclid dalam Racket (Skema)
Sunting: Tidak melihat solusi @Numeri lol. Entah bagaimana kami mendapat kode yang sama persis secara mandiri
sumber
> <> , 32 byte
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 !
sumber
ReRegex , 23 byte
Bekerja identik dengan jawaban Retina.
Cobalah online!
sumber
GML, 57 byte
sumber
Delphi 7, 148
Yah, saya pikir saya telah menemukan bahasa terburuk baru untuk bermain golf.
sumber
Hoon, 20 byte
-
Hoon # 2, 39 byte
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
d
dari output.Implementasi lainnya hanyalah definisi GCD rekursif default.
sumber
Python 3.5,
708273 byte:Dalam
not
hal ini akan memastikan jumlah semua angka dalam*args
moduloi
adalah nol.Juga, sekarang fungsi lambda ini dapat mengambil nilai sebanyak yang Anda inginkan, asalkan jumlah nilainya
>=2
, tidak sepertigcd
fungsi modul matematika. Misalnya, dapat mengambil nilai2,4,6,8,10
dan mengembalikan GCD 2 yang benar.sumber
Ruby, 23 byte
ingat bahwa blok ruby disebut dengan g [...] atau g.call (...), bukan g (...)
kredit parsial untuk voidpigeon
sumber
g.call(a,b)
bisa Anda gunakang[a,b]
. Alih-alihproc{|a,b|
, Anda bisa menggunakan->a,b{
.b>0
alih-alihb<=0
dan mengalihkan urutan operan lainnya.Kode mesin ARM, 12 byte:
majelis:
Saat ini tidak dapat mengkompilasi ini, tetapi setiap instruksi dalam ARM membutuhkan 4 byte. Mungkin itu bisa diturunkan menggunakan mode THUMB-2.
sumber
r0 > r1
kemudiansublt
akan melakukan apa-apa (lt
predikat salah) danbne
akan menjadi loop tak terbatas. Saya pikir Anda perlu swap jika tidaklt
, sehingga loop yang sama dapat dilakukanb-=a
ataua-=b
sesuai kebutuhan. Atau meniadakan jika sub diproduksi membawa (alias meminjam).cmp r0, r1
/subgt r0, r0, r1
/sublt r1, r1, r0
/bne gcd
. Itu 16B dalam instruksi ARM, mungkin 12 dalam instruksi thumb2?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. (add
tidak akanjne
keluar 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: /)ite
instruksi: if-then-else. Harus sempurna untuk cmp / sub cara satu / sub cara lain.TI-Basic, 10 byte
Non-bersaing karena aturan baru yang melarang built-in gcd
Solusi 17 byte tanpa
gcd(
built-inNon-bersaing karena aturan baru yang melarang built-in lcm
Solusi 27 byte tanpa
gcd(
ataulcm(
built-in:Solusi rekursif 35 byte tanpa
gcd(
ataulcm(
built-in (membutuhkan sistem operasi 2,53 MP atau lebih tinggi, harus dinamaiprgmG
):Anda akan meneruskan argumen ke varian rekursif
{A,B}
sehingga misalnya{1071, 462}:prgmG
akan menghasilkan21
.sumber
prgmG
.05AB1E , 10 byte
Kode:
Cobalah online!
Dengan built-in:
Penjelasan:
Cobalah online! atau Coba dengan beberapa nomor .
sumber
Oracle SQL 11.2,
104118 byteDiperbaiki untuk input 0
sumber
SELECT MAX(LEVEL)FROM DUAL WHERE MOD(:1,LEVEL)+MOD(:2,LEVEL)=0 CONNECT BY LEVEL<=:1+:2;
> <> , 12 + 3 = 15 byte
Mengharapkan angka-angka input untuk hadir pada tumpukan, jadi +3 byte untuk
-v
bendera. Cobalah online!Implementasi lain dari algoritma Euclidean.
sumber