Tag: matemática

O Joel mandou um mail hoje perguntando:

Tem alguma boa explicação pra 399999999999999-399999999999998 no google retornar 0?
se 399999999999999-399999999999997 é igual a 2 e 399999999999999-399999999999999 é igual a zero (por sinal, como deveria).

Pro que eu respondi, assim por alto:

Erro de precisão. Ele não trabalha com precisão arbitrária (número infinito de dígitos) e converte isso daí pra:

(3,99999999999999 * 10^14)  – (3,99999999999998 * 10^14), e representa esses caras em binário, com, digamos 32 bits. Aí, em binário, a diferença entre esses caras fica na 33a casa, mas a diferença entre 399999999999999 – 399999999999997 fica ainda na 32a (a diferença é o dobro, logo, uma casa antes em binário 🙂 ).

Por isso o primeiro dá errado e o segundo não.

No email eu dei uma resposta até curta, porque não achei que fosse algo tão importante! Mas em pouco tempo a jess me manda no google chat:

5:18 PM jess.listas: Obrigada =)

5:19 PM me: por?

jess.listas: Relevar o grande mistério da humanidade. Me encaminharam um e-mail seu explicando porque o google erra em algumas contas com numeros grandes

Não sabia que a repercussão da minha resposta ia ser tão grande, então resolvi logo escrever um post a respeito. O Problema que acontece com o google chama-se:

Erro de precisão

E pode acontecer com qualquer um… Quer dizer… Com qualquer sistema digital. O lance é o seguinte: Computadores, e sistemas digitais em geral, representam o número usando bits. Cada sistema pode ter seu padrão, mas o número de bits que se reserva pra representar um número é limitado. Já ouviu falar de sistemas de 16, 32 ou 64 bits? Pois então, esses são os tamanhos que são reservados para armazenar um número inteiro. Em geral, se você tenta enfiar¹⁾ um número maior que isso dentro do inteiro, ele simplesmente não aceita e dá erro. Outros sistemas simplesmente ignoram o erro e “comem” um pedaço do número, e você fica com um “restolho” inútil que não te serve pra nada, sem nem mesmo saber disso.

Pra evitar esses problemas, ao invés de usar números inteiros, alguns sistemas usam “números de ponto flutuante”, ou “números reais”. Ao invés de armazenar 399999999999999 como , armazena-se 399999999999999 como . As casas depois da vírgula que não couberem dentro do tamanho estipulado são simplesmente descartadas. E é isso que o google faz²⁾, e é por isso que vemos esses erros. Pra dar um exemplo prático, vamos usar um sistema com, digamos, 4 bits. Nesse sistema, vamos subtrair alguns números e ver no que dá:

Bom, 19 em binário é 10011 e 18 é 10010. Ambos tem mais de 4 bits, então eles serão representados como e respectivamente. Mas, veja bem! Ao eliminar os últimos bits, eu eliminei exatamente o que os números tinham de diferente. Agora ao efetuar a subtração tenho:

Aí vem a outra pergunta:

Porque então 399999999999999-399999999999997 deu a resposta certa?

Essa pode parecer mais difícil, mas tem exatamente a mesma explicação. em binário, 2 ocupa uma casa a mais do que 1: 2 em binário se escreve 10 enquanto 1 se escreve apenas 1. Isso quer dizer que, se eu estou “no limite” de casas decimais, o número 2 consegue ficar dentro da minha precisão, enquanto o número 1 já não consegue mais. Com o nosso exemplo, usemos 17 ao invés de 19. Bom, 17 em binário é 10001, e nossa conta com 4 bits fica assim:

Ajustando o expoente temos que , ou seja, 2.

Então, munidos dessa informação, podemos viajar ainda mais e descobrir

Quantos bits o Google usa para representar números reais?

Como vamos fazer isso? simples. Sabemos que 399999999999999-399999999999998 dá erro, enquanto 399999999999999-399999999999997 não dá. Com isso sabemos que 399999999999999 tem exatamente um único bit a mais do que a precisão que o google usa. Basta então descobrirmos quantos bits a representação binária de 399999999999999 usa, e esse será nosso npumero mágico de bits. Então vamos lá. Segundo minha calculadora do linux, 399999999999999₁₀ = 101101011 1100110001 0000011110 1000111111 1111111111₂. Contando os bits temos 49 bits. Parece um número estranho, afinal eu falei de 16, 32 e 64. De onde veio esse 49?

Bem, em primeiro lugar, o bit mais significativo (i.e. o bit mais a esquerda) não precisa ser armazenado: ele é sempre 1³⁾. Assim, baixamos pra 48. Um número par pelo menos, mas cadê o resto? Bom, a potência que eu representei antes “a parte” precisa ser armazenada em algum lugar. Os bits que faltam pra completar 64 são os bits que eu uso pra armazenar o expoente, ou potência. Assim, 48 bits representam a “mantissa” e os 16 bits restantes representam o expoente⁴⁾.

Conclusão

Não sei bem que conclusão tirar do fato de termos apenas 48 bits. Preciso estudar melhor o padrão IEEE 754 pra entender isso. De qualquer forma, uma conclusão fica latente:

A calculadora do google não usa python!!!

Isso porque, em python os números tem precisão infinita, e essa conta ficaria assim:

>>> print 399999999999999-399999999999998
1

Então, fica a sugestão para os desenvolvedores da calculadora do google: usem python ou alguma biblioteca de precisão arbitrária, para, pelo menos, não confundir os usuários.