Início > Ciência da Computação > Para onde foi o meu erro de precisão?

Para onde foi o meu erro de precisão?

A única coisa que fazemos em um computador é armazenar e trabalhar com números. Até nossos textos – como este que estão lendo – são apenas números. E números em binário, números que os processadores sabem trabalhar com, somar, subtrair, multiplicar e dividir.

Alguns números decimais, ao serem armazenados em formato binário perdem precisão pois não temos infinitos bits para representa-los. Os processadores mais modernos hoje, ja trabalham com números inteiros de 64 bits e com ponto flutuante de 128 bits. (É possível construirmos estrutura de dados e algoritmos para aumentar o tamanho de informação que podemos guardar, porem ela ainda não será infinita.)

Esta precisão disponível é suficiente para a maioria das pessoas, porem algumas aplicações específicas podem requerer mais.

Um exemplo é o caso onde tentamos armazenar 0.1 em um double. Pela forma como é feita a conversão do sistema decimal para o binário, ao transformarmos 0.1 em binário temos uma “dízima” binária infinita: 0.000110011001100…. (infinitas repetições de 1100).

Ou seja, não conseguimos representar exatamente 0.1 em nosso computador. Provavelmente 0.099999999999999999999 ou 0.10000000000000000001 representados é suficientemente perto de 0.1 para quase todo mundo.

Mas a pouco tempo estava resolvendo um problema simples (250-DivII) do TopCoder, onde basicamente eu iterava em um for com a variável i e fazia uma comparação utilizando ceil(0.1 * i);

Quando i = 10, as pessoas normais – e as que esquecem deste tipo de detalhe ao implementar a solução de um problema simples – esperariam que 0.1 * 10 = 1. Quem faz computação sabe que como 0.1 não é representado corretamente, logo ou teríamos um número um pouco menor que 1 ou um pouco maior que 1.

A minha grande surpresa foi o fato de que meu programa funcionava no meu ambiente: Windows Vista + GCC 4.4.1. Porem no juíz do TopCoder eu levava WrongAwnser em um dos primeiros casos de teste.

Mas voltando ao problema do erro de precisão, caso 0.1 tivesse um erro positivo, ou seja fosse representado como  0.10000000000000000001 então:

  • ceil(0.1 * 10) deveria ser igual a 2
  • floor(0.1 * 10) deveria ser igual a 1

Porem, caso o erro fosse negativo e nosso 0.1 fosse representado como 0.099999999999999999999 então:

  • ceil(0.1 * 10) deveria ser igual a 1
  • floor(0.1 * 10) deveria ser igual a 0

Porem parece que o GCC e/ou a cstdlib (de onde vem o ceil/floor) conseguem fazer o que as pessoas normais esperariam. Pelo menos foi a conclusão que cheguei ao executar o seguinte programa de testes aqui (Windows Vista + gcc (TDM-2 mingw32) 4.4.1): link.

A saída dele aqui é:

  • ceil(0.1 * 10) = 1.000000
  • floor(0.1 * 10) = 1.000000

Então para onde raios foi meu erro de precisão?!
PS: O for é apenas para evitar que o GCC faça algum tipo de calculo a tempo de compilação.

  1. janeiro 28, 2010 às 11:35 am

    vc quis dizer “0.0999999” em vez de “0.99999”, né?

    • brunobuss
      janeiro 28, 2010 às 8:59 pm

      Denilson :

      vc quis dizer “0.0999999″ em vez de “0.99999″, né?

      É isso sim, valeu =]

  2. janeiro 28, 2010 às 11:39 am

    Sei que você mandou o código compilado por e-mail, mas eu não parei para analisar. TALVEZ o gcc tenha “otimizado” e convertido o 0.1*i para i/10.0. Bom, este é o meu chute.

    Experimenta fazer x=0.1, y=10, e depois x*y. (ah, e tentar compilar sem otimizações e com otimizações)

    • brunobuss
      janeiro 28, 2010 às 9:01 pm

      Vou tentar fazer isso do x e do y.

    • brunobuss
      fevereiro 9, 2010 às 7:05 pm

      Então Denilson, desculpe a demora em responder aqui =]

      Tente fazer como você pediu e deram os mesmos resultados utilizando -O0 e -O3.
      De uma olhada no fonte aqui (para ver se eu fiz que nem você sugeriu ou se eu entendi errado alguma coisa):
      http://www.dcc.ufrj.br/~brunobuss/code/teste_fp_v2.c

      Como no próprio asm gerado ele faz um fmul antes da chamada da ceil/floor, eu não creio que ele esteja passando a multiplicação para divisão e fazendo alguma otimização desse tipo =]

  1. No trackbacks yet.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: