Por que os números decimais não podem ser representados exatamente em binário?

Houve várias perguntas postadas no SO sobre representação de ponto flutuante. Por exemplo, o número decimal 0.1 não tem uma representação binária exata, portanto, é perigoso usar o operador == para compará-lo com outro número de ponto flutuante. Entendo os princípios por trás da representação em ponto flutuante.

O que não entendo é por que, do ponto de vista matemático, os números à direita da casa decimal são mais "especiais" que os da esquerda?

Por exemplo, o número 61.0 tem uma representação binária exata porque a parte integrante de qualquer número é sempre exata. Mas o número 6.10 não é exato. Tudo o que fiz foi mover a casa decimal e de repente fui da Exactopia para Inexactville. Matematicamente, não deve haver diferença intrínseca entre os dois números - são apenas números.

Por outro lado, se eu mover o decimal uma casa na outra direção para produzir o número 610, ainda estou na Exactopia. Eu posso continuar nessa direção (6100, 610000000, 610000000000000) e eles ainda são exatos, exatos, exatos. Mas assim que o decimal cruzar algum limite, os números não serão mais exatos.

O que está acontecendo?

Editar: para esclarecer, quero ficar longe da discussão sobre representações padrão da indústria, como o IEEE, e manter o que acredito ser a maneira matematicamente "pura". Na base 10, os valores posicionais são:

... 1000  100   10    1   1/10  1/100 ...

Em binário, eles seriam:

... 8    4    2    1    1/2  1/4  1/8 ...

Também não há limites arbitrários para esses números. As posições aumentam indefinidamente para a esquerda e para a direita.

Os números decimais podem ser representados exatamente, se você tiver espaço suficiente - mas não flutuando números de pontos binários . Se você usar um tipo de ponto decimal flutuante (por exemplo, System.Decimalno .NET), muitos valores que não podem ser representados exatamente no ponto flutuante binário podem ser exatamente representados.

Vejamos de outra maneira - na base 10 com a qual você provavelmente se sentirá confortável, não poderá expressar 1/3 exatamente. É 0,3333333 ... (recorrente). O motivo pelo qual você não pode representar 0,1 como um número de ponto flutuante binário é exatamente pelo mesmo motivo. Você pode representar 3, 9 e 27 exatamente - mas não 1/3, 1/9 ou 1/27.

O problema é que 3 é um número primo que não é um fator de 10. Isso não é um problema quando você deseja multiplicar um número por 3: você sempre pode multiplicar por um número inteiro sem ter problemas. Mas quando você divide por um número que é primo e não é um fator de sua base, você pode ter problemas (e o fará se tentar dividir 1 por esse número).

Embora 0,1 seja normalmente usado como o exemplo mais simples de um número decimal exato que não possa ser representado exatamente no ponto flutuante binário, indiscutivelmente 0,2 é um exemplo mais simples, pois é 1/5 - e 5 é o primo que causa problemas entre decimal e binário .

Nota lateral para lidar com o problema das representações finitas:

Alguns tipos de ponto decimal flutuante têm um tamanho fixo, enquanto System.Decimaloutros java.math.BigDecimalsão "arbitrariamente grandes" - mas atingem um limite em algum momento, seja na memória do sistema ou no tamanho máximo teórico de uma matriz. Este é um ponto totalmente separado do principal desta resposta, no entanto. Mesmo se você tivesse um número genuinamente arbitrariamente grande de bits para jogar, ainda assim não poderia representar o decimal 0,1 exatamente em uma representação de ponto binário flutuante. Compare isso com o contrário: dado um número arbitrário de dígitos decimais, você pode representar exatamente qualquer número que seja exatamente representável como um ponto binário flutuante.

Por exemplo, o número 61.0 tem uma representação binária exata porque a parte integrante de qualquer número é sempre exata. Mas o número 6.10 não é exato. Tudo o que fiz foi mover a casa decimal e de repente fui da Exactopia para Inexactville. Matematicamente, não deve haver diferença intrínseca entre os dois números - são apenas números .

