Este loop 'para' pára e por que / por que não? para (var i = 0; 1 / i> 0; i ++) {}

104

Este forloop nunca para?

for (var i=0; 1/i > 0; i++) {
}

Em caso afirmativo, quando e por quê? Disseram-me que parava, mas não me deram razão para isso.

Upddate

Como parte da investigação, escrevi um artigo bastante longo e detalhado que explica tudo o que está acontecendo nos bastidores - Aqui está o que você precisa saber sobre o tipo de número do JavaScript

javascript Max Koretskyi
fonte
5
Não vai parar. tente executar este pedaço de código. para (var i = 0; 1 / i> 0; i ++) {console.log (i)}
Sourabh Agrawal
3
Relevante: Calcule o tempo necessário para quebrar a chave AES , de Segurança da Informação , originalmente de Schneier sobre Segurança .
Kobi de
3
Number.MAX_VALUE + 9.979202e291 == "Infinity" e 1 / (NaN ou 'Infinity' ou 'undefined')> 0 == false.
askeet de
6
O Javascript irá ignorar esse loop porque não contém instruções? ou seja, otimizá-lo? Eu sei que existem algumas linguagens compiladas que sim.
Brian J de
3
@askeet, como gotnull e outros apontam abaixo, nunca alcançamos o Infinity incrementando repetidamente, em vez de sermos pegos em um loop depois Number.MAX_SAFE_INTEGER + 1.
LSpice de

Respostas:

128

(Não sou fã de meta-conteúdo, mas: as respostas de gotnull's e le_m's estão corretas e úteis. Elas eram originalmente, e são ainda mais com as edições feitas depois que este Community Wiki foi postado. A motivação original para este CW desapareceu em grande parte como resultado dessas edições, mas continua útil, então ... Além disso: Embora haja apenas alguns autores listados, muitos outros membros da comunidade ajudaram muito com os comentários que foram dobrados e limpos. não é apenas um CW no nome.)

O loop não para em um mecanismo JavaScript implementado corretamente. (O ambiente de host do mecanismo pode eventualmente encerrá-lo porque é infinito, mas isso é outra coisa.)

Aqui está o porquê:

  1. Inicialmente, quando ié 0, a condição 1/i > 0é verdadeira porque em JavaScript, 1/0é Infinitye Infinity > 0é verdadeiro.

  2. Depois disso, iserá incrementado e continuará a crescer como um valor inteiro positivo por um longo tempo (mais 9.007.199.254.740.991 iterações). Em todos esses casos, 1/ipermanecerá > 0(embora os valores de 1/ifiquem muito pequenos no final!) E assim o loop continua até e incluindo o loop onde iatinge o valor Number.MAX_SAFE_INTEGER.

  3. Os números em JavaScript são de ponto flutuante binário de precisão dupla IEEE-754, um formato bastante compacto (64 bits) que fornece cálculos rápidos e uma vasta gama. Ele faz isso armazenando o número como um bit de sinal, um expoente de 11 bits e um significando de 52 bits (embora, por meio da inteligência, ele na verdade obtenha 53 bits de precisão). É ponto flutuante binário (base 2): o significando (mais alguma inteligência) nos dá o valor, e o expoente nos dá a magnitude do número.

    Naturalmente, com tantos bits significativos, nem todos os números podem ser armazenados. Aqui está o número 1 e o próximo número mais alto depois de 1 que o formato pode armazenar, 1 + 2 -52 ≈ 1.00000000000000022, e o próximo número mais alto depois desse 1 + 2 × 2 -52 ≈ 1.00000000000000044:

       + ------------------------------------------------- -------------- bit de sinal
  / + ------- + ---------------------------------------- -------------- expoente
 / / | + ------------------------------------------------- + - significando
/ / | / |
0 01111111111 0000000000000000000000000000000000000000000000000000
                = 1
0 01111111111 0000000000000000000000000000000000000000000000000001
                ≈ 1.00000000000000022
