Proszę nie rozgałęziać

14

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.

aaaaaaaaaaaa
źródło
Gdzie są jedni operatorzy? Nie dbam o to, -ale ~może być miły (nawet jeśli nie wiem po co).
John Dvorak,
Jasne 0xFFFF_FFFF_FFFF_FFFF ^ xi 0 - x. Jak mogłem zapomnieć?
John Dvorak,
@JanDvorak To najkrótszy opis, ponieważ logika kompletności !również nie jest dość trywialna:x == 0 .
aaaaaaaaaaaa
Jakie jest zachowanie dzielenia przez zero?
John Dvorak,
W Mathematica (a> b) zwraca True lub False. Boole zamienia False na 0 i True na 1. Czy używanie jest dozwoloneBoole[a-b] ?
DavidC,

Odpowiedzi:

5

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.

primo
źródło
Całkiem fajnie, ale zawodzi w przypadku 4294967295. Jeśli chodzi o zasady, muszą być ciasni, aby było ciekawie. Można spierać się o to, jakie dokładne założenia stanowią największe wyzwanie, ale ostatecznie znacznie ważniejsze jest, aby reguły były jasne i jednoznaczne, niż na to, na co pozwalają.
aaaaaaaaaaaa
Nie sądzę, żeby Halley i tak byłaby tego warta, z daleka przypuszczam, że poprawi się nieco mniej niż 3-krotnie, Newton trochę mniej niż 2-krotnie. Podobnie z dobrego przypuszczenia, że ​​Halley potroi się dokładność, Newton ją podwoi. Tak więc jedna iteracja Halleya jest warta dokładnie dokładnie log(3)/log(2) ~= 1.585iteracji Newtona.
aaaaaaaaaaaa
@eBusiness Początkowo miałem 2 Halleya z podobnie wybranym nasionem w sumie 25 operacji - z błędem kiedy A = 0- więc jest to w rzeczywistości krótsze. Około 4294967295 , co było przeoczeniem: jako 65536² ≡ 0 , iteracja korekty nie jest poprawna. Zobaczę, czy mogę znaleźć alternatywę.
primo
@eBusiness naprawiony.
primo
Najładniejszy pierwiastek kwadratowy paczki, dobra robota i oficjalna odznaka zwycięstwa.
aaaaaaaaaaaa
5

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.

John Dvorak
źródło
Myślę, że pierwsza linia Zadania 3 jest nieprawidłowa: druga stała powinna być 4-krotnością pierwszej stałej (aby mieć „czysty” Newton).
Przywróć Monikę
@WolframH Lepsze początkowe przypuszczenie może wyjaśnić, dlaczego marnuję cykle. Skąd pomysł na 4 *? To wygląda jak dwie iteracje połączone w jedną.
John Dvorak
(1024 + A/1024)/2 == (512 + A/2048)(co jest jak X0 = 1024, a następnie uruchomienie Newtona).
Przywróć Monikę
Ładne rozwiązanie zadania 1. Jajko Kolumba.
DavidC
@DavidCarraher oczywiście poprawnym rozwiązaniem byłoby MOV RESULT, A; CMP A,B; CMOVA RESULT, B;-)
John Dvorak
5

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)
aaaaaaaaaaaa
źródło
5

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)
Przywróć Monikę
źródło
Czy powinienem zachować moją gorszą kopię metody Newtona, która została zoptymalizowana równolegle z twoją i opublikowała sporo czasu później? Wielkie umysły myślą podobnie i podział rozwiązania na dwie dwie odpowiedzi jest zły, ale taki jest obecny stan rzeczy, ponieważ nie odpowiedziałeś # 2.
John Dvorak,
@JanDvorak: Dzięki za pytanie. W porządku, jeśli podasz moją nieco krótszą metodę w swojej odpowiedzi. Dziękuję również za uznanie :-)
Przywróć Monikę
Naprawdę fajna próba, ale nie udaje się wprowadzić danych 4294965360 do 4294967295.
aaaaaaaaaaaa
@eBusiness: Jaki wynik otrzymujesz za te wkłady? Dostaję 65535 w moich testach, co jest OK.
Przywróć Monikę
Dostaję 65536. Może nie używasz zalecanego formatu liczb całkowitych.
aaaaaaaaaaaa