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

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.

Knol, ou uma enxurada de girinadas.

O google lançou o seu complemento/concorrente da wikipédia: knol!

É tudo que um girino pediu a Deus! Nada de fontes, referências, ponto de vista neutro, o escambau aquático! É simplesmente um repositório de conhecimento, QUALQUER UM! Quer lugar melhor pras minhas girinadas? Pois já comecei por lá: escrevi um artiguinho sobre a Lilica Westies, copiei pra lá sem tirar nem por meu tutorial de fractais, e o que eu gastei mais tempo: um artigão, em inglês, introdutório sobre compressão de dados. (Essa foto aí do lado é uma das ilustrações toscas que eu fiz pro artigo 😉 ) Quem animar, dê uma olhada:

moro de favor meu filho pode me visitar

Hoje estou de mal humor! Por isso vou escrachar com essa frase usada nos mecanismos de busca!



A resposta simples é:

  • Não, nem fodeno[foot]segundo o adestrador da Lilica "nem fodeno" é coisa de mineiro. Será? Alguém de outro estado (des)confirma isso?[/foot]

A resposta mais complicada é:

  • Porra, tu não sabe escrever não?[foot]O erro de concordância foi proposital, viu?[/foot] Não sabe fazer busca no google não? Que espécie de animal é você? Acha que o google não tem sentimentos? Que ele não liga pra pontuação?

Bah, nem foi tão desopilante assim 🙁 Vou ter de zoar com a cara de mais alguém mais tarde.

Balanço geral das frases buscadas...

Pois é...

lá fui eu olhar o que tinha dado. Categorizei, de forma manual mesmo, as buscas em grandes grupos (no total foram 27 grupos, mais um "outros" das queries que eu não consegui categorizar). Pra minha surpresa, o "fondue" ganhou disparado da "muler pelada". Acho que o povo prefere o pecado da gula ao pecado da luxúria... (ou será só que pouca gente escreve sobre fondue por isso as buscas caem com mais freqüência no meu site? quem irá saber?). Aí em baixo um grafiquinho resumindo meu trabalho:

Gráfico das buscas que mais cairam no meu site, categorizadas por assunto.

Gostei também de saber que procuram meu blog pra "coisas sérias" como compressão de dados e colocação de padres no google maps. Mas o objetivo mesmo não era esse. Era recolher frases legais sobre as quais postar...

Frases legais

quem sou eu? curriculum

