Każdy, kto jest umiarkowanie nastawiony na optymalizację kodu niskiego poziomu, wie o zagrożeniach związanych z rozgałęzianiem, niezależnie od tego, czy są one implementowane jako instrukcje if, pętle lub instrukcje select, możliwość błędnego przewidywania gałęzi jest straszną rzeczą marnującą zegar.

Proste problemy można rozwiązać znacznie lepiej za pomocą prostej arytmetyki, więc zróbmy to.

W przypadku następujących problemów wszystkie zmienne są 32-bitowymi liczbami całkowitymi bez znaku, a jedynym dozwolonym kodem są instrukcje z prostym zestawem obejmujące tylko następujące operatory:

+ addition
- subtraction
* multiplication
/ integer division, rounds down, division by 0 not allowed
% modulo
& binary and
| binary or
^ binary exclusive or
>> bitshift right
<< bitshift left

Logic operators, return 1 if the expression is true and 0 if it is false.
== equal
!= not equal
< less than
<= less than or equal
> greater than
>= greater than or equal

Set operator
=

Każda linia musi składać się z identyfikatora zmiennej, po którym następuje operator zbioru, a po nim wyrażenie.

Wyrażenie może nie zawierać dodatkowych operatorów zestawów, ale może zawierać identyfikatory zmiennych, liczby literalne i nawiasy.

Wynik golfa liczy tylko liczbę operatorów.

Przykład:

myvar = ( ( ( foo + 5 ) * bar ) % 7 ) == 3

Ma wynik 5 operatorów.

Rozwiązanie może obejmować tyle zmiennych, ile autor uzna za stosowne.
Zmienne, które nie zostały ustawione, mają wartość 0.
Przepełnienie i niedomiar jest dozwolone, wszystkie liczby ujemne niedopełniony, tak 3 - 5jest 4294967294, nawet jako część większego rachunku.

Zadanie 1: maks

Dwie wartości, Ai Bistnieją w zakresie, sprawiają, że RESULTzmienna zawiera największą z tych wartości po zakończeniu programu.

Zadanie 2: Mediana

Trzy wartości, A, Bi Cistnieją w zakresie sprawiają, że RESULTzmienna zawiera medianę tych wartości, gdy kończy się program.

Zadanie 3: Pierwiastek kwadratowy

Jedna wartość, Aistniejąca w zakresie, sprawia, że RESULTzmienna zawiera pierwiastek kwadratowy z Azaokrąglenia w dół, gdy program się kończy.

Można odpowiedzieć tylko na jedno lub dwa pytania, dla niektórych z was znalezienie odpowiednich rozwiązań będzie wyzwaniem.

Zadanie 3, 23 op

x = (A >> 16) + A / ((A >> 13) + 511) + 15
x = (x + A/x) >> 1
x = (x + A/x) >> 1
x = (x + A/x) >> 1
RESULT = x - (x > A/x)

Stosując metodę Newtona, podobnie jak inne rozwiązania, z bardziej taktownie wybranym nasieniem. Pierwszy bit A >> 16utrzymuje górną część zakresu szczęśliwym, drugi bit A / ((A >> 13) + 511)utrzymuje środkową część zakresu szczęśliwym, a ostatni bit 15dolny, a także zapobiega podziałowi przez błędy zerowe (15 to największa możliwa wartość, która pozwala 0na prawidłową zbieżność - o połowę trzykrotnie minus korekta równa się zero). W przypadku wartości wejściowych 225, 275625, 82137969, 2908768489(i pobliskich) początkowe ziarno jest dokładne. Wszystkie przypadki krawędzi (idealne kwadraty, idealne kwadraty + 1 i idealne kwadraty - 1) w zakresie 0 .. 2**32-1zostały przetestowane i są poprawne.

Kilka komentarzy na temat reguł:
przepełnienie i niedopełnienie jest dozwolone, wszystkie liczby ujemne są niedopełnione, więc 3 - 5 to 4294967294, nawet jako część większej instrukcji .

Ten ostatni kawałek okazuje się być zabójcą innowacji. Początkowo próbowałem rozwiązania przy użyciu uogólnionej formy metody Halleya , ale zdałem sobie sprawę, że biorąc pod uwagę powyższe ograniczenie, jest ono nieważne. Iteracja (stosowana do pierwiastków kwadratowych) jest następująca:

x = x * (3*A + x*x) / (A + 3*x*x)

Ta iteracja ma ładne cechy, których nie ma Newton. Zbiega się sześciennie (a nie kwadratowo), zbiega się z góry lub z dołu (a nie tylko z góry) i nie jest tak wrażliwy na źle wybrane nasiona (jeśli iteracja Newtona jest zapewniona, że ​​ziarno jest o wiele za niskie, będzie znacznie przesadzić z punktem zbieżności, a następnie trzeba cofnąć się).

Metoda Newtona ma również problem (przynajmniej w przypadku liczb całkowitych), który dość często osiąga wartość x taką, że A / x - x = 2 - w tym przypadku zbiega się do wartości większej niż właściwy pierwiastek całkowity, które należy poprawić; Metoda Halleya nie wymaga takiej korekty. Niestety wartość parametru 3*A + x*xczęsto jest większa niż dozwolona 32-bitowa liczba całkowita.

Istnieje wiele innych uogólnionych n ^th algorytmów korzeniowych, ale wszystkie one udział ta sama cecha:

x = x + x*(v - x**n)/(v*n)
x = (x*(n+1) - x**(n+1)/v)/n
x = ((n-2)*x + (4*v*x)/(v + x**n))/n
x = x*((n+2)*v + (n-2)*x**n)/(v + x**n)/n
x = ((n-2)*x + (n*x*v)/(v + (n-1)*x**n))/(n-1)
x = ((n-2)*x + x*((n*2-1)*v + x**n)/(v + (n*2-1)*x**n))/(n-1)

x = x + 2*x*(v - x**n)/(v + x**n)/n
x = x + x*31*(v - x**n)/(10*v + 21*x**n)/n
x = x + x*561*(v - x**n)/(181*v + 380*x**n)/n
x = x + x*1153*(v - x**n)/(372*v + 781*x**n)/n

itd. Większość z nich wykazuje zbieżność sześcienną lub kwadratową. Cztery ostatnie są częścią serii iteracji, które są zbieżne w zakresie zbieżności kwartalnej. Ale w praktyce metoda Newtona zapewni ci to, czego potrzebujesz, przy mniejszej liczbie operacji, chyba że musisz obliczyć setki cyfr.

65 (61) operacji (5 + 13 + 47 (43))

Zadanie 1 - maks. (A, B)

RESULT = A + (B - A) * (A <= B)

To oczywiste rozwiązanie. Potrzebujesz przypisania, potrzebujesz porównania, musisz pomnożyć porównanie z czymś, multiplikacja nie może być jedną ze zmiennych, a produkt nie może być wynikiem.

Zadanie 2 - środek (A, B, C)

RESULT = A                               \
       + (B - A) * (A > B) ^ (B <= C)    \
       + (C - A) * (A > C) ^ (C <  B)

Jest to poprawa w stosunku do mojego poprzedniego rozwiązania 15-operacyjnego, które warunkowało wszystkie trzy zmienne - pozwoliło to zaoszczędzić dwa odejmowania, ale wprowadziło kolejny test centralności. Sam test jest prosty: element znajduje się w środku i dokładnie dokładnie jeden z dwóch powyżej.

Zadanie 3 - sqrt (A)

X1     = 1024 + A / 2048
X2     = (X1  + A / X1 ) / 2
...
X10    = (X9 + A / X9 ) / 2
RESULT = X16 - (X16 * X16 > A)

Jedenaście rund zbliżenia Newtona. Stała magiczna 1024 jest już pokonanaWolframW (a 512 powoduje dzielenie przez zero dla a = 0, zanim a = 2 ** 32 zbiega się), ale jeśli możemy zdefiniować 0/0 jako zero, dziesięć iteracji będzie działać z wartością początkową z 512. Przyznaję, że moje twierdzenie o dziesięciu iteracjach nie jest całkowicie czyste, ale nadal twierdzę, że w nawiasach. Będę jednak musiał sprawdzić, czy dziewięć jest możliwe.Rozwiązaniem WolframH jest dziewięć iteracji.

Operatorzy 1: 5

RESULT = B ^ (A ^ B)*(A > B)

2: 13 operatorów

RESULT = B ^ (A ^ B)*(A > B) ^ (A ^ C)*(A > C) ^ (B ^ C)*(B > C)

3: 27 operatorów

g = 47|((0x00ffffff & A)>>10)|(A>>14)
r = (g + A/g)/3
r = (r + A/r)>>1
r = (r + A/r)>>1
r = (r + A/r)>>1
RESULT = r - (r*r-1>=A)

Zadanie 3, 39 operacji

EDYCJA: Zmieniono ostatni wiersz; Zobacz komentarze.

Jest to implementacja metody Newthona. Testowany ze wszystkimi dodatnimi kwadratami, a także z dodatnimi kwadratami minus jeden, a także milion losowych liczb w zakresie od 0 do 2 ^ 32-1. Wartość pozornie zabawny wyjściowy jest skrótem (1022 + A/1022) / 2, który wymaga najmniejszej liczby iteracji (chyba), a także sprawia, że RESULTna A=0prawo (które nie byłyby w przypadku 1024zamiast 1022).

r = (511 + A/2044)
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
RESULT = r - (r > A/r)