Tentukan bidang dengan 256 elemen

15

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 pbilangan prima, dan nbilangan alami. Dalam tantangan ini, mari kita ambil p = 2dan n = 8, jadi mari kita membuat bidang dengan 256 elemen.

Elemen-elemen bidang harus bilangan bulat berturut-turut dalam rentang yang berisi 0dan 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)dan m(x,y)menghasilkan hasil yang sama ketika dipanggil dengan argumen yang sama
  • Tertutup: Hasil adan mbilangan bulat dalam rentang yang relevan
  • Asosiatif: untuk apa pun x, ydan zdalam kisaran, a(a(x,y),z)sama dengan a(x,a(y,z)); sama untukm
  • Commutativity: untuk apa pun xdan ydalam kisaran, a(x,y)sama dengan a(y,x); sama untukm
  • Distribusi: untuk apa pun x, ydan zdalam kisaran, m(x,a(y,z))sama dengana(m(x,y),m(x,z))
  • Elemen netral: untuk apa pun xdalam rentang, a(0,x)sama dengan x, dan m(1,x)sama denganx
  • Negasi: untuk setiap xdalam kisaran, terdapat seperti yitu a(x,y)adalah0
  • Inverse: untuk setiap x≠0dalam kisaran, terdapat seperti yitu m(x,y)adalah1

Nama adan mhanya contoh; Anda dapat menggunakan nama lain, atau fungsi yang tidak disebutkan namanya. Skor jawaban Anda adalah jumlah byte-panjang untuk adan m.

Jika Anda menggunakan fungsi bawaan, harap juga jelaskan dengan kata-kata yang dihasilkannya (mis. Berikan tabel perkalian).

anatolyg
sumber
3
@LeakyNun "Selain" hanyalah operasi abstrak di sini yang memenuhi properti di atas. Tidak perlu a(2,1) = 3, Anda bisa memiliki a(2,1) = 5selama aksioma di atas puas. atidak harus melakukan apa pun dengan penambahan yang biasa Anda gunakan misalnya dari bidang bilangan rasional.
Martin Ender
2
Cincin komutatif itu sepele. Bidang ... tidak mudah.
Neil
Apakah ada yang salah a=+ m=×?
Adám
4
@ Adám Ya - 2 tidak akan memiliki terbalik jikam=×
Sp3000
2
Terkait
Peter Taylor

Jawaban:

4

Intel x86-64 + AVX-512 + GFNI, 11 byte

add:
    C5 F0 57 C0     # vxorps     xmm0, xmm1, xmm0
    C3              # ret
mul:
    C4 E2 79 CF C1  # vgf2p8mulb xmm0, xmm0, xmm1
    C3              # ret

Menggunakan GF2P8MULBinstruksi baru pada Ice Lake CPU.

Instruksi mengalikan elemen dalam bidang hingga GF (2 8 ), yang beroperasi pada byte (elemen lapangan) di operan sumber pertama dan byte yang sesuai dalam operan sumber kedua. GF bidang (2 8 ) diwakili dalam representasi polinomial dengan polinomial reduksi x 8 + x 4 + x 3 + x + 1.

nwellnhof
sumber
13

Python 2, 11 + 45 = 56 byte

Tambahan (11 byte):

int.__xor__

Perkalian (45 byte):

m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

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:

a=int.__xor__
m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

for x in range(256):
    assert a(0,x) == a(x,0) == x
    assert m(1,x) == m(x,1) == x

    assert any(a(x,y) == 0 for y in range(256))

    if x != 0:
        assert any(m(x,y) == 1 for y in range(256))

    for y in range(256):
        assert 0 <= a(x,y) < 256
        assert 0 <= m(x,y) < 256
        assert a(x,y) == a(y,x)
        assert m(x,y) == m(y,x)

        for z in range(256):
            assert a(a(x,y),z) == a(x,a(y,z))
            assert m(m(x,y),z) == m(x,m(y,z))
            assert m(x,a(y,z)) == a(m(x,y), m(x,z))
Sp3000
sumber
Salah satu dari kita harus berubah: P
Mego
@Mego Hah, well ... Saya akan mencoba dan melihat apakah saya dapat menemukan pendekatan lain. Mungkin sulit dikalahkan.
Sp3000
1
Polinomial mana yang menjadi dasar?
feersum
1
@ Spice Sekarang saya menyadari bahwa saya dapat dengan mudah menemukan polinomial dengan menjalankan m(2,128)yang menghasilkan 27 = 283 - 256, jadi Anda benar dan polinomialnya adalah x^8 + x^4 + x^3 + x + 1.
feersum
1
@Spice Dalam jawaban Neil dia memberikan halaman Wikipedia sebagai sumber untuk algoritma, jadi mungkin semua orang membacanya. Tapi itu tetap merupakan pilihan yang paling jelas untuk kode golf karena merupakan polinomial terkecil yang tidak dapat direduksi pada tingkat 8 dalam representasi ini.
feersum
6

JavaScript (ES6), 10 + 49 = 59 byte

a=(x,y)=>x^y
m=(x,y,p=0)=>x?m(x>>1,2*y^283*(y>>7),p^y*(x&1)):p

Domain adalah 0 ... 255. Sumber .

