Ein Feld in der Mathematik ist eine Menge von Zahlen, auf denen Additions- und Multiplikationsoperationen so definiert sind, dass sie bestimmte Axiome erfüllen (beschrieben in Wikipedia; siehe auch unten).
Ein endliches Feld kann p n -Elemente haben, wobei p
es sich um eine Primzahl und n
eine natürliche Zahl handelt. Nehmen wir in dieser Herausforderung p = 2
und n = 8
und erstellen ein Feld mit 256 Elementen.
Die Elemente des Feldes sollten aufeinanderfolgende ganze Zahlen in einem Bereich liegen, enthält 0
und 1
:
- -128 ... 127
- 0 ... 255
- oder irgendein anderer solcher Bereich
Definieren Sie zwei Funktionen (oder Programme, falls dies einfacher ist) a(x,y)
für abstrakte "Addition" und m(x,y)
für abstrakte "Multiplikation", so dass sie die Feldaxiome erfüllen:
- Konsistenz:
a(x,y)
undm(x,y)
erzeugen dasselbe Ergebnis, wenn sie mit denselben Argumenten aufgerufen werden - Closedness: Das Ergebnis von
a
undm
ist eine ganze Zahl im relevanten Bereich - Assoziativität: für jeden
x
,y
undz
in dem Bereich,a(a(x,y),z)
gleich ista(x,a(y,z))
; das gleiche fürm
- Kommutativität: für jede
x
undy
im Bereicha(x,y)
ist gleicha(y,x)
; das gleiche fürm
- Distributivity: für jeden
x
,y
undz
im Bereich,m(x,a(y,z))
ist gleicha(m(x,y),m(x,z))
- Neutrale Elemente: für alle
x
im Bereicha(0,x)
ist gleichx
undm(1,x)
gleichx
- Negierung: für jede
x
im Bereich, gibt es solche ,y
diea(x,y)
ist0
- Invers: für jede
x≠0
im Bereich gibt es solche ,y
diem(x,y)
ist1
Die Namen a
und m
sind nur Beispiele; Sie können andere Namen oder unbenannte Funktionen verwenden. Die Punktzahl Ihrer Antwort ist die Summe der Byte-Längen für a
und m
.
Wenn Sie eine eingebaute Funktion verwenden, beschreiben Sie bitte auch in Worten, welches Ergebnis sie liefert (z. B. eine Multiplikationstabelle).
quelle
a(2,1) = 3
, die Sie haben könnten,a(2,1) = 5
solange die obigen Axiome erfüllt sind.a
Mit dem üblichen Zusatz, den man zB aus dem Bereich der rationalen Zahlen kennt, muss man nichts anfangen.a=+
m=×
?m=×
Antworten:
Hoon , 22 Bytes
Hoon hat bereits eine Funktion
++ga
, die Galois-Felder für die Verwendung in der AES-Implementierung erstellt. Dies gibt ein Tupel von zwei Funktionen zurück, anstatt zwei Programme zu verwenden.Arbeitet in der Domäne
[0...255]
Testsuite:
Das Posten einer Multiplikationstabelle wäre gigantisch. Hier sind einige zufällige Testfälle:
quelle
Python 2, 11 + 45 = 56 Bytes
Zusatz (11 Bytes):
Multiplikation (45 Byte):
Nimmt Eingabenummern in den Bereich
[0 ... 255]
. Addition ist nur bitweise XOR, Multiplikation ist Multiplikation von Polynomen mit Koeffizienten in GF2 mit russischen Bauern .Und zur Kontrolle:
quelle
m(2,128)
was 27 = 283 - 256 ergibt, also sind Sie richtig und das Polynom istx^8 + x^4 + x^3 + x + 1
.JavaScript (ES6), 10 + 49 = 59 Byte
Domain ist 0 ... 255. Quelle .
quelle
Intel x86-64 + AVX-512 + GFNI, 11 Byte
Benutzt das Neue
GF2P8MULB
Anweisung für Ice Lake-CPUs.quelle
IA-32 Maschinencode, 22 Bytes
"Multiplikation", 18 Bytes:
"Addition", 4 Bytes:
Dies streckt die Regeln ein wenig: Dem "Multiplikations" -Code fehlt der Funktionsexitcode; Es ist darauf angewiesen, dass sich der Zusatzcode unmittelbar danach im Speicher befindet, sodass er "durchfallen" kann. Ich habe es getan, um die Codegröße um 1 Byte zu verringern.
Quellcode (kann
ml
von MS Visual Studio zusammengestellt werden):Der Algorithmus ist der Standard mit dem üblichen Polynom
x^8 + x^4 + x^3 + x + 1
, dargestellt durch die Hexadezimalzahl1b
. Der "Multiplikations" -Code akkumuliert das Ergebnis inedx
. Wenn dies erledigt ist, gelangt es zum Additionscode, in den es verschoben wirdeax
(herkömmliches Register, um den Rückgabewert zu halten); diexor
mitecx
ist ein no-op, da an dieser stelleecx
gelöscht wird.Eine Besonderheit ist die Schleife. Anstatt auf Null zu prüfen
es verwendet die dedizierte
loop
Anweisung. Dieser Befehl verringert jedoch den Schleifen- "Zähler", bevor er mit 0 verglichen wird. Um dies zu kompensieren, erhöht der Code ihn, bevor er denloop
Befehl verwendet.quelle
Mathematica 155 Bytes
Implementierung
Zusatzprüfung:
Mehr:
NB Sollte in der Lage sein,
{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}
anstelle von283
.quelle
±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]
(setzt voraus, dass die Quelle in ISO 8859-1 codiert ist)±
anstelle vonf
undp
anstelle von verwendeto
(natürlich kannst du das beibehalten, ich habe es nur verwendeto
,p
damit ich beide testen kann) und dann ein paar weitere Bytes mit Standard gespeichert syntaktische Zuckertricks.±
genauso arbeiten wief
, aber nichtp
... nicht sicher, wo ich falsch liegeBrainfuck, 28 Zeichen
Glücklicherweise macht Standard Brainfuck alles modulo 256.
Zusatz:
[->+<]
voraus, dass sich die Eingänge an den ersten beiden Stellen des Bandes befinden, setzt den Ausgang auf Position 0Multiplikation: Setzt
[->[->+>+<<]>[-<+>]<<]
voraus, dass sich die Eingänge an den ersten beiden Stellen des Bandes befinden, setzt den Ausgang an Position 3quelle