Vamos nos afastar por um momento dos detalhes das bases 10 e 2. Vamos perguntar - na base b, quais números têm representações terminantes e quais não têm? O pensamento de um momento nos diz que um número xtem uma brepresentação final se, e somente se, existe um número inteiro ncomo x b^num número inteiro.

Então, por exemplo, x = 11/500tem uma representação final de 10, porque podemos escolher n = 3e x b^n = 22, em seguida , um número inteiro. No entanto x = 1/3, não, porque o nque escolhemos, não seremos capazes de nos livrar dos 3.

Este segundo exemplo nos leva a pensar em fatores, e podemos ver que, para qualquer racional x = p/q (supostamente em termos mais baixos), podemos responder à pergunta comparando as principais fatorações de be q. Se qhouver algum fator primordial que não esteja na fatoração primordial de b, nunca conseguiremos encontrar um adequado npara se livrar desses fatores.

Assim, para a base 10, qualquer um p/q que qpossua fatores primos diferentes de 2 ou 5 não terá uma representação final.

Então, agora voltando às bases 10 e 2, vemos que qualquer racional com uma representação 10 terminante terá a forma p/qexatamente quando qtiver apenas 2s e 5s em sua fatoração primária; e esse mesmo número terá uma representação 2 final exatamente quando qtiver apenas 2s em sua fatoração primária.

Mas um desses casos é um subconjunto do outro! Sempre que

qtem apenas 2s em sua fatoração principal

obviamente também é verdade que

qpossui apenas 2s e 5s em sua principal fatoração

ou, dito de outra maneira, sempre que p/qtiver uma representação 2 final, p/qtenha uma representação 10 final . O inverso, no entanto, não se aplica - sempre que qhouver um 5 em sua fatoração primária, ele terá uma representação 10 final, mas não uma representação 2 final. Este é o 0.1exemplo mencionado por outras respostas.

Portanto, temos a resposta para sua pergunta - porque os fatores primos de 2 são um subconjunto dos fatores primos de 10, todos os números com 2 terminais são números com 10, mas não vice-versa. Não se trata de 61 versus 6,1 - é de cerca de 10 versus 2.

Como uma nota de fechamento, se por algumas pessoas Quirk usados (digamos) de base 17, mas nossos computadores usados base 5, a sua intuição nunca teriam sido desviados por isso - não haveria nenhum (não-zero, não-inteiros) números que terminou em ambos os casos!

A razão raiz (matemática) é que, quando você lida com números inteiros, eles são contados infinitamente .

O que significa que, embora haja uma quantidade infinita deles, poderíamos "contar" todos os itens da sequência, sem pular nenhum. Isso significa que, se queremos colocar o item na 610000000000000posição th da lista, podemos descobrir isso através de uma fórmula.

No entanto, números reais são incontáveis ​​e infinitos . Você não pode dizer "me dê o número real na posição 610000000000000" e receba de volta uma resposta. O motivo é que, mesmo entre 0e 1, há um número infinito de valores, quando você considera valores de ponto flutuante. O mesmo vale para dois números de ponto flutuante.

Mais informações:

http://en.wikipedia.org/wiki/Countable_set

http://en.wikipedia.org/wiki/Uncountable_set

Atualização: desculpas, parece que eu interpretei incorretamente a pergunta. Minha resposta é sobre por que não podemos representar todo valor real ; eu não tinha percebido que o ponto flutuante era automaticamente classificado como racional.

Para repetir o que eu disse no meu comentário ao Sr. Skeet: nós pode representar 1/3, 1/9, 1/27, ou qualquer racional em notação decimal. Fazemos isso adicionando um símbolo extra. Por exemplo, uma linha sobre os dígitos que se repetem na expansão decimal do número. O que precisamos para representar números decimais como uma sequência de números binários é 1) uma sequência de números binários, 2) um ponto de raiz e 3) algum outro símbolo para indicar a parte repetida da sequência.

A notação de citação de Hehner é uma maneira de fazer isso. Ele usa um símbolo de cotação para representar a parte repetida da sequência. O artigo: http://www.cs.toronto.edu/~hehner/ratno.pdf e a entrada da Wikipedia: http://en.wikipedia.org/wiki/Quote_notation .