Neil
sumber
2
Anda mungkin harus menentukan rentang yang Anda gunakan.
Martin Ender
4

Hoon , 22 byte

[dif pro]:(ga 8 283 3)

Hoon sudah memiliki fungsi ++gayang menciptakan Galois Fields, untuk digunakan dalam implementasi AES. Ini mengembalikan tupel dari dua fungsi, bukannya menggunakan dua program.

Beroperasi di domain [0...255]

Testsuite:

=+  f=(ga 8 283 3)
=+  n=(gulf 0 255)

=+  a=dif:f
=+  m=pro:f

=+  %+  turn  n
    |=  x/@
    ?>  =((a 0 x) x)
    ?>  =((m 1 x) x)
    ~&  outer+x

    %+  turn  n
      |=  y/@
      ?>  =((a x y) (a y x))
      ?>  &((lte 0 (a x y)) (lte (a x y) 255))
      ?>  &((lte 0 (m x y)) (lte (m x y) 255))

      %+  turn  n
        |=  z/@
        ?>  =((a (a x y) z) (a x (a y z)))
        ?>  =((m x (a y z)) (a (m x y) (m x z)))
        ~
"ok"

Posting tabel perkalian akan sangat besar, jadi inilah beberapa testcas acak:

20x148=229
61x189=143
111x239=181
163x36=29
193x40=1
Pengaturan rendering
sumber
1

Kode mesin IA-32, 22 byte

"Multiplikasi", 18 byte:

33 c0 92 d1 e9 73 02 33 d0 d0 e0 73 02 34 1b 41
e2 f1

"Tambahan", 4 byte:

92 33 c1 c3

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 mlMS Visual Studio):

    TITLE   x

PUBLIC @m@8
PUBLIC @a@8

_TEXT   SEGMENT USE32
@m@8    PROC
    xor eax, eax;
    xchg eax, edx;
myloop:
    shr ecx, 1
    jnc sk1
    xor edx, eax
sk1:
    shl al, 1
    jnc sk2
    xor al, 1bh
sk2:
    inc ecx
    loop myloop
@m@8 endp

@a@8 proc
    xchg eax, edx;
    xor eax, ecx
    ret
@a@8    ENDP
_text ENDS
END

Algoritma adalah yang standar, yang melibatkan polinomial biasa x^8 + x^4 + x^3 + x + 1, diwakili oleh bilangan heksadesimal 1b. Kode "multiplikasi" mengakumulasi hasil di edx. Ketika selesai, itu jatuh ke kode tambahan, yang memindahkannya ke eax(register konvensional untuk menyimpan nilai kembali); yang xordengan ecxadalah no-op, karena pada saat itu ecxdihapus.

Salah satu fitur aneh adalah loop. Alih-alih memeriksa nol

cmp ecx, 0
jne myloop

menggunakan loopinstruksi khusus . Tetapi instruksi ini mengurangi loop "counter" sebelum membandingkannya dengan 0. Untuk mengkompensasi ini, kode meningkatkannya sebelum menggunakan loopinstruksi.

anatolyg
sumber
0

Mathematica 155 byte

f[y_]:=Total[x^Reverse@Range[0,Log[2,y]]*RealDigits[y,2][[1]]];o[q_,c_,d_]:=FromDigits[Reverse@Mod[CoefficientList[PolynomialMod[q[f@c,f@d],f@283],x],2],2]

Penerapan

(*
  in: o[Times, 202, 83]    out: 1
  in: o[Plus, 202, 83]     out: 153
*)

periksa tambahan:

(*
  in: BitXor[202, 83]      out: 153
*)

Lebih:

(*
  in: o[Times, #, #2] & @@@ {{20, 148}, {61, 189}, {111, 239}, {163, 36}, {193, 40}}
  out: {229, 143, 181, 29, 1}
*)

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}dari 283.

martin
sumber
Nah, ini 13 byte lebih sedikit: ±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)
Martin Ender
@ MartinEnder tidak yakin bagaimana menerapkan saran Anda
martin
@martin Anda dapat menggunakannya persis seperti sebelumnya, saya baru saja menggunakan ±bukan fdan pbukannya o(tentu saja Anda dapat menyimpannya o, saya hanya menggunakan psehingga saya bisa menguji keduanya), dan kemudian menyimpan beberapa byte lagi dengan standar trik gula sintaksis.
Martin Ender
@ MartinEnder bisa mulai ±bekerja sama f, tetapi tidak p... tidak yakin di mana saya salah
martin
Jika Anda menyalinnya langsung dari komentar, mungkin ada beberapa karakter yang tidak dapat dicetak di mana pun browser Anda menampilkan jeda baris dalam komentar. Hapus karakter di sekitar posisi itu setelah menyalin dan ketik ulang. Jika itu tidak berhasil, saya tidak yakin di mana masalahnya ..
Martin Ender
-1

Brainfuck, 28 karakter

Untungnya, Brainfuck standar melakukan semuanya modulo 256.

Tambahan [->+<]:, mengasumsikan bahwa input berada pada dua posisi pertama dari rekaman, menempatkan output pada posisi 0

Perkalian:, [->[->+>+<<]>[-<+>]<<]mengasumsikan bahwa input berada pada dua posisi pertama dari rekaman, menempatkan output pada posisi 3

ymbirtt
sumber