Un campo en matemáticas es un conjunto de números, con operaciones de suma y multiplicación definidas en él, de modo que satisfacen ciertos axiomas (descritos en Wikipedia; ver también a continuación).
Un campo finito puede tener p n elementos, donde p
es un número primo y n
es un número natural. En este desafío, tomemos p = 2
y n = 8
, entonces, hagamos un campo con 256 elementos.
Los elementos del campo deben ser enteros consecutivos en un rango que contenga 0
y 1
:
- -128 ... 127
- 0 ... 255
- o cualquier otro rango
Defina dos funciones (o programas, si eso es más fácil), a(x,y)
para la "suma" m(x,y)
abstracta y para la "multiplicación" abstracta, de modo que satisfagan los axiomas del campo:
- Consistencia:
a(x,y)
ym(x,y)
produce el mismo resultado cuando se llama con los mismos argumentos - Cerrado: el resultado de
a
ym
es un número entero en el rango relevante - Asociatividad: para cualquier
x
,y
yz
en el rango,a(a(x,y),z)
es igual aa(x,a(y,z))
; lo mismo param
- Conmutatividad: para cualquiera
x
yy
en el rango,a(x,y)
es igual aa(y,x)
; lo mismo param
- Distributividad: para cualquier
x
,y
yz
en el rango,m(x,a(y,z))
es igual aa(m(x,y),m(x,z))
- Elementos neutros: para cualquiera
x
en el rango,a(0,x)
es igual ax
, ym(1,x)
es igual ax
- Negación: para cualquiera
x
en el rango, existe taly
quea(x,y)
es0
- Inversa: para cualquiera
x≠0
en el rango, existe taly
quem(x,y)
es1
Los nombres a
y m
son solo ejemplos; puede usar otros nombres o funciones sin nombre. La puntuación de su respuesta es la suma de las longitudes de bytes para a
y m
.
Si usa una función incorporada, describa también en palabras el resultado que produce (por ejemplo, proporcione una tabla de multiplicación).
fuente
a(2,1) = 3
,a(2,1) = 5
siempre y cuando se cumplan los axiomas anteriores.a
no tiene que hacer nada con la adición habitual a la que está acostumbrado, por ejemplo, desde el campo de los números racionales.a=+
m=×
?m=×
Respuestas:
Intel x86-64 + AVX-512 + GFNI, 11 bytes
Utiliza la nueva
GF2P8MULB
instrucción en las CPU de Ice Lake.fuente
Python 2, 11 + 45 = 56 bytes
Adición (11 bytes):
Multiplicación (45 bytes):
Toma los números de entrada en el rango
[0 ... 255]
. La suma es simplemente XOR bit a bit, la multiplicación es la multiplicación de polinomios con coeficientes en GF2 con campesinos rusos .Y para verificar:
fuente
m(2,128)
que resulta en 27 = 283 - 256, por lo que está correcto y el polinomio esx^8 + x^4 + x^3 + x + 1
.JavaScript (ES6), 10 + 49 = 59 bytes
El dominio es 0 ... 255. Fuente .
fuente
Hoon , 22 bytes
Hoon ya tiene una función
++ga
que crea Galois Fields, para usar en la implementación de AES. Esto devuelve una tupla de dos funciones, en lugar de usar dos programas.Opera en el dominio
[0...255]
Banco de pruebas:
Publicar una tabla de multiplicar sería gigantesco, así que aquí hay algunos casos de prueba al azar:
fuente
Código de máquina IA-32, 22 bytes
"Multiplicación", 18 bytes:
"Adición", 4 bytes:
Esto estira las reglas un poco: el código de "multiplicación" carece de código de salida de función; se basa en el código de "adición" que está en la memoria inmediatamente después, por lo que puede "caerse". Lo hice para disminuir el tamaño del código en 1 byte.
Código fuente (puede ser ensamblado por
ml
MS Visual Studio):El algoritmo es el estándar, involucrando el polinomio usual
x^8 + x^4 + x^3 + x + 1
, representado por el número hexadecimal1b
. El código de "multiplicación" acumula el resultado enedx
. Cuando se hace, pasa al código de adición, que lo mueve aeax
(registro convencional para mantener el valor de retorno); elxor
withecx
es un no-op, porque en ese puntoecx
se borra.Una característica peculiar es el bucle. En lugar de verificar cero
Utiliza la
loop
instrucción dedicada . Pero esta instrucción disminuye el "contador" del bucle antes de compararlo con 0. Para compensar esto, el código lo aumenta antes de usar laloop
instrucción.fuente
Mathematica 155 bytes
Implementación
verificación de adición:
Más:
NB Debe poder usar cualquiera de
{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}
en lugar de283
.fuente
±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]
(se supone que la fuente está codificada en ISO 8859-1)±
lugar def
y enp
lugar deo
(por supuesto, puedes guardarlo comoo
, solo lo usép
para poder probarlos a ambos), y luego guardé algunos bytes más con el estándar trucos de azúcar sintácticos.±
a trabajar igual quef
, pero nop
... no estoy seguro de dónde me estoy equivocandoBrainfuck, 28 personajes
Afortunadamente, Brainfuck estándar hace todo el módulo 256.
Adición:
[->+<]
supone que las entradas están en las dos primeras posiciones de la cinta, coloca la salida en la posición 0Multiplicación:
[->[->+>+<<]>[-<+>]<<]
supone que las entradas están en las dos primeras posiciones de la cinta, coloca la salida en la posición 3fuente