Sebuah bidang dalam matematika adalah seperangkat angka, dengan operasi penjumlahan dan perkalian didefinisikan di atasnya, sehingga mereka memenuhi aksioma tertentu (yang dijelaskan dalam Wikipedia; lihat juga di bawah).
Bidang terbatas dapat memiliki elemen p n , di mana p
bilangan prima, dan n
bilangan alami. Dalam tantangan ini, mari kita ambil p = 2
dan n = 8
, jadi mari kita membuat bidang dengan 256 elemen.
Elemen-elemen bidang harus bilangan bulat berturut-turut dalam rentang yang berisi 0
dan 1
:
- -128 ... 127
- 0 ... 255
- atau rentang lain seperti itu
Tentukan dua fungsi (atau program, jika itu lebih mudah), a(x,y)
untuk abstrak "penjumlahan", dan m(x,y)
untuk "perkalian" abstrak, sedemikian rupa sehingga memenuhi bidang aksioma:
- Konsistensi:
a(x,y)
danm(x,y)
menghasilkan hasil yang sama ketika dipanggil dengan argumen yang sama - Tertutup: Hasil
a
danm
bilangan bulat dalam rentang yang relevan - Asosiatif: untuk apa pun
x
,y
danz
dalam kisaran,a(a(x,y),z)
sama dengana(x,a(y,z))
; sama untukm
- Commutativity: untuk apa pun
x
dany
dalam kisaran,a(x,y)
sama dengana(y,x)
; sama untukm
- Distribusi: untuk apa pun
x
,y
danz
dalam kisaran,m(x,a(y,z))
sama dengana(m(x,y),m(x,z))
- Elemen netral: untuk apa pun
x
dalam rentang,a(0,x)
sama denganx
, danm(1,x)
sama denganx
- Negasi: untuk setiap
x
dalam kisaran, terdapat sepertiy
itua(x,y)
adalah0
- Inverse: untuk setiap
x≠0
dalam kisaran, terdapat sepertiy
itum(x,y)
adalah1
Nama a
dan m
hanya contoh; Anda dapat menggunakan nama lain, atau fungsi yang tidak disebutkan namanya. Skor jawaban Anda adalah jumlah byte-panjang untuk a
dan m
.
Jika Anda menggunakan fungsi bawaan, harap juga jelaskan dengan kata-kata yang dihasilkannya (mis. Berikan tabel perkalian).
sumber
a(2,1) = 3
, Anda bisa memilikia(2,1) = 5
selama aksioma di atas puas.a
tidak harus melakukan apa pun dengan penambahan yang biasa Anda gunakan misalnya dari bidang bilangan rasional.a=+
m=×
?m=×
Jawaban:
Intel x86-64 + AVX-512 + GFNI, 11 byte
Menggunakan
GF2P8MULB
instruksi baru pada Ice Lake CPU.sumber
Python 2, 11 + 45 = 56 byte
Tambahan (11 byte):
Perkalian (45 byte):
Membawa nomor input dalam kisaran
[0 ... 255]
. Penambahan hanya bitor XOR, perkalian adalah perkalian polinomial dengan koefisien dalam GF2 dengan petani Rusia .Dan untuk memeriksa:
sumber
m(2,128)
yang menghasilkan 27 = 283 - 256, jadi Anda benar dan polinomialnya adalahx^8 + x^4 + x^3 + x + 1
.JavaScript (ES6), 10 + 49 = 59 byte
Domain adalah 0 ... 255. Sumber .
sumber
Hoon , 22 byte
Hoon sudah memiliki fungsi
++ga
yang menciptakan Galois Fields, untuk digunakan dalam implementasi AES. Ini mengembalikan tupel dari dua fungsi, bukannya menggunakan dua program.Beroperasi di domain
[0...255]
Testsuite:
Posting tabel perkalian akan sangat besar, jadi inilah beberapa testcas acak:
sumber
Kode mesin IA-32, 22 byte
"Multiplikasi", 18 byte:
"Tambahan", 4 byte:
Ini membentang aturan sedikit: kode "multiplikasi" tidak memiliki kode keluar fungsi; itu bergantung pada "tambahan" kode yang ada di memori setelahnya, sehingga bisa "gagal". Saya melakukannya untuk mengurangi ukuran kode sebesar 1 byte.
Kode sumber (dapat dirakit oleh
ml
MS Visual Studio):Algoritma adalah yang standar, yang melibatkan polinomial biasa
x^8 + x^4 + x^3 + x + 1
, diwakili oleh bilangan heksadesimal1b
. Kode "multiplikasi" mengakumulasi hasil diedx
. Ketika selesai, itu jatuh ke kode tambahan, yang memindahkannya keeax
(register konvensional untuk menyimpan nilai kembali); yangxor
denganecx
adalah no-op, karena pada saat ituecx
dihapus.Salah satu fitur aneh adalah loop. Alih-alih memeriksa nol
menggunakan
loop
instruksi khusus . Tetapi instruksi ini mengurangi loop "counter" sebelum membandingkannya dengan 0. Untuk mengkompensasi ini, kode meningkatkannya sebelum menggunakanloop
instruksi.sumber
Mathematica 155 byte
Penerapan
periksa tambahan:
Lebih:
NB Harus dapat menggunakan salah satu
{283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375, 379, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 499, 501, 505}
dari283
.sumber
±y_:=Total[#&@@y~RealDigits~2x^Reverse@Range[0,2~Log~y]];p[q_,c_,d_]:=Fold[#+##&,Reverse@CoefficientList[q[±c,±d]~PolynomialMod~±283,x]~Mod~2]
(mengasumsikan bahwa sumbernya dikodekan dalam ISO 8859-1)±
bukanf
danp
bukannyao
(tentu saja Anda dapat menyimpannyao
, saya hanya menggunakanp
sehingga saya bisa menguji keduanya), dan kemudian menyimpan beberapa byte lagi dengan standar trik gula sintaksis.±
bekerja samaf
, tetapi tidakp
... tidak yakin di mana saya salahBrainfuck, 28 karakter
Untungnya, Brainfuck standar melakukan semuanya modulo 256.
Tambahan
[->+<]
:, mengasumsikan bahwa input berada pada dua posisi pertama dari rekaman, menempatkan output pada posisi 0Perkalian:,
[->[->+>+<<]>[-<+>]<<]
mengasumsikan bahwa input berada pada dua posisi pertama dari rekaman, menempatkan output pada posisi 3sumber