0 01111111111 0000000000000000000000000000000000000000000000000010
                ≈ 1.00000000000000044

    Observe o salto de 1.00000000000000022 para 1.00000000000000044; não há como armazenar 1.0000000000000003. Isso também pode acontecer com inteiros: Number.MAX_SAFE_INTEGER(9.007.199.254.740.991) é o valor inteiro positivo mais alto que o formato pode conter, onde ie i + 1são ambos representáveis ​​exatamente ( especificação ). Ambos 9.007.199.254.740.991 e 9.007.199.254.740.992 podem ser representados, mas o próximo número inteiro, 9.007.199.254.740.993, não pode; o próximo número inteiro que podemos representar após 9.007.199.254.740.992 é 9.007.199.254.740.994. Aqui estão os padrões de bits, observe o bit mais à direita (menos significativo):

       + ------------------------------------------------- -------------- bit de sinal
  / + ------- + ---------------------------------------- -------------- expoente
 / / | + ------------------------------------------------- + - significando
/ / | / |
0 10000110011 111111111111111111111111111111111111111111111111111111
                = 9007199254740991 (Number.MAX_SAFE_INTEGER)
0 10000110100 00000000000000000000000000000000000000000000000000000000
                = 9007199254740992 (Número.MAX_SAFE_INTEGER + 1)
x xxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
                  9007199254740993 (Number.MAX_SAFE_INTEGER + 2) não pode ser armazenado
0 10000110100 0000000000000000000000000000000000000000000000000001
                = 9007199254740994 (Número.MAX_SAFE_INTEGER + 3)

    Lembre-se de que o formato é de base 2 e, com esse expoente, o bit menos significativo não é mais fracionário; tem um valor de 2. Pode ser desativado (9.007.199.254.740.992) ou ativado (9.007.199.254.740.994); então, neste ponto, começamos a perder a precisão mesmo na escala de número inteiro (inteiro). O que tem implicações para o nosso loop!

  4. Depois de completar o i = 9,007,199,254,740,992loop, i++dá-nos ... i = 9,007,199,254,740,992novamente; não há alteração em i, porque o próximo inteiro não pode ser armazenado e o cálculo acaba sendo arredondado para baixo. imudaria se o fizéssemos i += 2, mas i++não podemos mudar. Assim, alcançamos o estado estacionário: inunca muda e o loop nunca termina.

Aqui estão os vários cálculos relevantes:

if (!Number.MAX_SAFE_INTEGER) {
  // Browser doesn't have the Number.MAX_SAFE_INTEGER
  // property; shim it. Should use Object.defineProperty
  // but hey, maybe it's so old it doesn't have that either
  Number.MAX_SAFE_INTEGER = 9007199254740991;
}
var i = 0;
console.log(i, 1/i, 1/i > 0); // 0, Infinity, true
i++;
console.log(i, 1/i, 1/i > 0); // 1, 1, true
// ...eventually i is incremented all the way to Number.MAX_SAFE_INTEGER
i = Number.MAX_SAFE_INTEGER;
console.log(i, 1/i, 1/i > 0); // 9007199254740991 1.1102230246251568e-16, true
i++;
console.log(i, 1/i, 1/i > 0); // 9007199254740992 1.1102230246251565e-16, true
i++;
console.log(i, 1/i, 1/i > 0); // 9007199254740992 1.1102230246251565e-16, true (no change)
console.log(i == i + 1);      // true
Expandir trecho

TJ Crowder
fonte
79

Responda:

A condição 1/i > 0sempre será avaliada como verdadeira:

  • Inicialmente, é verdade porque 1/0avalia Infinitye Infinity > 0é verdadeiro

  • Permanece verdadeiro, pois 1/i > 0é verdadeiro para todos i < Infinitye i++nunca atinge Infinity.

Por que i++nunca chega Infinity? Devido à precisão limitada do Numbertipo de dados, há um valor para o qual i + 1 == i:

9007199254740992 + 1 == 9007199254740992 // true

Depois de iatingir esse valor (que corresponde a ), ele permanecerá o mesmo mesmo depois .Number.MAX_SAFE_INTEGER + 1i++

Portanto, temos um loop infinito.