Não há nada que diga que não podemos adicionar um símbolo ao nosso sistema de representação; portanto, podemos representar racionais decimais exatamente usando a notação de aspas binárias e vice-versa.

BCD - Decimal com código binário - as representações são exatas. Eles não são muito eficientes em termos de espaço, mas é uma troca que você precisa fazer com precisão neste caso.

É o mesmo motivo pelo qual você não pode representar 1/3 exatamente na base 10, é preciso dizer 0,33333 (3). Em binário, é o mesmo tipo de problema, mas ocorre apenas para diferentes conjuntos de números.

(Nota: acrescentarei 'b' para indicar números binários aqui. Todos os outros números são dados em decimal)

Uma maneira de pensar sobre as coisas é em termos de algo como notação científica. Estamos acostumados a ver números expressos em notação científica como 6.022141 * 10 ^ 23. Os números de ponto flutuante são armazenados internamente usando um formato semelhante - mantissa e expoente, mas usando potências de dois em vez de dez.

Seu 61.0 pode ser reescrito como 1.90625 * 2 ^ 5 ou 1.11101b * 2 ^ 101b com a mantissa e os expoentes. Para multiplicar por dez e (mover o ponto decimal), podemos fazer:

(1,90625 * 2 ^ 5) * (1,25 * 2 ^ 3) = (2,3828125 * 2 ^ 8) = (1,19140625 * 2 ^ 9)

ou com a mantissa e expoentes em binário:

(1.11101b * 2 ^ 101b) * (1.01b * 2 ^ 11b) = (10.0110001b * 2 ^ 1000b) = (1.00110001b * 2 ^ 1001b)

Observe o que fizemos lá para multiplicar os números. Nós multiplicamos as mantissas e adicionamos os expoentes. Então, como a mantissa terminou acima de dois, normalizamos o resultado batendo no expoente. É como quando ajustamos o expoente após fazer uma operação em números em notação científica decimal. Em cada caso, os valores com os quais trabalhamos tinham uma representação finita em binário e, portanto, os valores gerados pelas operações básicas de multiplicação e adição também produziam valores com uma representação finita.

Agora, considere como dividiríamos 61 por 10. Começaríamos dividindo as mantissas, 1,90625 e 1,25. Em decimal, isso dá 1,525, um bom número curto. Mas o que é isso se o convertermos em binário? Faremos isso da maneira usual - subtraindo a maior potência de duas sempre que possível, assim como converter decimais inteiros em binários, mas usaremos potências negativas de duas:

1,525 - 1 * 2 ^ 0 -> 1
0,525 - 1 * 2 ^ -1 -> 1
0,025 - 0 * 2 ^ -2 -> 0
0,025 - 0 * 2 ^ -3 -> 0
0,025 - 0 * 2 ^ -4 -> 0
0,025 - 0 * 2 ^ -5 -> 0
0,025 - 1 * 2 ^ -6 -> 1
0,009375 - 1 * 2 ^ -7 -> 1
0,0015625 - 0 * 2 ^ -8 -> 0
0,0015625 - 0 * 2 ^ -9 -> 0
0,0015625 - 1 * 2 ^ -10 -> 1
0,0005859375 - 1 * 2 ^ -11 -> 1
0,00009765625 ...

Ah, oh. Agora estamos com problemas. Acontece que 1.90625 / 1.25 = 1.525, é uma fração repetida quando expressa em binário: 1.11101b / 1.01b = 1.10000110011 ... b Nossas máquinas só têm tantos bits para manter essa mantissa e, portanto, arredondam a fração e assuma zeros além de um certo ponto. O erro que você vê ao dividir 61 por 10 é a diferença entre:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
e, digamos:
1.100001100110011001100110b * 2 ^ 10b

É esse arredondamento da mantissa que leva à perda de precisão que associamos aos valores de ponto flutuante. Mesmo quando a mantissa pode ser expressa exatamente (por exemplo, ao adicionar apenas dois números), ainda podemos obter perdas numéricas se a mantissa precisar de muitos dígitos para ajustar após a normalização do expoente.

