¿Qué pasa si tomamos matemáticas maravillosas (es decir, ecuaciones lineales) y nuestro
JavaScript igualmente maravilloso, y luego superponemos una sobre la otra? En las condiciones de limitaciones y detalles del entorno js, un simple problema matemático puede convertirse en un problema muy curioso y lleno de trampas de piedras js. En la última conferencia
HolyJS 19 en Moscú, una de estas ecuaciones lineales (entre otras tareas de
SEMrush ) causó un
gran revuelo .
Y sí, este es nuevamente el encabezado de Entretenimiento de JavaScript: le pido que elimine a todos los que se preocupan.
Por supuesto, todo lo que se describe a continuación, esto es solo un intento frívolo de simbiosis entre dos cosas maravillosas para divertirse, no debe tomarse en serio. ¡Y este material no habría existido si no hubiera sido por el vivo interés de los participantes de la conferencia, por lo que les agradecemos especialmente!
Redacción
1. Encuentra todas las soluciones enteras de la ecuación:
9 +~ x >> 6 / 3 = -x / 3
2. Encuentre todas las soluciones enteras de la ecuación:
9 +~ x >> 6 / 3 = -x / 3 | 0
La segunda ecuación difiere de la primera solo en una operación adicional en el lado derecho.
Aproximación matemática
Pasamos a la primera ecuación. Y para comenzar, entenderemos las prioridades de las operaciones utilizadas, de
acuerdo con la tabla :
(9 +(~ x)) >> (6 / 3) = -x / 3
Tomamos la negación bit a partir de
x , luego la sumamos a 9. El resultado de la suma se desplaza bit a la derecha por el número de bits igual al resultado de dividir 6 por 3.
Obviamente, el problema radica en el uso de operaciones bit a bit en la
x deseada. Pero para encontrar alguna raíz condicional para un razonamiento adicional, vale la pena intentar llevar la ecuación a un análogo matemático aproximado.
Las operaciones bit a bit funcionan con operandos como enteros de 32 bits con signo. El NOT bit a bit puede ser reemplazado por
una negación
entera del incremento:
(9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3
El desplazamiento bit a la derecha (mientras se preserva el signo) se puede reemplazar por
la división de
enteros por dos en un grado igual al operando a la derecha:
(8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3
Por supuesto, estos reemplazos son muy arbitrarios, y hablaremos de esto más adelante. Y ahora tenemos la ecuación lineal habitual, cuya única raíz es -24. Sustituya el valor en los lados izquierdo y derecho de la ecuación original:
9 +~ (-24) >> 6 / 3;
Ambas partes son iguales, lo que significa que no todo es tan desesperado y -24 es realmente una solución.
Busca a los perezosos
Si dibujamos gráficos de las funciones
f1 (x) = (8 -x) / 4 y
f2 (x) = -x / 3 , entonces, por supuesto, encontramos el único punto de intersección de las dos líneas en
x = -24 .
Pero hicimos un par de sustituciones desiguales con operaciones bit a bit en la expresión izquierda, por lo que en realidad la gráfica de la función
f1 será ligeramente diferente. Para cualquier
x, el valor de la función será un número entero diferente del valor en la línea continua
f1 con un posible cambio en el rango de -1 a 1. Esto significa que podemos limitar el área de búsqueda de solución a la izquierda y derecha de -24, donde los valores de las funciones
f1 y
f2 comienzan a diferir en más de uno.
Para encontrar los límites del área de búsqueda, puede 1) resolver la desigualdad con el módulo, o 2) observar más de cerca los gráficos de las funciones. Encontraremos que vale la pena mirar
x en el segmento [-36, -12]:
| (8 - x) / 4 + x / 3 | <= 1
Para iterar sobre soluciones completas en un rango cerrado
[beg, end], escribimos la función
findx :
const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f);
La función devuelve una matriz de enteros para los cuales el valor de la función pasada
f se reduce a
verdadero . Para encontrar soluciones, representamos la ecuación como una función js usando el operador de igualdad:
let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12);
Por lo tanto,
x = [-24, -21, -18, -15] son las soluciones deseadas para la primera ecuación.
Solución gráfica
La enumeración es, por supuesto, un éxito, pero aún así descubramos la gráfica de la función
f1 hasta el final y resolvamos la ecuación gráficamente. Además, la solución no implica la propiedad obligatoria de la consola del navegador.
El operador NOT a nivel de bits simplemente descarta la parte fraccionaria, por lo tanto, el resultado
- (x + 1) se redondeará hacia abajo. El operador de desplazamiento de bits es un poco más complicado. Lo reemplazamos con división entera, pero dependiendo del signo del número de dividendo, esta operación redondea el resultado hacia abajo o hacia arriba:
10 >> 2;
Sin embargo, sabemos que la
x deseada está en el rango [-36, -12]. En consecuencia, el operando izquierdo del desplazamiento a nivel de bits (
8 -x ) está en el rango [20, 44], es decir, siempre es positivo. Lo que a su vez significa división entera con redondeo hacia abajo.
Habiendo descubierto la naturaleza de las operaciones, podemos dibujar la gráfica correcta de la función
f1 :
Encontraremos cuatro puntos de intersección de las funciones en las mismas coordenadas
x = [-24, -21, -18, -15].
Segunda ecuación
Entonces, llegamos a la segunda ecuación:
9 +~ x >> 6 / 3 = -x / 3 | 0
Se diferencia del primero por la adición de un OR bit a bit. Si el operando derecho de tal operación es cero, entonces el resultado es simplemente el valor del operando izquierdo con la parte fraccionaria descartada.
Para comenzar, pasemos por la misma búsqueda, solo decida el área de búsqueda. Dado que ahora la función
f2 tiene un carácter similar con
f1 , para mayor confiabilidad, el posible cambio debe resumirse y la búsqueda debe limitarse donde las funciones difieren en valor absoluto en más de dos unidades, esto es [-48, 0].
let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0);
Y obtuvimos las mismas respuestas. Existe la sospecha de que, después de todo, algo está mal. Pero el hecho es que habiendo representado la ecuación original como tal función js, combinamos las dos expresiones (izquierda y derecha) a través del operador de igualdad en una sola. Y el operador de igualdad tiene su prioridad, que es mayor que la prioridad del OR bit a bit. La función es idéntica a la siguiente:
x => (9 +~ x >> 6 / 3 == -x / 3) | 0;
En este caso, un OR bit a bit no tiene efecto, ya que
true | 0 = 1 . Para evitar esto, es necesario indicar explícitamente en el cuerpo de la función que estamos comparando los resultados de dos subexpresiones:
let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0);
El número de soluciones ha aumentado. Ahora echemos un vistazo a los gráficos de funciones. Por analogía con
f1 , una "escalera de mano" construye una función modificada
f2 :
Los gráficos de lugares de funciones se superponen entre sí, pero solo nos interesan los puntos con un valor entero de la coordenada
x : [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15], solo 12 soluciones. La intersección de dos "escaleras" con los pasos 3 y 4 se puede encontrar algorítmicamente, si lo desea.
Pregunta adicional
En el problema propuesto en la conferencia había una pregunta adicional: era necesario encontrar la solución mínima para la ecuación 2. No se dijo que esto fuera necesariamente un número entero, por lo que la respuesta
x = -32 - resultó ser incorrecta.
Encontrar una solución por fuerza bruta no funcionará aquí, pero resolverlo gráficamente es muy simple. Este es el valor más cercano
x a -33 a la derecha:
Parece que
x = -32. (9). Pero esto aún no es cierto. Dado que nuestro entorno es JavaScript, significa que en la representación de números estamos limitados por el tipo de datos utilizado. El número de tipo es float64,
un número de coma flotante de doble precisión (IEEE 754). ¡Recordar esto y nombrar una precisión aproximada fue suficiente para obtener un zorro de peluche!
El lado oscuro de las operaciones bit a bit
Como se mencionó anteriormente, las operaciones bit a bit convierten los operandos a números de 32 bits representados por la secuencia 0 y 1; este es el rango [-2147483648, 2147483647]. Si el número no cabe, entonces los bits más significativos serán descartados.
En la primera ecuación, esto no juega ningún papel, ya que no hay operación bit a bit en el lado derecho. Pero en el segundo, esta conversión de números impone un efecto interesante.
Por ejemplo, el número -24 se representará como:
11111111111111111111111111101000
Se obtiene un valor negativo del número invirtiendo (NO bit a bit) en el registro de un número positivo con la suma de uno.
Cualquier número fuera del rango, después de la conversión que termina en esta secuencia de 32 bits, será idéntico en operaciones binarias al número -24. Por ejemplo, estos son números:
4294967272 | 0;
En el lado derecho de la ecuación, antes de la operación bit a bit, dividimos
x entre 3. Encontramos
x entre los "equivalentes" -24 que es divisible por 3. El número más cercano es 12884901864. Sustitúyalo en la ecuación:
9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8
El resultado de dividir por 3 (-4294967288) no cabe en los 32 dígitos asignados; al invertir bits, el signo finalmente se pierde y solo quedan 8:
00000000000000000000000000001000
Además, puede verificar la exactitud del resultado llamando a la función
eq2 :
eq2(12884901864);
Si lo piensa, al lado de esta raíz puede encontrar las proyecciones de las 11 soluciones enteras restantes.
Por lo tanto, aparece una gran cantidad de nuevas soluciones, y solo se considera el equivalente positivo más cercano de -24. Sin embargo, esto no es tan interesante como la tarea principal, y al analizar las decisiones de los participantes, estas respuestas muy raras se evaluaron por separado. Para no confundirse, puede introducir una restricción en los enteros deseados en la condición del problema como los firmados de 32 bits.
Y no puedes hacer! Luego, para encontrar la raíz más pequeña, debe prestar atención a la vecindad de
Number.MAX_SAFE_INTEGER con un signo negativo, ya que este número es entero y con extrema precisión float64. Bueno, entonces por tu cuenta.
Conclusión
Como resultado de la conferencia, la mayoría de los participantes resolvieron el problema mediante una búsqueda exhaustiva, mientras que el rango de búsqueda fue completamente diferente por varias razones. Pero como vimos, es suficiente correr a ~ 50 enteros. Muchos cayeron en trampas prioritarias operativas. Alguien también decidió gráficamente que complacido. Unidades sorprendidas por el lanzamiento de 32 categorías. Podrías usar la fuerza bruta para avanzar más en las tareas. Pero para obtener un premio adicional, aún era necesario realizar un análisis casi matemático.
Realmente espero que les haya gustado la idea de una tarea tan atípica como el entretenimiento para el formato de conferencia. Durante el año pasado, acumulé varias tareas de JavaScript "entretenidas". Decidí recogerlos todos en un solo lugar. Siga el enlace si no tiene miedo:
JavaScript desafiado inesperado . Las tareas de
Look Complex y
Broken Pipe , que también se propusieron en la conferencia, ya se han presentado. Sí, hay muchas de esas colecciones, ¡pero esta es mía! Gracias de nuevo a todos.