Apêndice:

Porque é 9007199254740992 + 1 == 9007199254740992?

O Numbertipo de dados do JavaScript é, na verdade, um flutuante de precisão dupla IEEE 754 de 64 bits . Cada um Numberé desmontado e armazenado em três partes: sinal de 1 bit, expoente de 11 bits e mantissa de 52 bits. Seu valor é -1 sinal × mantissa × 2 expoente .

Como 9007199254740992 é representado? Como 1,0 × 2 53 ou em binário:

insira a descrição da imagem aqui

Incrementando o bit menos significativo da mantissa, obtemos o próximo número mais alto:

insira a descrição da imagem aqui

O valor desse número é 1.00000000000000022… × 2 53 = 9007199254740994

O que isso significa? Numberpode ser 900719925474099 2 ou 900719925474099 4 , mas nada no meio.

Agora, qual escolheremos para representar 900719925474099 2 + 1 ? As regras de arredondamento IEEE 754 fornecem a resposta: 900719925474099 2 .

le_m
fonte
9
curta e correta, melhor do que a resposta aceita atualmente
AlexWien
@AlexWien A resposta aceita é uma resposta aceita pelo wiki da comunidade.
fulvio
2
Não conheço a resposta do termo "comunidade wiki aceita". O que isso tem a ver com stackoverflow? Se este for um link externo, um link deve ser fornecido. Respostas aceitas em stackoverflow podem sempre mudar, o status aceito não é final.
AlexWien
"Por que i ++ nunca atinge o infinito? Devido à precisão limitada do tipo de dados Número ..." <- Certamente ele nunca alcançaria o infinito, mesmo com um tipo de número de precisão infinita .. Você sabe, porque você não pode contar até infinito: P
Blorgbeard foi lançado em
1
@Blorgbeard Você pode contar até o infinito com duplas de precisão limitada, você só precisa incrementar por um número muito maior do que 1, por exemplo for (var i = 0; i < Infinity; i += 1E306);. Mas eu entendi de onde você está vindo;)
le_m
27

A Number.MAX_SAFE_INTEGERconstante representa o número inteiro seguro máximo em JavaScript. A MAX_SAFE_INTEGERconstante tem um valor de 9007199254740991. O raciocínio por trás desse número é que o JavaScript usa números de formato de ponto flutuante de precisão dupla conforme especificado no IEEE 754 e só pode representar com segurança números entre - (2 53 - 1) e 2 53 - 1.

Seguro neste contexto refere-se à capacidade de representar inteiros exatamente e compará-los corretamente. Por exemplo, Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2irá avaliar para true, o que é matematicamente incorreto. Veja Number.isSafeInteger()para mais informações.

Por MAX_SAFE_INTEGERser uma propriedade estática de Number, você sempre a usa como Number.MAX_SAFE_INTEGER, e não como uma propriedade de um Numberobjeto que criou.

ATUALIZAR:

Alguém em uma resposta que foi deletada mencionou: inunca alcançará o infinito. Quando atinge Number.MAX_SAFE_INTEGER, i++não incrementa mais a variável. Na verdade, isso não é correto.

@TJ Crowder comenta que i = Number.MAX_SAFE_INTEGER; i++; i == Number.MAX_SAFE_INTEGER;é false. Mas a próxima iteração atinge um estado imutável, então a resposta principal está correta.

ino exemplo nunca chega Infinity.

Fúlvio
fonte
2
Especificamente, 9007199254740992 + 1é 9007199254740992.
Kobi de
1
@GerardoFurtado Eu imagino que sim.
fulvio de
1
@GerardoFurtado for (var i=0; NaN > 0; i++) { console.log(i); }não vai produzir nada.
fulvio de
2
@GerardoFurtado: Nesse caso, o loop parava. O corpo do loop nunca seria inserido, já que o primeiro test ( 1/i > 0) seria falso, pois if ié 0, 1/ié NaNe NaN > 0é falso.
TJ Crowder de
1
@TJCrowder Eu atualizei minha resposta. Obrigado por apontar isso!
fulvio