Na verdade, fazemos esse tipo de coisa o tempo todo quando arredondamos números decimais para um tamanho gerenciável e apenas fornecemos os primeiros dígitos. Como expressamos o resultado em decimal, parece natural. Mas se arredondássemos um decimal e depois o convertêssemos em uma base diferente, ficaria tão feio quanto os decimais que obtemos devido ao arredondamento do ponto flutuante.

Essa é uma boa pergunta.

Toda a sua pergunta é baseada em "como representamos um número?"

TODOS os números podem ser representados com representação decimal ou com representação binária (complemento de 2). Todos eles !!

MAS alguns (a maioria deles) requerem um número infinito de elementos ("0" ou "1" para a posição binária ou "0", "1" a "9" para a representação decimal).

Como 1/3 na representação decimal (1/3 = 0,3333333 ... <- com um número infinito de "3")

Como 0,1 no binário (0,1 = 0,00011001100110011 .... <- com um número infinito de "0011")

Tudo está nesse conceito. Como o seu computador pode considerar apenas finitos conjunto de dígitos (decimal ou binário), apenas alguns números podem ser exatamente representados no seu computador ...

E como disse Jon, 3 é um número primo que não é um fator de 10, portanto 1/3 não pode ser representado com um número finito número de elementos na base 10.

Mesmo com aritmética com precisão arbitrária, o sistema de posição de numeração na base 2 não é capaz de descrever completamente 6.1, embora possa representar 61.

Para 6.1, devemos usar outra representação (como representação decimal ou IEEE 854 que permite a base 2 ou a base 10 para a representação de valores de ponto flutuante)

Se você criar um número grande o suficiente com ponto flutuante (como pode fazer expoentes), também terminará com inexatidão na frente do ponto decimal. Portanto, não acho que sua pergunta seja totalmente válida porque a premissa está errada; não é o caso que mudar para 10 sempre criará mais precisão, porque em algum momento o número do ponto flutuante precisará usar expoentes para representar a amplitude do número e perderá também alguma precisão dessa maneira.

Estou surpreso que ninguém tenha declarado isso ainda: use frações contínuas . Qualquer número racional pode ser representado finitamente em binário dessa maneira.

Alguns exemplos:

1/3 (0,3333 ...)

0; 3

5/9 (0,5555 ...)

0; 1, 1, 4

10/43 (0,232558139534883720930 ...)

0; 4, 3, 3

9093/18478 (0.49209871198181621387596060179673 ...)

0; 2, 31, 7, 8, 5

A partir daqui, há várias maneiras conhecidas de armazenar uma sequência de números inteiros na memória.

Além de armazenar seu número com precisão perfeita, as frações continuadas também têm outros benefícios, como a melhor aproximação racional. Se você decidir encerrar a sequência de números em uma fração contínua mais cedo, os dígitos restantes (quando recombinados em uma fração) fornecerão a melhor fração possível. É assim que as aproximações de pi são encontradas:

Fração continuada de Pi:

3; 7, 15, 1, 292 ...

Terminando a sequência em 1, isso fornece a fração:

355/113

o que é uma excelente aproximação racional.

Na equação

2^x = y ;  
x = log(y) / log(2)

Por isso, eu estava me perguntando se poderíamos ter um sistema de base logarítmica para binários como,

 2^1, 2^0, 2^(log(1/2) / log(2)), 2^(log(1/4) / log(2)), 2^(log(1/8) / log(2)),2^(log(1/16) / log(2)) ........

Isso pode resolver o problema; portanto, se você quiser escrever algo como 32,41 em binário, seria

2^5 + 2^(log(0.4) / log(2)) + 2^(log(0.01) / log(2))

Ou

2^5 + 2^(log(0.41) / log(2))

O problema é que você realmente não sabe se o número é exatamente 61,0. Considere isto:

float a = 60;
float b = 0.1;
float c = a + b * 10;

Qual é o valor de c? Não é exatamente 61, porque b não é realmente .1 porque .1 não tem uma representação binária exata.

