Was ist, wenn wir wunderbare Mathematik (nämlich lineare Gleichungen) und unser ebenso wundervolles
JavaScript nehmen und dann einander überlagern? Unter den Bedingungen der Einschränkungen und Besonderheiten der js-Umgebung kann sich ein einfaches mathematisches Problem in ein sehr merkwürdiges und voller Fallen von js-Steinen verwandeln. Bei der letzten
HolyJS 19- Konferenz in Moskau machte eine solche lineare Gleichung (neben anderen Aufgaben von
SEMrush ) ziemlich viel Lärm.
Und ja, das ist wieder die Überschrift von Entertaining JavaScript: Ich bitte Sie, alle auszuschneiden, die sich dafür interessieren.
Natürlich sollte alles, was im Folgenden beschrieben wird - dies ist nur ein leichtfertiger Versuch, zwei wundervolle Dinge in Symbiose zu bringen, um Spaß zu haben - nicht ernst genommen werden. Und dieses Material hätte es nicht gegeben, wenn nicht das lebhafte Interesse der Konferenzteilnehmer geweckt worden wäre, wofür ihnen ein besonderer Dank gilt!
Formulierung
1. Finden Sie alle ganzzahligen Lösungen der Gleichung:
9 +~ x >> 6 / 3 = -x / 3
2. Finden Sie alle ganzzahligen Lösungen der Gleichung:
9 +~ x >> 6 / 3 = -x / 3 | 0
Die zweite Gleichung unterscheidet sich von der ersten nur durch eine zusätzliche Operation auf der rechten Seite.
Mathematische Approximation
Wir wenden uns der ersten Gleichung zu. Zunächst werden wir die Prioritäten der verwendeten Operationen
gemäß der Tabelle verstehen:
(9 +(~ x)) >> (6 / 3) = -x / 3
Wir nehmen die bitweise Negation von
x und addieren sie zu 9. Das Ergebnis der Addition wird bitweise um die Anzahl der Bits nach rechts verschoben, die dem Ergebnis der Division von 6 durch 3 entspricht.
Offensichtlich liegt das Problem in der Verwendung bitweiser Operationen für das gewünschte
x . Um jedoch eine bedingte Wurzel für weitere Überlegungen zu finden, lohnt es sich, die Gleichung zu einem ungefähren mathematischen Analogon zu bringen.
Bitweise Operationen arbeiten mit Operanden als vorzeichenbehaftete 32-Bit-Ganzzahlen. Das bitweise NICHT kann durch
eine ganzzahlige Negation aus dem Inkrement ersetzt werden:
(9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3
Die bitweise Verschiebung nach rechts (unter Beibehaltung des Vorzeichens) kann durch eine
ganzzahlige Division durch zwei bis zu dem Grad ersetzt werden, der dem Operanden auf der rechten Seite entspricht:
(8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3
Natürlich sind diese Ersetzungen sehr willkürlich, und wir werden später darüber sprechen. Und jetzt haben wir die übliche lineare Gleichung, deren einzige Wurzel -24 ist. Ersetzen Sie den Wert auf der linken und rechten Seite der ursprünglichen Gleichung:
9 +~ (-24) >> 6 / 3;
Beide Teile sind gleich, was bedeutet, dass nicht alles so hoffnungslos ist und -24 wirklich eine Lösung ist.
Suche nach den Faulen
Wenn wir Graphen der Funktionen
f1 (x) = (8 -x) / 4 und
f2 (x) = -x / 3 zeichnen, finden wir natürlich den einzigen Schnittpunkt der beiden Linien bei
x = -24 .
Wir haben jedoch einige ungleiche Substitutionen mit bitweisen Operationen im linken Ausdruck durchgeführt, so dass der Graph der Funktion
f1 in Wirklichkeit etwas anders sein wird. Für jedes
x ist der Wert der Funktion eine ganze Zahl, die sich von dem Wert auf der durchgehenden Linie
f1 unterscheidet, mit einer möglichen Verschiebung im Bereich von -1 bis 1. Dies bedeutet, dass wir den Lösungssuchbereich nach links und rechts von -24 einschränken können, wobei die Werte der Funktionen
f1 und
f2 beginnen, sich um mehr als eins zu unterscheiden.
Um die Grenzen des Suchbereichs zu finden, können Sie 1) die Ungleichung mit dem Modul lösen oder 2) die Diagramme der Funktionen genauer betrachten. Wir werden feststellen, dass
x einen Blick auf das Segment wert ist [-36, -12]:
| (8 - x) / 4 + x / 3 | <= 1
Um ganze Lösungen in einem geschlossenen Bereich
durchlaufen zu können
, schreiben wir die
findx- Funktion:
const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f);
Die Funktion gibt ein Array von Ganzzahlen zurück, für die der Wert der übergebenen Funktion
f auf
true reduziert wird. Um Lösungen zu finden, stellen wir die Gleichung mit dem Gleichheitsoperator als js-Funktion dar:
let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12);
Somit sind
x = [-24, -21, -18, -15] die gewünschten Lösungen für die erste Gleichung.
Grafische Lösung
Die Aufzählung ist natürlich ein Erfolg, aber lassen Sie uns den Graphen der Funktion
f1 noch bis zum Ende herausfinden und die Gleichung grafisch lösen. Darüber hinaus impliziert die Lösung nicht das obligatorische Eigentum an der Browserkonsole.
Der bitweise NOT-Operator verwirft einfach den Bruchteil, wodurch das Ergebnis
- (x + 1) abgerundet wird. Der Bitverschiebungsoperator ist etwas komplizierter. Wir haben es durch eine Ganzzahldivision ersetzt, aber abhängig vom Vorzeichen der Dividendenzahl rundet diese Operation das Ergebnis entweder nach unten oder nach oben:
10 >> 2;
Wir wissen jedoch, dass das gewünschte
x im Bereich [-36, -12] liegt. Dementsprechend liegt der linke Operand der bitweisen Verschiebung (
8-x ) im Bereich [20, 44], das heißt, er ist immer positiv. Was wiederum eine ganzzahlige Division mit Abrundung bedeutet.
Nachdem wir die Art der Operationen herausgefunden haben, können wir den korrekten Graphen der Funktion
f1 zeichnen:
Wir finden vier Schnittpunkte der Funktionen in den gleichen Koordinaten
x = [-24, -21, -18, -15].
Zweite Gleichung
Also kamen wir zur zweiten Gleichung:
9 +~ x >> 6 / 3 = -x / 3 | 0
Sie unterscheidet sich von der ersten durch das Hinzufügen eines bitweisen ODER. Wenn der rechte Operand einer solchen Operation Null ist, ist das Ergebnis einfach der Wert des linken Operanden, wobei der Bruchteil verworfen wird.
Lassen Sie uns zunächst dieselbe Suche durchführen. Legen Sie einfach den Suchbereich fest. Da die Funktion
f2 jetzt einen ähnlichen Charakter wie
f1 hat , sollte aus Gründen der Zuverlässigkeit eine mögliche Verschiebung aufsummiert und die Suche begrenzt werden, wenn sich die Funktionen im absoluten Wert um mehr als zwei Einheiten unterscheiden - dies ist [-48, 0].
let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0);
Und wir haben die gleichen Antworten bekommen. Es besteht der Verdacht, dass doch etwas nicht stimmt. Fakt ist jedoch, dass wir die ursprüngliche Gleichung als eine solche js-Funktion dargestellt haben und die beiden Ausdrücke (links und rechts) durch den Gleichheitsoperator zu einem zusammengefasst haben. Und der Gleichheitsoperator hat seine Priorität, die höher ist als die Priorität des bitweisen ODER. Die Funktion ist identisch mit:
x => (9 +~ x >> 6 / 3 == -x / 3) | 0;
In diesem Fall hat ein bitweises ODER keine Auswirkung, da
true | 0 = 1 . Um dies zu vermeiden, muss im Funktionskörper explizit angegeben werden, dass die Ergebnisse zweier Unterausdrücke verglichen werden:
let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0);
Die Anzahl der Lösungen hat zugenommen. Betrachten wir nun die Funktionsgraphen. Analog zu
f1 konstruiert eine „Trittleiter“ eine modifizierte Funktion
f2 :
Orte von Funktionsgraphen überlappen sich, aber wir interessieren uns nur für Punkte mit einem ganzzahligen Wert der
x- Koordinate: [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15], nur 12 Lösungen. Der Schnittpunkt zweier "Leitern" mit den Schritten 3 und 4 kann auf Wunsch algorithmisch ermittelt werden.
Zusätzliche Frage
In dem auf der Konferenz vorgeschlagenen Problem gab es eine zusätzliche Frage: Es musste die Mindestlösung für Gleichung 2 gefunden werden. Es wurde nicht gesagt, dass dies notwendigerweise eine ganze Zahl ist, daher stellte sich heraus, dass die Antwort
x = -32 - falsch war.
Eine Lösung mit brachialer Gewalt zu finden, wird hier nicht funktionieren, aber es ist sehr einfach, sie grafisch zu lösen. Dies ist der nächste Wert
x von -33 auf der rechten Seite:
Es scheint, dass
x = -32. (9). Das ist aber immer noch nicht wahr. Da unsere Umgebung JavaScript ist, bedeutet dies, dass wir bei der Darstellung von Zahlen durch den verwendeten Datentyp eingeschränkt sind. Die Typennummer ist float64,
eine Gleitkommazahl mit doppelter Genauigkeit (IEEE 754). Sich daran zu erinnern und die ungefähre Genauigkeit zu nennen, reichte aus, um einen Plüschfuchs zu bekommen!
Die dunkle Seite bitweiser Operationen
Wie oben erwähnt, konvertieren bitweise Operationen Operanden in 32-Bit-Zahlen, dargestellt durch die Sequenz 0 und 1 - dies ist der Bereich [-2147483648, 2147483647]. Wenn die Zahl nicht hineinpasst, werden die höchstwertigen Bits verworfen.
In der ersten Gleichung spielt dies keine Rolle, da es auf der rechten Seite keine bitweise Operation gibt. Aber im zweiten Fall bringt diese Umrechnung von Zahlen einen interessanten Effekt mit sich.
Zum Beispiel wird die Zahl -24 dargestellt als:
11111111111111111111111111101000
Ein negativer Wert der Zahl wird erhalten, indem (bitweise NICHT) Bits in dem Datensatz einer positiven Zahl durch Addition von Eins invertiert werden.
Jede Zahl außerhalb des Bereichs ist nach der Umwandlung, die in dieser 32-Bit-Sequenz endet, bei Binäroperationen mit der Zahl -24 identisch. Zum Beispiel sind dies Zahlen:
4294967272 | 0;
Auf der rechten Seite der Gleichung teilen wir
x vor der bitweisen Operation durch 3. Wir finden
x unter den "Äquivalenten" -24, die durch 3 teilbar sind. Die nächstliegende Zahl ist 12884901864. Ersetzen Sie sie in der Gleichung:
9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8
Das Ergebnis der Division durch 3 (-4294967288) passt nicht zu den zugewiesenen 32 Ziffern. Beim Invertieren von Bits geht das Vorzeichen endgültig verloren und es verbleiben nur noch 8:
00000000000000000000000000001000
Zusätzlich können Sie die Richtigkeit des Ergebnisses überprüfen, indem Sie die Funktion
eq2 aufrufen:
eq2(12884901864);
Wenn Sie darüber nachdenken, finden Sie neben dieser Wurzel die Projektionen der verbleibenden 11 ganzzahligen Lösungen.
Somit erscheint eine große Anzahl neuer Lösungen, und nur das nächsthöhere positive Äquivalent von -24 wird berücksichtigt. Dies ist jedoch nicht so interessant wie die Hauptaufgabe, und bei der Analyse der Entscheidungen der Teilnehmer wurden sehr seltene Antworten separat bewertet. Um nicht durcheinander zu kommen, können Sie eine Einschränkung für die gewünschten Ganzzahlen in die Problembedingung als vorzeichenbehaftete 32-Bit-Ganzzahlen einfügen.
Und das kannst du nicht machen!
Um dann die kleinste Wurzel zu finden, sollten Sie auf die Nachbarschaft von
Number.MAX_SAFE_INTEGER mit einem negativen Vorzeichen
achten , da diese Zahl eine Ganzzahl ist und mit extremer Präzision float64. Na dann auf eigene Faust.
Fazit
Infolge der Konferenz lösten die meisten Teilnehmer das Problem durch eine umfassende Suche, während der Bereich für die Suche aus verschiedenen Gründen völlig unterschiedlich war. Aber wie wir gesehen haben, reicht es aus, mit ~ 50 ganzen Zahlen davonzulaufen. Viele sind in betriebliche Prioritätsfallen geraten. Jemand hat sich auch grafisch so gefreut. Einheiten von der Veröffentlichung von 32 Kategorien überrascht. Sie könnten brachiale Gewalt anwenden, um bei Aufgaben weiter voranzukommen. Um jedoch einen zusätzlichen Preis zu erhalten, war es immer noch notwendig, eine fast mathematische Analyse durchzuführen.
Ich hoffe sehr, dass Ihnen die Idee einer so untypischen Aufgabe wie Unterhaltung für das Konferenzformat gefallen hat. Im letzten Jahr habe ich mehrere solcher "unterhaltsamen" JavaScript-Aufgaben angesammelt. Ich beschloss, sie alle an einem Ort zu sammeln. Folgen Sie dem Link, wenn Sie keine Angst haben:
Unerwartet herausgefordertes JavaScript . Die Aufgaben von
Look Complex und
Broken Pipe , die ebenfalls auf der Konferenz vorgeschlagen wurden, wurden bereits festgelegt. Ja, es gibt viele solcher Sammlungen, aber diese gehören mir! Nochmals vielen Dank an alle.