Bitte keine Verzweigung

14

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.

aaaaaaaaaaa
quelle
Wo sind unäre Operatoren? Es ist mir egal, -aber ich ~könnte nett sein (auch wenn ich nicht weiß, wofür).
John Dvorak
Sicher 0xFFFF_FFFF_FFFF_FFFF ^ xund 0 - x. Wie hätte ich das vergessen können?
John Dvorak
@JanDvorak Es machte die kürzeste Beschreibung, der Vollständigkeit halber Logik nicht !auch ziemlich trivial ist: x == 0.
aaaaaaaaaaa
Was ist das Verhalten der Division durch Null?
John Dvorak
In Mathematica gibt (a> b) Wahr oder Falsch zurück. Boole konvertiert False in 0 und True in 1. Ist die Verwendung legal Boole[a-b]?
DavidC

Antworten:

5

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.

primo
quelle
Ziemlich nett, aber scheitert bei 4294967295. Was die Regeln betrifft, müssen sie eng sein, um es interessant zu machen. Sie können sich überlegen, welche genauen Voraussetzungen die beste Herausforderung darstellen. Letztendlich ist es jedoch viel wichtiger, dass die Regeln klar und eindeutig sind, als was genau sie zulassen.
aaaaaaaaaaa 13.09.13
Ich glaube nicht, dass es sich für Halley gelohnt hätte, nach weitem Ermessen wird es sich um etwas weniger als den Faktor 3 verbessern, Newton um etwas weniger als den Faktor 2. Entsprechend wird sich Halley nach einer guten Vermutung verdreifachen die Genauigkeit wird Newton verdoppeln. Eine Halley-Iteration ist also ziemlich genau log(3)/log(2) ~= 1.585Newton-Iterationen wert .
aaaaaaaaaaa 13.09.13
@eBusiness Ich hatte anfangs 2 Halleys mit einem ähnlich gewählten Startwert von insgesamt 25 Operationen - mit Fehler, wenn A = 0-, also ist dies tatsächlich kürzer. Bei 4294967295 war das ein Versehen: Mit 65536² ≡ 0 kann die Korrekturiteration nicht korrigiert werden. Ich werde sehen, ob ich eine Alternative finden kann.
Primo
@eBusiness behoben.
Primo
Die glatteste Quadratwurzel des Rudels, gute Arbeit und ein offizielles Siegesabzeichen.
aaaaaaaaaaa
5

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.

John Dvorak
quelle
Ich denke, die erste Zeile von Aufgabe 3 ist nicht richtig: Die zweite Konstante sollte das Vierfache der ersten Konstante sein (um "reines" Newton zu haben).
Setzen Sie Monica
@WolframH Eine bessere erste Vermutung könnte erklären, warum ich Zyklen verschwende. Wo bist du auf 4 * gekommen? Dies sieht aus wie zwei Iterationen in einer zusammengefasst.
John Dvorak
(1024 + A/1024)/2 == (512 + A/2048)(Das ist wie X0 = 1024, und dann starten Newton).
Setzen Sie Monica
Schöne Lösung für Aufgabe 1. Columbus 'Ei.
DavidC
@ DavidCarraher natürlich die richtige Lösung wäre MOV RESULT, A; CMP A,B; CMOVA RESULT, B;-)
John Dvorak
5

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)
aaaaaaaaaaa
quelle
5

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)
Setzen Sie Monica wieder ein
quelle
Soll ich meine minderwertige Kopie der Newton-Methode behalten, die parallel zu Ihrer optimiert wurde und später eine angemessene Zeitspanne veröffentlicht hat? Große Köpfe denken gleich und es ist schlecht, die Lösung auf zwei Antworten aufzuteilen, aber das ist der aktuelle Stand der Dinge, da Sie nicht auf # 2 geantwortet haben.
John Dvorak
@ JanDvorak: Danke für die Nachfrage. Es ist in Ordnung, wenn Sie meine etwas kürzere Methode in Ihre Antwort einfügen. Vielen Dank auch für die Anerkennung :-)
Reinstate Monica
Wirklich netter Versuch, schlägt aber für die Eingaben 4294965360 bis 4294967295 fehl.
aaaaaaaaaa
@eBusiness: Welches Ergebnis erzielen Sie für diese Eingaben? Ich bekomme 65535 in meinen Tests, was in Ordnung ist.
Setzen Sie Monica
Ich erhalte 65536. Vielleicht verwenden Sie nicht das vorgeschriebene Ganzzahlformat.
aaaaaaaaaaa