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 - 5
jest 4294967294
, nawet jako część większego rachunku.
Zadanie 1: maks
Dwie wartości, A
i B
istnieją w zakresie, sprawiają, że RESULT
zmienna zawiera największą z tych wartości po zakończeniu programu.
Zadanie 2: Mediana
Trzy wartości, A
, B
i C
istnieją w zakresie sprawiają, że RESULT
zmienna zawiera medianę tych wartości, gdy kończy się program.
Zadanie 3: Pierwiastek kwadratowy
Jedna wartość, A
istniejąca w zakresie, sprawia, że RESULT
zmienna zawiera pierwiastek kwadratowy z A
zaokrą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.
źródło
-
ale~
może być miły (nawet jeśli nie wiem po co).0xFFFF_FFFF_FFFF_FFFF ^ x
i0 - x
. Jak mogłem zapomnieć?!
również nie jest dość trywialna:x == 0
.Boole[a-b]
?Odpowiedzi:
Zadanie 3, 23 op
Stosując metodę Newtona, podobnie jak inne rozwiązania, z bardziej taktownie wybranym nasieniem. Pierwszy bit
A >> 16
utrzymuje górną część zakresu szczęśliwym, drugi bitA / ((A >> 13) + 511)
utrzymuje środkową część zakresu szczęśliwym, a ostatni bit15
dolny, a także zapobiega podziałowi przez błędy zerowe (15 to największa możliwa wartość, która pozwala0
na prawidłową zbieżność - o połowę trzykrotnie minus korekta równa się zero). W przypadku wartości wejściowych225, 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 zakresie0 .. 2**32-1
został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:
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*x
czę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:
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.
źródło
log(3)/log(2) ~= 1.585
iteracji Newtona.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ę.65 (61) operacji (5 + 13 + 47 (43))
Zadanie 1 - maks. (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)
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)
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.źródło
(1024 + A/1024)/2 == (512 + A/2048)
(co jest jakX0 = 1024
, a następnie uruchomienie Newtona).MOV RESULT, A; CMP A,B; CMOVA RESULT, B
;-)Operatorzy 1: 5
2: 13 operatorów
3: 27 operatorów
źródło
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, żeRESULT
naA=0
prawo (które nie byłyby w przypadku1024
zamiast1022
).źródło