GAP , 368 bajtów
Dla matematyków jest to mnożenie w pierścieniu wielomianowym F_2 [x], identyfikującym wielomiany liczbami naturalnymi, oceniając przy x = 2 jako wielomian nad Z.
Jasne, zróbmy to! (jest to tylko luźna gra w golfa, chodziło raczej o przejście do F 2 [x] i wykonanie obliczeń bardziej niż jakakolwiek próba bycia zwycięzcą)
Oto kod
f:=function(i,j)R:=PolynomialRing(GF(2));x:=IndeterminatesOfPolynomialRing(R);x:=x[1];a:=function(i)local n,r;r:=0*x;while not i=0 do n:=0;while 2^n<=i do n:=n+1;od;n:=n-1;r:=r+x^n;i:=i-2^n;od;return r;end;b:=function(r)local c,i,n;i:=0;n:=0;for c in CoefficientsOfUnivariatePolynomial(r) do if c=Z(2)^0 then n:=n+2^i;fi;i:=i+1;od;return n;end;return b(a(i)*a(j));end;
Oto niepoznany kod z wyjaśnieniem:
xor_multiplication:=function(i,j)
R:=PolynomialRing(GF(2));
x:=IndeterminatesOfPolynomialRing(R);
x:=x[1];
to_ring:=function(i)
local n,r;
r:=0*x;
while not i=0 do
n:=0;
while 2^n<=i do
n:=n+1;
od;
n:=n-1;
r:=r+x^n;
i:=i-2^n;
od;
return r;
end;
to_ints:=function(r)
local c,i,n;
i:=0;n:=0;
for c in CoefficientsOfUnivariatePolynomial(r) do
if c=Z(2)^0 then
n:=n+2^i;
fi;
i:=i+1;
od;
return n;
end;
return to_ints( to_ring(i)*to_ring(j));
end;
Dobra, więc po pierwsze, tworzymy pierścień wielomianowy jednowymiarowy nad polem F 2 i nazywamy go R. Należy pamiętać, że GF(2)jest F 2 w Gap.
R:=PolynomialRing(GF(2));
Następnie przypiszemy zmienną GAP xdo nieokreślonego pierścienia R. Teraz, ilekroć mówię xw GAP, system będzie wiedział, że mówię o nieokreślonym pierścieniu R.
x:=IndeterminatesOfPolynomialRing(R);
x:=x[1];
Następnie mamy dwie funkcje, które są odwrotnymi mapami. Obie mapy są włączone, ale nie zachowują struktury, więc nie mogłem znaleźć lepszego sposobu na ich wdrożenie w GAP. Jest prawie na pewno lepszy sposób, jeśli go znasz, proszę o komentarz!
Pierwsza mapa to_ringpobiera liczbę całkowitą i odwzorowuje ją na odpowiadający jej element pierścieniowy. Robi to poprzez użycie algorytmu konwersji do binarnego, w którym każdy, 1który pojawiłby się w binarnym, jest zastępowany przez x^ngdzie njest odpowiednia moc, którą 2 by wziął, gdyby liczba rzeczywiście była binarna.
to_ring:=function(i)
local n,r;
r:=0*x; # initiate r to the zero element of R
while not i=0 do # this is a modified binary algorithm
n:=0;
while 2^n<=i do
n:=n+1;
od;
n:=n-1;
r:=r+x^n;
i:=i-2^n;
od;
return r;
end;
Następna funkcja odwraca to. to_intsbierze element pierścienia i mapuje go na odpowiednią liczbę całkowitą. Robię to, uzyskując listę współczynników wielomianu i dla każdego niezerowego współczynnika wynik jest zwiększany o 2 ^ n, w taki sam sposób, w jaki konwertujemy wartość binarną na dziesiętną.
to_ints:=function(r)
local c,i,n;
i:=0;n:=0;
for c in CoefficientsOfUnivariatePolynomial(r) do
if c=Z(2)^0 then
# ^-- Right here you'll notice that the Z(2) is basically '1' in GF(2). So Z(2)^0 ~ 1 and Z(2)*0 ~ 0
# effectively, this line checks for nonzero coefficients
n:=n+2^i;
fi;
i:=i+1;
od;
return n;
end;
W ostatnim kroku nazywamy te funkcje. Bierzemy dwa wejścia całkowite, przekształcamy je w elementy w pierścieniu R, a następnie mnożymy te elementy razem i wysyłamy produkt z powrotem do liczb całkowitych.
return to_ints( to_ring(i)*to_ring(j));
PCLMULQDQz rozszerzenia CLMUL. Niestety zostałem wcześniej oceniony za moją wiedzę na temat zestawu instrukcji x86 (Powiązane zPEXT/PDEP), więc zostawię to jako komentarz tutaj.