Porque o google erra as contas?
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 enfiar1 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 
Bom, 19 em binário é 10011 e 18 é 10010. Ambos tem mais de 4 bits, então eles serão representados como 
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 
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, 39999999999999910 = 101101011 1100110001 0000011110 1000111111 11111111112. 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 13. 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 expoente4.
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.
- Eu ia dizer xuxar mas quem não é mineiro não ia entender
- Ou pelo menos deve fazer
- Já ouviu falar de zero a esquerda? Pois é, não existe zero a esquerda, e como em binário só existe 0 ou 1…
- Como esses valores não correspondem ao padrão da IEEE eu suponho que por algum acaso ou mistério da natureza, os números não estão sendo normalizados como deveriam, e por isso usam menos do que os 52 bits do padrão.
Comments
17 Comments on Porque o google erra as contas?
-
carlos on
Mon, 1st Sep 2008 10:19
-
lucas on
Mon, 1st Sep 2008 11:47
-
Girino Vey on
Mon, 1st Sep 2008 11:54
-
gabriel on
Tue, 2nd Sep 2008 5:30
-
Girino Vey on
Tue, 2nd Sep 2008 8:23
-
gabriel on
Tue, 2nd Sep 2008 19:04
-
gabriel on
Tue, 2nd Sep 2008 19:30
-
Girino Vey on
Tue, 2nd Sep 2008 22:02
-
gabriel on
Wed, 3rd Sep 2008 3:53
-
gabriel on
Wed, 3rd Sep 2008 4:18
-
Maysa on
Thu, 4th Sep 2008 20:07
-
mirna on
Fri, 19th Sep 2008 21:17
-
Daniel on
Wed, 31st Dec 2008 17:17
-
lucas on
Fri, 30th Jan 2009 2:35
-
joana on
Thu, 26th Feb 2009 10:55
-
Girino Vey on
Thu, 26th Feb 2009 11:32
-
Marckye on
Thu, 3rd Sep 2009 14:41
@lucas: eu digitei errado! Eu queria dizer que “quem NÃO É mineiro…” não vai entender 
Desculpas, já corrigi no texto.
Ops! Acredito q vc está equivocado. resposta: não estou não, leia o próximo comentário
Segundo sua especulação o erro estaria no primeiro bit,
no caso da subtração 39…999 – 39…995 a diferença se encontra, inclusive, no primeiro bit e a operação devolve o resultado correto, 4.
9 em decimal – 1001 em binário
8 em decimal – 1000 em binário
7 em decimal – 0111 em binário
6 em decimal – 0110 em binário
5 em decimal – 0101 em binário
Sem um debugger não tem como explicar onde está se perdendo essa unidade.
E tem outra, 2^49 -1, ou seja, todas as combinações que contêm na 49º casa o número 1, chega até 562.949.953.421.311, que excede em 162.949.953.421.312 o valor que estamos usando, 399.999.999.999.999. Isso seria justamente 49 bits usados como 48, sendo o primeiro digito sempre um. Dificilmente alguém usaria desse raciocínio para acrescentar complexidade a um algoritmo matemático.
descobri q o google está perdendo essa unidade em qualquer operação cujo resultado seja UM e o minuendo seja igual ou maior que 333333333333335. ou seja 3…334 – 3…333 = 1, OK. 3…335 – 3…334 = 0, ERRADO.
abs!
@gabriel: 4 em binário é 100, então a diferença está no TERCEIRO bit, não no primeiro.
Sobre o comentário de “Isso seria justamente 49 bits usados como 48, sendo o primeiro digito sempre um. Dificilmente alguém usaria desse raciocínio para acrescentar complexidade a um algoritmo matemático.”:
Leia a norma da IEEE linkada no artigo. É assim que é feito em QUALQUER sistema de ponto flutuante. Nesses casos ESPAÇO é mais importante que tempo, logo a eliminação de um bit implícito é muito mais vantajosa do que o tempo ganho por se facilitar o cálculo. (além do que, acrescentar esse bit ao desempacotar o número é uma operação trivial de “AND” em um único bit, não acrescenta acrescenta nem um milésimo de centavo ao custo do processador).
Ok, mas se nos elementos da subtração ele conta com o primeiro bit, porque no resultado ele não contaria?
tenta com 3..999 – 3.996 que o resultado está correto, 3. todos os elementos, minuendo, subtraento e resposta (diferença) estão com o primeiro bit UM.
o que eu quis lhe dizer com 49 bits usados como 48, é que ele só passaria a usar o 50º bit (um a mais que o implicito, segundo sua teoria) quando o valor superasse 562.949.953.421.311. Aí sim ele supostamente descartaria o primeiro.
E tem outra, vc vai precisar de algum outro bit para informar SE o último bit (o 49º) é UM ou ZERO, ou até um byte para descrever a quantidade de bits usados em CADA operação de preenchimento na memória, para poder colocar sempre um UM na última casa se necessário! Um boom na economia de espaço e organização do algoritmo. O processador n tem como descobrir isso!! Um exemplo, não teria como distinguir o número 1.024 de 281.474.976.711.680. A única diferença entre os dois está no 49º bit, um é ZERO e outro é UM.
abs!
você viajou tanto, mas tanto na maionese que nem ficou compreensível o que você disse! Leia a Norma da IEEE e você vai entender o do que se trata o bit implicito e como se opera com ele. Ah, e vocÊ anda confundindo “direita” com “esquerda” o bit implícito fica à ESQUERDA e não a direita
Cara, você que chama o último bit de primeiro bit.
Último -> 1000001 <- Primeiro. Pensei que n fosse necessário explanar sobre isso.
Releia seu post e os meus comentários.
Deixarei como está. Vai ser inútil insistir.
Só recomendo cautela.
Abs!
E eu recomendo estudo. Você confundiu duas partes do artigo que não tem nada a ver uma com a outra: O erro de precisão (primeira parte) e o bit implícito, parte da norma IEEE754, citado ao final do artigo. Ao misturar os dois, você “colocou na minha boca” palavras que eu não disse, e tentou provar que uma coisa que eu nunca disse, estava errada.
Por último você tentou argumentar que o bit implícito, parte da norma IEEE 754, adotata internacionalmente desde 1985, estivesse errado. Ora, se não entendeu, pergunte, não tente negar!
Seus comentários não fazem sentido por confundirem duas partes disjuntas do texto e por falta de conhecimento prévio do assunto.
Então, eu da minha parte, recomendo além de cautela ao discutir assuntos sobre os quais não conhece, humildade, pra evitar falar merda e passar esse tipo de vexame!
E pra quem não entendeu o erro do gabriel quando ele diz que:
> não teria como distinguir o número 1.024 de
> 281.474.976.711.680. A única diferença entre os dois está no
> 49º bit, um é ZERO e outro é UM.
Ele não prestou atenção que:
1- o processador usa DUAS partes, um expoente e uma mantissa.
2- o bit implícito é SEMPRE 1.
Assim, o numero 1024 é representado como:
expoente: 2^10
mantissa: 000…000000000000 (só zeros, o primeiro um implícito)
enquanto o outro numero dele é representado como:
expoente: 2^49
mantissa: 000…1000000000 (tem um um não implícito no meio, tá vendo?)
Caro Girino Véi!
me parece ser muito novo ou leigo.
tenho pouca, mas, alguma prática em assembly.
vc desconhece do assunto, então n poste coisas desse tipo!
conselho que te dou sem te chamar de um MERDA! (sobre esse assunto)
tentei evitar, mas vc quem implorou.
o post está aí, e os comments também, quem quiser confira!
sem raivas,
abs!
Bom, mais uma vez, falando besteiras Isso não tem nada a ver com assembly, e sim com representação numérica em sistemas digitais. Se você tem “alguma prática” com assembly, já explica bastante seus erros: você não tem uma formação de engenharia elétrica ou de teoria da computação. Seus erros são compreensíveis do ponto de vista de um “programador assembly”.
Lembre-se que os comments estão aí porque me divertem! Eu posso apagá-los quando bem entender, então só deixo eles aí pra te humilhar bastante (sim, eu sou malvado).
E me chamar de MERDA, vindo de um programador assembly, é um elogio sem tamanho, você nem imagina!
Obrigado, por fim, por diminuir minha idade. Chute por favor um valor, pra eu ficar BEM feliz!
Agora a piada do dia foi o “tentei evitar” tentou nada! Está fazendo tudo pra aparecer, tirando teorias do rabo e contestando coisas aceitas desde antes de você nascer sem a menor base teórica. Nem ler direito parece que não sabe! (Ah, desculpa, não precisa saber ler pra programar assembly).
Programador assembly! Huhauhauahuah boa! Muito boa!
nem é preciso mencionar seus erros de acordo com a NORMA IEEE 754…
Melhor não, você ia se atolar ainda mais na lama!
eta
como nao entendo praga nenhuma dos assuntos citados acima, exceto o que foi explicado, o minimo que posso fazer é parabeniza-lo pelo seu trabalho, pelo blog e pelo estudo que vc fez em cima do assunto para poder escrever essa aula. Acho até mesmo que o google deveria considerar sua explicaçao e adota-la.
Quanto ao debate, ficou clara a sua vitoria
parabéns cara, continue estudando e trabalhando, pois pelo que li, voce eh 1 excelente profissional.
abraço
3,99999999999999×10[14] não é 3,99999999999999 e sim 3,9999999999999999999999999999. o certo seria escrever 3,9×10[13].
@joana
Juro que não entendi seu comentário. Primeiro vou considerar que você usou a vírgula em “3,9999999999999999999999999999″ sem querer e queria na verdade dizer “39999999999999999999999999999″. Bem, note que 39999999999999999999999999999 tem 29 dígitos, e não 15, logo usando notação em potências de 10 ele seria escrito:
3,9999999999999999999999999999 x 1028.
Quanto à 3,9×1013, ele seria escrito, sem potência de 10, assim:
39000000000000
Ham.. agora entendi… você interpretou a potência de 10 como sendo a repetição do último dígito (nem sei se existe notação própria pra isso). Para entender melhor o que escrevi, leia:
http://pt.wikipedia.org/wiki/Nota%C3%A7%C3%A3o_cient%C3%ADfica
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!
Blog aggregators
