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 399999999999999, armazena-se 399999999999999 como 3,99999999999999 times 10^{14}. As casas depois da vírgula que não couberem dentro do tamanho estipulado são simplesmente descartadas. E é isso que o google faz2), 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á:

frac{begin{array}{cr} & 19 \ - & 18 end{array}}{begin{array}{cr} = & 1 end{array}}

Bom, 19 em binário é 10011 e 18 é 10010. Ambos tem mais de 4 bits, então eles serão representados como 1,001 times 2^{4} e 1,001 times 2^{4} 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:

frac{ begin{array}{cr} & 1,001_{b} times 2^{4} \ - & 1,001_{b} times 2^{4} end{array} }{ begin{array}{cr} = & 0,000_{b} times 2^{4} end{array} }

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:

frac{ begin{array}{cr} & 1,001_{b} times 2^{4} \ - & 1,000_{b} times 2^{4} end{array} }{ begin{array}{cr} = & 0,001_{b} times 2^{4} end{array} }

Ajustando o expoente temos que 0,001_{b} times 2^{4} = 1_{b} times 2^{1} = 10_{b} , 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, 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.

References

References
1 Eu ia dizer xuxar mas quem não é mineiro não ia entender
2 Ou pelo menos deve fazer
3 Já ouviu falar de zero a esquerda? Pois é, não existe zero a esquerda, e como em binário só existe 0 ou 1…
4 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.

22 thoughts on “Porque o google erra as contas?

  1. @lucas: eu digitei errado! Eu queria dizer que “quem NÃO É mineiro…” não vai entender 😛 Desculpas, já corrigi no texto.

  2. 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!

  3. @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).

  4. 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

  5. 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!

  6. 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?)

  7. 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!

  8. nem é preciso mencionar seus erros de acordo com a NORMA IEEE 754…

    Melhor não, você ia se atolar ainda mais na lama!

  9. 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

  10. 3,99999999999999×10[14] não é 3,99999999999999 e sim 3,9999999999999999999999999999. o certo seria escrever 3,9×10[13].

  11. @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

    1. É uma tradição do exército britânico iniciada em 1791 com o conde de Komeninggen, quando ele abriu o diário de bordo do seu navio aos comentários dos marinheiros. Para que ele pudesse responder cada um deles mas sem divulgar a identidade do comentador, ele criou um sistema que separava o nome e o endereço da pessoa com uma arroba (medida de peso, veja na wikipedia) de carne de boi que deveria ser consumida depois da viagem, numa grande festa. Com o tempo a arroba de carne foi substituída pelo seu símbolo, @, esculpido em madeira. Mas como a escultura de madeira pesava apenas metade do peso da carne, os marinheiros começaram a protestar:
      – É meio, É meio
      Para dizer que o peso estava pela metade. Com o tempo o sistema de endereços criado pelo nobre inglês foi apelidado de “é meio”, e finalmente de “email”, como o conhecemos hoje.

  12. a uma reposta melhor para porque o google erra contas, ele foi programado por humanos, mais simples a resposta ressumindo tudo que ele disse… pra ver como o google erra quaze tudo observe quantas coisas que voce escreve e o google poe um resultado nada a ver, por exemplo ponha download do hal life, vai vir historia do half life.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.