Há um limite porque o significado do dígito passou de inteiro para não inteiro. Para representar 61, você tem 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 e 10 ^ 0 são ambos números inteiros. 6.1 é 6 * 10 ^ 0 + 1 * 10 ^ -1, mas 10 ^ -1 é 1/10, o que definitivamente não é um número inteiro. É assim que você acaba em Inexactville.

Um paralelo pode ser feito de frações e números inteiros. Algumas frações, por exemplo, 1/7 não podem ser representadas na forma decimal sem lotes e lotes de decimais. Como o ponto flutuante é baseado em binário, os casos especiais mudam, mas o mesmo tipo de problema de precisão se apresenta.

Há um número infinito de números racionais e um número finito de bits para representá-los. Veja http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems .

O número 61.0 realmente tem uma operação exata de ponto flutuante - mas isso não é verdade para todos os números inteiros. Se você escrevesse um loop que adicionasse um a um número de ponto flutuante de precisão dupla e a um número inteiro de 64 bits, chegaria a um ponto em que o número inteiro de 64 bits representa perfeitamente um número, mas o ponto flutuante não - porque não há bits significativos suficientes.

É muito mais fácil alcançar o ponto de aproximação no lado direito do ponto decimal. Se você começasse a escrever todos os números no ponto flutuante binário, faria mais sentido.

Outra maneira de pensar sobre isso é que, quando você nota que 61.0 é perfeitamente representável na base 10, e mudar o ponto decimal ao redor não muda isso, você está realizando a multiplicação por potências de dez (10 ^ 1, 10 ^ -1 ) No ponto flutuante, a multiplicação por potências de dois não afeta a precisão do número. Tente pegar o 61.0 e dividi-lo por três repetidamente para ilustrar como um número perfeitamente preciso pode perder sua representação precisa.

você sabe números inteiros certo? cada bit representa 2 ^ n

2 ^ 4 = 16
2 ^ 3 = 8
2 ^ 2 = 4
2 ^ 1 = 2
2 ^ 0 = 1

bem, é o mesmo para ponto flutuante (com algumas distinções), mas os bits representam 2 ^ -n 2 ^ -1 = 1/2 = 0,5
2 ^ -2 = 1 / (2 * 2) = 0,25
2 ^ -3 = 0,125
2 ^ -4 = 0,0625

Representação binária de ponto flutuante:

assina Fração do expoente (acho que 1 invisível é anexado à fração)
B11 B10 B9 B8 B7 B6 B5 B4 B3 B2 B1 B0

A resposta de alta pontuação acima acertou em cheio.

Primeiro você estava misturando a base 2 e a base 10 na sua pergunta; depois, quando você coloca um número no lado direito que não é divisível na base, você tem problemas. Como 1/3 em decimal, porque 3 não entra em uma potência de 10 ou 1/5 em binário, o que não entra em uma potência de 2.

Outro comentário, embora NUNCA use igual a números de ponto flutuante, ponto final. Mesmo se for uma representação exata, existem alguns números em alguns sistemas de ponto flutuante que podem ser representados com precisão de mais de uma maneira (o IEEE é ruim nisso, é uma especificação horrível de ponto flutuante para começar, portanto, espere dores de cabeça). Não é diferente aqui 1/3 não é igual ao número da sua calculadora 0,3333333, não importa quantos 3's existam à direita do ponto decimal. É ou pode estar perto o suficiente, mas não é igual. então você esperaria que algo como 2 * 1/3 não fosse igual a 2/3, dependendo do arredondamento. Nunca use igual ao ponto flutuante.

Como discutimos, na aritmética de ponto flutuante, o decimal 0,1 não pode ser perfeitamente representado em binário.

As representações de ponto flutuante e número inteiro fornecem grades ou treliças para os números representados. À medida que a aritmética é feita, os resultados caem da grade e precisam ser colocados de volta na grade por arredondamento. O exemplo é 1/10 em uma grade binária.

Se usarmos a representação decimal codificada em binário, como sugeriu um cavalheiro, seremos capazes de manter os números na grade?