Jeder, der ein wenig mit Codeoptimierung auf niedriger Ebene beschäftigt ist, kennt die Gefahren der Verzweigung, sei es als if-Anweisungen, Schleifen oder select-Anweisungen implementiert.

Einfache Probleme können mit einfacher Arithmetik viel besser gelöst werden.

Für die folgenden Probleme sind alle Variablen vorzeichenlose 32-Bit-Ganzzahlen, und der einzige zulässige Code sind einfache Mengenanweisungen, die nur die folgenden Operatoren betreffen:

+ 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
=

Jede Zeile muss aus einer Variablenkennung, gefolgt von einem Mengenoperator und einem Ausdruck bestehen.

Ein Ausdruck darf keine zusätzlichen Mengenoperatoren enthalten, kann jedoch Variablenbezeichner, Literalzahlen und Klammern enthalten.

Die Golfwertung zählt nur die Anzahl der Fahrer.

Beispiel:

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

Hat eine Punktzahl von 5 Operatoren.

Eine Lösung kann so viele Variablen enthalten, wie der Autor für richtig hält.
Nicht gesetzte Variablen haben Wert 0.
Über- und Unterlauf ist erlaubt, alle negativen Zahlen unterlaufen , so 3 - 5sind 4294967294auch als Teil einer größeren Erklärung.

Schritt 1: max

Zwei Werte, Aund Bbestehen im Rahmen machen die RESULTVariable enthalten die größte dieser Werte , wenn das Programm beendet wird .

Schritt 2: Median

Drei Werte, A, Bund Cbestehen im Rahmen machen die RESULTVariable den Median dieser Werte enthalten , wenn das Programm beendet wird .

Schritt 3: Quadratwurzel

Ein Wert, der Aim Gültigkeitsbereich vorhanden ist, bewirkt, dass die RESULTVariable die Quadratwurzel von enthält A, abgerundet, wenn das Programm beendet wird.

Es ist in Ordnung, nur eine oder zwei der Fragen zu beantworten. Für einige von Ihnen wird es eine Herausforderung sein, nur gültige Lösungen zu finden.

Aufgabe 3, 23 ops

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)

Verwendung der Newton-Methode, wie bei den anderen Lösungen, mit einem taktvolleren Samen. Das erste Bit A >> 16hält die obere Hälfte des Bereichs, das zweite Bit A / ((A >> 13) + 511)die mittlere Hälfte des Bereichs und das letzte Bit 15die untere und verhindert außerdem die Division durch Nullfehler (15 ist der größtmögliche Wert, der eine 0korrekte Konvergenz ermöglicht - halbiert dreimal minus Korrektur gleich Null). Für die Eingabewerte 225, 275625, 82137969, 2908768489(und Werte in der Nähe) ist der anfängliche Startwert genau. Alle Kantenfälle (perfekte Quadrate, perfekte Quadrate + 1 und perfekte Quadrate - 1) im Bereich 0 .. 2**32-1wurden getestet und sind korrekt.

Ein paar Kommentare zu den Regeln:
Überlauf und Unterlauf sind erlaubt, alle negativen Zahlen unterlaufen, also 3 - 5 ist 4294967294, auch als Teil einer größeren Anweisung .

Das letzte bisschen entpuppt sich als ein Innovationskiller. Ich versuchte zunächst eine Lösung mit einer verallgemeinerten Form der Halleyschen Methode , erkannte jedoch, dass sie aufgrund der obigen Einschränkung ungültig war. Die Iteration (bezogen auf Quadratwurzeln) lautet wie folgt:

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

Diese Iteration hat nette Eigenschaften, die Newtons nicht hat. Es konvergiert kubisch (und nicht quadratisch), es konvergiert von oben oder unten (und nicht nur von oben) und es ist nicht so empfindlich für einen schlecht ausgewählten Samen (wenn Newtons Iteration einen viel zu niedrigen Samen liefert, wird dies der Fall sein) den Konvergenzpunkt stark überschreiten und sich dann wieder nach unten arbeiten müssen).

Newtons Methode hat auch das Problem (zumindest beim Umgang mit ganzen Zahlen), dass sie ziemlich oft ein x erreicht, so dass A / x - x = 2 - in diesem Fall zu einem Wert konvergiert, der um eins größer ist als die eigentliche ganze Wurzel. was korrigiert werden muss; Die Methode von Halley benötigt keine solche Korrektur. Leider ist der Wert von 3*A + x*xhäufig größer als der zulässige 32-Bit-Ganzzahlbereich.

Es gibt eine Reihe anderer verallgemeinerter n- ^ter Root-Algorithmen, die jedoch alle dasselbe Merkmal aufweisen:

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

usw. Die meisten davon zeigen entweder kubische oder quadratische Konvergenz. Die letzten vier sind Teil einer Reihe von Iterationen, die sich der quartalen Konvergenz annähern. In der Praxis erhalten Sie mit der Newton-Methode jedoch mit weniger Operationen das, was Sie benötigen, es sei denn, Sie müssen viele Hundert Stellen berechnen.

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

Aufgabe 1 - Max (A, B)

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

Dies ist die naheliegende Lösung. Sie brauchen die Zuweisung, Sie brauchen einen Vergleich, Sie müssen den Vergleich mit etwas multiplizieren, der Multiplikand kann nicht eine der Variablen sein und das Produkt kann nicht das Ergebnis sein.

Aufgabe 2 - Mitte (A, B, C)

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

Dies ist eine Verbesserung gegenüber meiner vorherigen 15-op-Lösung, bei der alle drei Variablen konditioniert wurden - dies ersparte zwei Subtraktionen, führte jedoch einen weiteren Zentralitätstest ein. Der Test selbst ist einfach: Ein Element befindet sich in der Mitte, wenn genau eines der beiden Elemente darüber liegt.

Aufgabe 3 - sqrt (A)

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

Elf Runden Newton-Approximation. Die magische Konstante von 1024 wird bereits von WolframW geschlagen (und 512 bewirkt eine Division durch Null für a = 0, bevor a = 2 ** 32 konvergiert), aber wenn wir 0/0 als Null definieren können, funktionieren zehn Iterationen mit dem Startwert Ich gebe zu, dass meine Behauptung von zehn Iterationen nicht ganz sauber ist, aber ich behaupte sie immer noch in Klammern. Ich muss jedoch untersuchen, ob neun möglich sind.Die WolframH-Lösung besteht aus neun Iterationen.

1: 5 Bediener

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

2: 13 Bediener

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

3: 27 Bediener

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)

Aufgabe 3, 39 Operationen

EDIT: Letzte Zeile geändert; Zeige Kommentare.

Dies ist eine Implementierung der Newthon-Methode. Getestet mit allen positiven Quadraten und auch mit den positiven Quadraten minus eins sowie mit einer Million Zufallszahlen im Bereich von 0 bis 2 ^ 32-1. Der scheinbar lustig Startwert ist die Abkürzung für (1022 + A/1022) / 2, die die geringste Anzahl von Iterationen benötigt (glaube ich), und macht auch die RESULTfür A=0Recht (was nicht der Fall wäre , 1024statt 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)