Será que esse daí queria que o currículo dele já estivesse pronto na internet? Ou será que ele nem mesmo sabe quem ele é? vai saber... (mas quem quiser, tem um link pro MEU currículo aqui 😉

mera

Ein??? Mera? Que diabos é isso?

moro de favor meu filho pode me visitar

Será que ele(a) acha mais fácil encontrar essa informação na internet do que perguntando pro dono da casa?

passei concurso banco brasil 57 chama

Parabéns, seja lá o que isso queira dizer.

E ainda essas 4 que eu pretendo blogar a respeito com mais tempo:

cosseno o que serve para o futuro;1
que lingua falam? os indios pataxó;1
foto garrafa vinho mioranza;1
porque a água apaga o fogo e o álcool não;1

A da garrafa de mioranza, vinho da família da Carol, eu já posto duma vez:

Os finos, e

os de garrfão!

Os outros assuntos eu blogarei mais tarde, ou outro dia... ou não.

Como enviar emails de seu host local (ou o que o apt-get não te conta).

Larguei mão de pagar provedor de email. O google me fornece um serviço melhor, maior e mais barato (i.e. de gratis). Então migrei o meu email @girino.org pro google. Foi fácil, segui as instruções e tudo veio às mil e uma maravilhas.

Mas só que o google preza pela segurança bem mais que a locaweb (meu anterior provedor), e eu não consegui mais mandar emails da linha de comando no linux (usando mutt no meu caso, que eu gosto de usar pra automatizar o envio de emails através de scripts, por exemplo). O Google reclamava: não aceito servidores de email de mentirinha, seu bobão[foot]Na verdade a mensagem era "The IP you're using to send mail is not authorized to send email directly to our servers. Please use the SMTP relay at your service provider instead. Learn more at http://mail.google.com/support/bin/answer.py?answer=10336 9si12791434ywf.9"[/foot]! Ou você autentica ou se vira com seu provedor. Só que meu provedor, é... digamos... fuleiro! Não me fornece conta de email nem nada. Então fiquei na mão.

Até fucei outros jeitos de configurar o "relay" no exim (o "sendmail" que o ubuntu usa chama exim), mas não adiantava: ninguém me queria!

Aí eu pensei: poxa, esse exim é tão bacana, será que ele não autentica sozinho? E pior que eu autentica! foi só acrescentar a linha

*:meuusuario@gmail.com:minhasenha

no arquivo

/etc/exim4/passwd.client

e usar o host

smtp.gmail.com

como smarthost no exim.

Para configurar o exim, rode:

sudo dpkg-reconfigure exim4-config

no terminal, selecione a opção de "mail sent by smarthost; received via SMTP or fetchmail" e deixe os valores padrão todos exceto quando ele perguntar o endereço do seu smarthost. Nessa hora preencha com

smtp.gmail.com

.

Agora é só usar o pine, mutt, mail ou qualquer outro programa de linha de comando que você queira, e partir pro abraço!

Anotações no google reader

Duas importantes notícias:

  1. Os analistas do google leem o blog do Kenji, e
  2. O google Reader tem um recurso novo: anotações e compartilhamento de páginas da web (não só de RSS).

Sim, o recurso tão desejado pelo Kenji e por todos que comentaram no blog dele agora é realidade. Se antes você se comunicava por uma espécie de "mímica" compartilhando o que você gostava, agora você pode acrescentar seus comentários no que compartilhou. Alias, pode apenas compartilhar um mero comentário, sem notícia, blog ou artigo como "base". E ainda mais, pode compartilhar, estilo del.icio.us ou stumbleupon, páginas e sites que encontrar pela web afora.

A interface ainda está meio pobrinha se comparada com esses carinhas das antigas, e a usabilidade não é nada perfeita, mas poxa, já bate um bolão.

Alias, umas coisinhas eu achei estranhas:

  1. não dá pra deletar uma "note" (thanks paulim),
  2. quando eu "anoto" um post ou página, ele deixa eu EDITAR a página ou post original. Dá pra deturpar totalmente o que os outros disseram nos blogs e fingir que foram eles... uma loucuuuuuura... :),
  3. não dá pra "responder" um compartilhamento ou anotação. Tipo, o amigo A compartilha uma página com o comentário: "como será que faz isso?", e eu quero responder: "Faz com a mão, seu burro!!!", mas não dá! Se eu responder, o comentário dele "some" e meus amigos vão achar que eu fiquei maluco dizendo coisas sem sentido.
  4. A "widget" para gente colocar no blog tem uns bugzinhos... ja apareceu mensagem em branco, mensagem em letras garrafais ou negrito. Precisa de um certo retrabalho ali...

Mas como disse, é uma EXCELENTE feature! thanks google...

link.

Faceboogle?!?

Buscas na internet estão para morrer. Ao menos as buscas da forma como conhecemos. As redes sociais e a Web 2.0[foot]Só pra irritar o Gazel[/foot] mudaram a forma como o usuário procura informação. Ao invés de ir a um mecanismo de busca, porque não "imitar" a vida real e procurar a informação com seus amigos, conhecidos e outros membros de sua rede?

Segundo este artigo da PopularMechanics, O futuro das buscas está intimamente ligado ao futuro (incerto) das redes sociais, como orkut, facebook e myspace. O futuro do google seria usar essa informação, e tudo mais que o usuário tiver divulgado em relação a si, para melhorar e filtrar os resultados das buscas. Compras, amigos, blogs lidos e visitados. Tudo entraria na equação para tentar oferecer uma busca melhor do que a antiga forma de "pergunte aos amigos" pode fornecer. A possibilidade da volta ao tradicional conteúdo "push"[foot]empurrado, no sentido de que o usuário não escolhe, mas sim aceita o que escolheram pra ele[/foot], só que bem mais sofisticado e talhado sob medida para os usuários, não deixa de ser um futuro possível.

As coisas nesse sentido ainda tem muito que evoluir e amadurecer, então até lá, a busca na internet ainda não morreu! (será?)

link, (via /.)