E se pegarmos uma matemática maravilhosa (ou seja, equações lineares) e nosso igualmente maravilhoso
JavaScript , e depois sobrepormos uma à outra? Nas condições de limitações e especificidades do ambiente js, um simples problema matemático pode se transformar em um muito curioso e cheio de armadilhas de js-stones. Na última conferência do
HolyJS 19 em Moscou, uma dessas equações lineares (entre outras tarefas do
SEMrush ) causou um grande
alvoroço .
E sim, este é novamente o título do Entertaining JavaScript: peço que corte todos que se importam.
Obviamente, tudo o que é descrito abaixo - é apenas uma tentativa frívola de simbiose duas coisas maravilhosas para se divertir - não deve ser levado a sério. E esse material não teria existido se não fosse pelo vivo interesse dos participantes da conferência, pelos quais agradecemos especialmente a eles!
Redação
1. Encontre todas as soluções inteiras da equação:
9 +~ x >> 6 / 3 = -x / 3
2. Encontre todas as soluções inteiras da equação:
9 +~ x >> 6 / 3 = -x / 3 | 0
A segunda equação difere da primeira apenas em uma operação adicional no lado direito.
Aproximação matemática
Nos voltamos para a primeira equação. E, para começar, entenderemos as prioridades das operações utilizadas,
conforme a tabela :
(9 +(~ x)) >> (6 / 3) = -x / 3
Pegamos a negação bit a bit de
x e a adicionamos a 9. O resultado da adição é deslocado bit a bit para a direita pelo número de bits igual ao resultado da divisão de 6 por 3.
Obviamente, o problema está no uso de operações bit a bit no
x desejado. Mas, para encontrar alguma raiz condicional para mais raciocínios, vale a pena tentar levar a equação a um análogo matemático aproximado.
As operações bit a bit funcionam com operandos como números inteiros de 32 bits assinados. O NOT bit a bit pode ser substituído por
uma negação de
número inteiro a partir do incremento:
(9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3
O deslocamento bit a bit para a direita (preservando o sinal) pode ser substituído pela divisão
inteira por dois no grau igual ao operando à direita:
(8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3
Obviamente, essas substituições são muito arbitrárias, e falaremos sobre isso mais tarde. E agora temos a equação linear usual, cuja única raiz é -24. Substitua o valor nos lados esquerdo e direito da equação original:
9 +~ (-24) >> 6 / 3;
Ambas as partes são iguais, o que significa que nem tudo é tão desesperador e -24 é realmente uma solução.
Procure os preguiçosos
Se desenharmos gráficos das funções
f1 (x) = (8 -x) / 4 ef2 (x) = -x / 3 , é claro que encontraremos o único ponto de interseção das duas linhas em
x = -24 .
Mas fizemos algumas substituições desiguais com operações bit a bit na expressão esquerda, portanto, na realidade, o gráfico da função
f1 será um pouco diferente. Para qualquer
x, o valor da função será um número inteiro diferente do valor na linha contínua
f1, com uma possível mudança no intervalo de -1 a 1. Isso significa que podemos limitar a área de pesquisa da solução à esquerda e à direita de -24, onde os valores das funções
f1 e
f2 começar a diferir em mais de um.
Para encontrar os limites da área de pesquisa, você pode 1) resolver a desigualdade com o módulo ou 2) examinar mais de perto os gráficos das funções. Veremos que vale a pena analisar
x no segmento [-36, -12]:
| (8 - x) / 4 + x / 3 | <= 1
Para iterar soluções inteiras em um intervalo fechado
[beg, end], escrevemos a função
findx :
const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f);
A função retorna uma matriz de números inteiros para os quais o valor da função passada
f é reduzido para
verdadeiro . Para encontrar soluções, representamos a equação como uma função js usando o operador de igualdade:
let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12);
Assim,
x = [-24, -21, -18, -15] são as soluções desejadas para a primeira equação.
Solução gráfica
A enumeração é obviamente um sucesso, mas ainda vamos descobrir o gráfico da função
f1 até o fim e resolver a equação graficamente. Além disso, a solução não implica a propriedade obrigatória do console do navegador.
O operador NOT bit a bit simplesmente descarta a parte fracionária, assim o resultado
- (x + 1) será arredondado para baixo. O operador de troca de bits é um pouco mais complicado. Nós a substituímos por divisão inteira, mas, dependendo do sinal do número de dividendos, esta operação arredonda o resultado para baixo ou para cima:
10 >> 2;
No entanto, sabemos que o
x desejado está no intervalo [-36, -12]. Conseqüentemente, o operando esquerdo do deslocamento bit a bit (
8 -x ) está no intervalo [20, 44], ou seja, é sempre positivo. O que, por sua vez, significa divisão inteira com arredondamento para baixo.
Depois de descobrir a natureza das operações, podemos desenhar o gráfico correto da função
f1 :
Vamos encontrar quatro pontos de interseção das funções nas mesmas coordenadas
x = [-24, -21, -18, -15].
Segunda equação
Então, chegamos à segunda equação:
9 +~ x >> 6 / 3 = -x / 3 | 0
Difere do primeiro pela adição de um OR bit a bit. Se o operando direito de tal operação for zero, o resultado será simplesmente o valor do operando esquerdo com a parte fracionária descartada.
Para começar, vamos fazer a mesma pesquisa, basta decidir na área de pesquisa. Como agora a função
f2 tem um caractere semelhante a
f1 , para confiabilidade, uma possível mudança deve ser resumida e a pesquisa deve ser limitada onde as funções diferem em valor absoluto em mais de duas unidades - isto é [-48, 0].
let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0);
E nós temos as mesmas respostas. Há uma suspeita de que, afinal, algo está errado. Mas o fato é que, tendo representado a equação original como uma função js, combinamos as duas expressões (esquerda e direita) através do operador de igualdade em uma. E o operador de igualdade tem sua prioridade, que é maior que a prioridade do OR bit a bit. A função é idêntica à seguinte:
x => (9 +~ x >> 6 / 3 == -x / 3) | 0;
Nesse caso, um OR bit a bit não tem efeito, pois
true | 0 = 1 . Para evitar isso, é necessário indicar explicitamente no corpo da função que estamos comparando os resultados de duas subexpressões:
let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0);
O número de soluções aumentou. Agora vamos ver os gráficos de funções. Por analogia com
f1 , uma “escada de mão” constrói uma função modificada
f2 :
Em alguns lugares, os gráficos de funções se sobrepõem, mas estamos interessados apenas em pontos com um valor inteiro de coordenadas
x : [-32, -29, -28, -26, -26, -25, -24, -23, -22, -21, -19, -18, -15], apenas 12 soluções. A interseção de duas "escadas" com as etapas 3 e 4 pode ser encontrada algoritmicamente, se você desejar.
Pergunta adicional
No problema proposto na conferência, havia uma pergunta adicional: era necessário encontrar a solução mínima para a equação 2. Não se dizia que isso era necessariamente um número inteiro; portanto, a resposta
x = -32 - mostrou-se incorreta.
Encontrar uma solução por força bruta não funcionará aqui, mas resolvê-la graficamente é muito simples. Este é o valor mais próximo de
x a -33 à direita:
Parece que
x = -32. (9). Mas isso ainda não é verdade. Como nosso ambiente é JavaScript, isso significa que, na representação de números, somos limitados pelo tipo de dados usado. O número do tipo é float64,
um número de ponto flutuante de precisão dupla (IEEE 754). Lembrar-se disso e nomear precisão aproximada foram suficientes para obter uma raposa de pelúcia!
O lado sombrio das operações bit a bit
Como mencionado acima, as operações bit a bit convertem operandos em números de 32 bits, representados pela sequência 0 e 1 - esse é o intervalo [-2147483648, 2147483647]. Se o número não se encaixar, os bits mais significativos serão descartados.
Na primeira equação, isso não tem nenhum papel, pois não há operação bit a bit no lado direito. Mas no segundo, essa conversão de números impõe um efeito interessante.
Por exemplo, o número -24 será representado como:
11111111111111111111111111101000
Um valor negativo do número é obtido invertendo os bits (NOT bit a bit) no registro de um número positivo com a adição de um.
Qualquer número fora do intervalo, após a conversão terminar nesta sequência de 32 bits, será idêntico em operações binárias ao número -24. Por exemplo, estes são números:
4294967272 | 0;
No lado direito da equação, antes da operação bit a bit, dividimos
x por 3. Encontramos
x entre os "equivalentes" -24 que são divisíveis por 3. O número mais próximo é 12884901864. Substitua-o na equação:
9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8
O resultado da divisão por 3 (-4294967288) não se encaixa nos 32 dígitos alocados; ao inverter bits, o sinal é finalmente perdido e restam apenas 8:
00000000000000000000000000001000
Além disso, você pode verificar a correção do resultado chamando a função
eq2 :
eq2(12884901864);
Se você pensar bem, ao lado desta raiz, você encontrará as projeções das 11 soluções inteiras restantes.
Assim, um grande número de novas soluções aparece e apenas o equivalente positivo mais próximo de -24 é considerado. No entanto, isso não é tão interessante quanto a tarefa principal e, ao analisar as decisões dos participantes, essas respostas muito raras foram avaliadas separadamente. Para não ficar confuso, você pode introduzir uma restrição nos números inteiros desejados na condição do problema, como os de 32 bits assinados.
E você não pode fazer! Em seguida, para encontrar a menor raiz, preste atenção à vizinhança de
Number.MAX_SAFE_INTEGER com um sinal negativo, pois esse número é inteiro e com extrema precisão float64. Bem, então por conta própria.
Conclusão
Como resultado da conferência, a maioria dos participantes resolveu o problema com pesquisa exaustiva, enquanto o alcance da pesquisa foi completamente diferente por vários motivos. Mas, como vimos, basta executar a ~ 50 números inteiros. Muitos caíram em armadilhas de prioridade operacional. Alguém também decidiu graficamente que agradou. Unidades surpreendidas pelo lançamento de 32 categorias. Você pode usar força bruta para avançar ainda mais nas tarefas. Mas, para obter um prêmio adicional, ainda era necessário realizar algumas análises quase matemáticas.
Eu realmente espero que você tenha gostado da ideia de uma tarefa tão atípica como entretenimento para o formato da conferência. No ano passado, acumulei várias tarefas JavaScript "divertidas". Eu decidi colecioná-los todos em um só lugar. Siga o link se você não tiver medo:
JavaScript desafiado inesperado . As tarefas de
Look Complex e
Broken Pipe , que também foram propostas na conferência, já foram definidas. Sim, existem muitas dessas coleções, mas esta é minha! Mais uma vez obrigado a todos.