Et si nous prenions de merveilleuses mathématiques (à savoir, des équations linéaires) et notre
JavaScript tout aussi merveilleux, puis nous les superposions? Dans les conditions de limitations et de spécificités de l'environnement js, un simple problème mathématique peut se transformer en un très curieux et plein d'embûches de pierres js. Lors de la dernière conférence
HolyJS 19 à Moscou, une de ces équations linéaires (parmi d'autres tâches de
SEMrush ) a fait pas mal de bruit.
Et oui, c'est encore le titre de Entertaining JavaScript: je vous demande de couper tout le monde qui s'en soucie.
Bien sûr, tout ce qui est décrit ci-dessous - ce n'est qu'une tentative frivole de symbiose entre deux choses merveilleuses pour s'amuser - ne doit pas être pris au sérieux. Et ce matériel n'aurait pas existé s'il n'y avait pas eu un vif intérêt de la part des participants à la conférence, pour laquelle un merci spécial à eux!
Libellé
1. Trouvez toutes les solutions entières de l'équation:
9 +~ x >> 6 / 3 = -x / 3
2. Trouvez toutes les solutions entières de l'équation:
9 +~ x >> 6 / 3 = -x / 3 | 0
La deuxième équation ne diffère de la première que par une opération supplémentaire sur le côté droit.
Approximation mathématique
Nous passons à la première équation. Et pour commencer, nous comprendrons les priorités des opérations utilisées,
selon le tableau :
(9 +(~ x)) >> (6 / 3) = -x / 3
Nous prenons la négation au niveau du bit de
x , puis nous l'ajoutons à 9. Le résultat de l'addition est décalé au niveau du bit vers la droite par le nombre de bits égal au résultat de la division de 6 par 3.
Évidemment, le problème réside dans l'utilisation d'opérations au niveau du bit sur le
x souhaité. Mais afin de trouver une racine conditionnelle pour un raisonnement plus approfondi, il vaut la peine d'essayer de ramener l'équation à un analogue mathématique approximatif.
Les opérations au niveau du bit fonctionnent avec des opérandes en tant qu'entiers 32 bits signés. Le NOT au niveau du bit peut être remplacé par
une négation
entière de l'incrément:
(9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3
Le décalage au niveau du bit vers la droite (tout en préservant le signe) peut être remplacé par une division
entière par deux au degré égal à l'opérande de droite:
(8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3
Bien sûr, ces remplacements sont très arbitraires, et nous en reparlerons plus tard. Et maintenant, nous avons l'équation linéaire habituelle, dont la seule racine est -24. Remplacez la valeur dans les côtés gauche et droit de l'équation d'origine:
9 +~ (-24) >> 6 / 3;
Les deux parties sont égales, ce qui signifie que tout n'est pas si désespéré et -24 est vraiment une solution.
Rechercher les paresseux
Si nous dessinons des graphiques des fonctions
f1 (x) = (8 -x) / 4 et
f2 (x) = -x / 3 , alors bien sûr, nous trouvons le seul point d'intersection des deux lignes à
x = -24 .
Mais nous avons fait quelques substitutions inégales avec des opérations au niveau du bit dans l'expression de gauche, donc en réalité le graphique de la fonction
f1 sera légèrement différent. Pour tout
x, la valeur de la fonction sera un entier différent de la valeur sur la ligne continue
f1 avec un décalage possible dans la plage de -1 à 1. Cela signifie que nous pouvons limiter la zone de recherche de solution à gauche et à droite de -24, où les valeurs des fonctions
f1 et
f2 commencer à différer de plus d'un.
Pour trouver les limites de la zone de recherche, vous pouvez 1) résoudre l'inégalité avec le module, ou 2) regarder de plus près les graphiques des fonctions. Nous constaterons que
x vaut la peine de regarder le segment [-36, -12]:
| (8 - x) / 4 + x / 3 | <= 1
Pour itérer sur des solutions entières dans une plage fermée
[début, fin], nous écrivons la fonction
findx :
const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f);
La fonction renvoie un tableau d'entiers pour lesquels la valeur de la fonction passée
f est réduite à
true . Pour trouver des solutions, nous représentons l'équation comme une fonction js en utilisant l'opérateur d'égalité:
let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12);
Ainsi,
x = [-24, -21, -18, -15] sont les solutions souhaitées pour la première équation.
Solution graphique
L'énumération est bien sûr un succès, mais essayons de trouver le graphique de la fonction
f1 jusqu'à la fin et de résoudre l'équation graphiquement. De plus, la solution n'implique pas la propriété obligatoire de la console du navigateur.
L'opérateur NOT au niveau du bit supprime simplement la partie fractionnaire, ainsi le résultat
- (x + 1) sera arrondi vers le bas. L'opérateur de décalage de bit est un peu plus compliqué. Nous l'avons remplacé par une division entière, mais selon le signe du nombre de dividendes, cette opération arrondit le résultat vers le bas ou vers le haut:
10 >> 2;
Cependant, nous savons que le
x souhaité est dans la plage [-36, -12]. Par conséquent, l'opérande gauche de décalage au niveau du bit (
8 -x ) est dans la plage [20, 44], c'est-à-dire qu'il est toujours positif. Ce qui signifie à son tour une division entière avec arrondi.
Après avoir compris la nature des opérations, nous pouvons dessiner le graphique correct de la fonction
f1 :
Nous trouverons quatre points d'intersection des fonctions dans les mêmes coordonnées
x = [-24, -21, -18, -15].
Deuxième équation
Donc, nous sommes arrivés à la deuxième équation:
9 +~ x >> 6 / 3 = -x / 3 | 0
Il diffère du premier par l'ajout d'un OU au niveau du bit. Si l'opérande droit d'une telle opération est nul, alors le résultat est simplement la valeur de l'opérande gauche avec la partie fractionnaire rejetée.
Pour commencer, procédons à la même recherche, choisissez simplement la zone de recherche. Puisque maintenant la fonction
f2 a un caractère similaire à
f1 , pour la fiabilité, le décalage possible devrait être résumé et la recherche devrait être limitée lorsque les fonctions diffèrent en valeur absolue de plus de deux unités - c'est [-48, 0].
let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0);
Et nous avons eu les mêmes réponses. On soupçonne qu'après tout, quelque chose ne va pas. Mais le fait est qu'après avoir représenté l'équation d'origine en tant que telle fonction js, nous avons combiné les deux expressions (gauche et droite) via l'opérateur d'égalité en une seule. Et l'opérateur d'égalité a sa priorité, qui est supérieure à la priorité de l'opérateur OR au niveau du bit. La fonction est identique à la suivante:
x => (9 +~ x >> 6 / 3 == -x / 3) | 0;
Dans ce cas, un OR au niveau du bit n'a aucun effet, car
true | 0 = 1 . Pour éviter cela, il est nécessaire d'indiquer explicitement dans le corps de la fonction que nous comparons les résultats de deux sous-expressions:
let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0);
Le nombre de solutions a augmenté. Examinons maintenant les graphiques de fonction. Par analogie avec
f1 , une «échelle à degrés» construit une fonction modifiée
f2 :
Les emplacements des graphiques de fonctions se chevauchent, mais nous ne nous intéressons qu'aux points avec une valeur entière de la coordonnée
x : [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15], seulement 12 solutions. L'intersection de deux "échelles" avec les étapes 3 et 4 peut être trouvée par algorithme, si vous le souhaitez.
Question supplémentaire
Dans le problème proposé lors de la conférence, il y avait une question supplémentaire: il était nécessaire de trouver la solution minimale à l'équation 2. Il n'était pas dit que c'était nécessairement un entier, donc la réponse
x = -32 - s'est avérée incorrecte.
Trouver une solution par force brute ne fonctionnera pas ici, mais la résoudre graphiquement est très simple. Il s'agit de la valeur la plus proche de
x à -33 sur la droite:
Il semble que
x = -32. (9). Mais ce n'est toujours pas vrai. Puisque notre environnement est JavaScript, cela signifie que dans la représentation des nombres, nous sommes limités par le type de données utilisé. Le numéro de type est float64,
un nombre à virgule flottante double précision (IEEE 754). Pour s'en souvenir et pour nommer une précision approximative, il suffisait d'obtenir un renard en peluche!
Le côté obscur des opérations au niveau du bit
Comme mentionné ci-dessus, les opérations au niveau du bit convertissent les opérandes en nombres de 32 bits représentés par la séquence 0 et 1 - c'est la plage [-2147483648, 2147483647]. Si le nombre ne rentre pas dedans, alors les bits les plus significatifs seront rejetés.
Dans la première équation, cela ne joue aucun rôle, car il n'y a pas d'opération au niveau du bit sur le côté droit. Mais dans le second, cette conversion des nombres impose un effet intéressant.
Par exemple, le nombre -24 sera représenté par:
11111111111111111111111111101000
Une valeur négative du nombre est obtenue en inversant les bits (NOT au niveau du bit) dans l'enregistrement d'un nombre positif avec l'addition d'un.
Tout nombre en dehors de la plage, après la fin de la conversion dans cette séquence de 32 bits, sera identique dans les opérations binaires au nombre -24. Par exemple, ce sont des chiffres:
4294967272 | 0;
Sur le côté droit de l'équation, avant l'opération au niveau du bit, nous divisons
x par 3. Nous trouvons
x parmi les "équivalents" -24 qui est divisible par 3. Le nombre le plus proche est 12884901864. Remplacez-le dans l'équation:
9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8
Le résultat de la division par 3 (-4294967288) ne correspond pas aux 32 chiffres attribués; lors de l'inversion des bits, le signe est finalement perdu et il ne reste que 8:
00000000000000000000000000001000
De plus, vous pouvez vérifier l'exactitude du résultat en appelant la fonction
eq2 :
eq2(12884901864);
Si vous y réfléchissez, à côté de cette racine, vous pouvez trouver les projections des 11 solutions entières restantes.
Ainsi, un grand nombre de nouvelles solutions apparaissent et seul l'équivalent positif le plus proche de -24 est pris en compte. Néanmoins, ce n'est pas aussi intéressant que la tâche principale, et lors de l'analyse des décisions des participants, ces réponses très rares ont été évaluées séparément. Afin de ne pas être confus, vous pouvez introduire une restriction sur les entiers souhaités dans la condition de problème en tant que ceux signés sur 32 bits.
Et vous ne pouvez pas faire! Ensuite, pour trouver la plus petite racine, vous devez faire attention au voisinage de
Number.MAX_SAFE_INTEGER avec un signe négatif, car ce nombre est entier et avec une précision extrême float64. Eh bien, alors tout seul.
Conclusion
À la suite de la conférence, la plupart des participants ont résolu le problème par une recherche exhaustive, tandis que la plage de recherche était complètement différente pour diverses raisons. Mais comme nous l'avons vu, il suffit de s'écouler à ~ 50 entiers. Beaucoup sont tombés dans des pièges prioritaires opérationnels. Quelqu'un a également décidé graphiquement qu'il était satisfait. Unités surpris par la sortie de 32 catégories. Vous pouvez utiliser la force brute pour avancer davantage dans les tâches. Mais pour obtenir un prix supplémentaire, il fallait encore effectuer une analyse quasi mathématique.
J'espère vraiment que vous avez aimé l'idée d'une tâche aussi atypique que le divertissement pour le format de la conférence. Au cours de la dernière année, j'ai accumulé plusieurs de ces tâches JavaScript "divertissantes". J'ai décidé de les rassembler en un seul endroit. Suivez le lien si vous n'avez pas peur:
JavaScript contesté inattendu . Les tâches de
Look Complex et
Broken Pipe , qui ont également été proposées lors de la conférence, ont déjà été définies. Oui, il existe de nombreuses collections de ce type, mais celle-ci est à moi! Merci encore à tout le monde.