O que causa erros de arredondamento de ponto flutuante?

62

Estou ciente de que a aritmética de ponto flutuante tem problemas de precisão. Normalmente, eu os supero alternando para uma representação decimal fixa do número ou simplesmente negligenciando o erro.

No entanto, não sei quais são as causas dessa imprecisão. Por que existem tantos problemas de arredondamento nos números flutuantes?

nmat
fonte
28
Para ser preciso, não é realmente o erro causado pelo arredondamento com o qual a maioria das pessoas se preocupa - é o fato de o arredondamento binário de ponto flutuante se comportar de maneiras não intuitivas. Mudar para uma representação decimal pode fazer com que o arredondamento se comporte de uma maneira mais intuitiva, mas, em troca, você quase sempre aumenta o erro relativo (ou precisa aumentar o espaço de armazenamento para compensar).
Daniel Pryden
12
Minha tentativa de esclarecer as confusões mais comuns: floating-point-gui.de
Michael Borgwardt
Eu acho que o que @DanielPryden significa é "Mudar para uma representação [de ponto fixo] pode fazer com que o arredondamento se comporte de uma maneira mais intuitiva ..." . o que causa problemas de arredondamento, sejam eles números fixos ou de ponto flutuante, é a largura finita das palavras. é que, com ponto flutuante, a magnitude do erro de arredondamento normalmente permanece aproximadamente proporcional à magnitude do número que está sendo arredondado. (exceto quando você começa realmente pequena e "desordenado" números.)
Robert Bristow-johnson
@robert: Isso não é exatamente o que eu estava me referindo. O "erro" que a maioria das pessoas encontra com ponto flutuante não tem nada a ver com ponto flutuante em si, é a base. Os flutuadores e duplos da IEEE-754 usam um expoente na base 2, o que significa que os números fracionários arredondam-se para potências negativas de dois (1/2, 1/16, 1/1024 etc.) em vez de potências negativas de 10 (1 / 10, 1/1000, etc.) Isso resulta em resultados não intuitivos, como arredondamento de 0,1 para 0,1000001 e problemas semelhantes.
Daniel Pryden
Você pode fazer números de ponto flutuante na base 10 - é assim que o decimaltipo do .NET funciona. O ponto fixo, por outro lado, é diferente. Contanto que seu alcance seja limitado, o ponto fixo é uma ótima resposta. Mas a faixa restritiva torna o ponto fixo inadequado para muitas aplicações matemáticas e, como resultado, as implementações de números de ponto fixo geralmente não são bem otimizadas em hardware.
27515 Daniel Pryden

Respostas:

82

Isso ocorre porque algumas frações precisam de uma quantidade muito grande (ou mesmo infinita) de locais a serem expressos sem arredondamentos. Isso vale tanto para notação decimal quanto para binário ou qualquer outro. Se você limitar a quantidade de casas decimais a ser usada em seus cálculos (e evitar fazer cálculos em notação de fração), será necessário arredondar até uma expressão simples como 1/3 + 1/3. Em vez de escrever 2/3 como resultado, você teria que escrever 0,33333 + 0,33333 = 0,66666, que não é idêntico a 2/3.

No caso de um computador, o número de dígitos é limitado pela natureza técnica de seus registros de memória e CPU. A notação binária usada internamente adiciona mais algumas dificuldades. Os computadores normalmente não podem expressar números em notação de fração, embora algumas linguagens de programação adicionem essa capacidade, o que permite que esses problemas sejam evitados até certo ponto.

O que todo cientista da computação deve saber sobre aritmética de ponto flutuante

thorsten müller
fonte
12
Spot on. Mas eu também observaria que alguns números que terminam em decimal não terminam em binário. Em particular, 0,1 é um número recorrente em binário e, portanto, nenhum número binário de ponto flutuante pode representar exatamente 0,1.
precisa saber é o seguinte
4
Os pontos flutuantes não são úteis apenas para muitas casas decimais. Os números inteiros de 32 bits podem contar até cerca de 4 bilhões, mas um número flutuante de 32 bits pode ser quase infinitamente grande.
Abhi Beckert
7
Em particular, as frações que podemos expressar como decimais finitos são aquelas cuja fatoração primária dos denominadores contém apenas 2 e 5 (por exemplo, podemos expressar 3/10 e 7/25, mas não 11/18). Quando passamos para o binário, perdemos o fator 5, de modo que apenas os racionais diádicos (por exemplo, 1/4, 3/128) podem ser expressos exatamente.
David Zhang
70

Principalmente, os erros de arredondamento vêm do fato de que o infinito de todos os números reais não pode ser representado pela memória finita de um computador , muito menos por uma pequena fatia de memória, como uma única variável de ponto flutuante , de modo que muitos números armazenados são apenas aproximações de o número que eles devem representar.

Como existe apenas um número limitado de valores que não são uma aproximação e qualquer operação entre uma aproximação e outro número resulta em uma aproximação, os erros de arredondamento são quase inevitáveis .

O importante é perceber quando eles podem causar um problema e tomar medidas para mitigar os riscos .


Além do essencial de David Goldberg , O que todo cientista da computação deve saber sobre aritmética de ponto flutuante (republicado pela Sun / Oracle como um apêndice ao Guia de computação numérica ), mencionado por thorsten , o periódico ACCU Overload teve um excelente série de artigos de Richard Harris sobre o Floating Point Blues .

A série começou com

A computação numérica tem muitas armadilhas. Richard Harris começa a procurar uma bala de prata.

O dragão do erro numérico geralmente não é despertado de seu sono, mas, se for abordado de maneira incauta, ele ocasionalmente causará danos catastróficos nos cálculos do programador incauto.

Tanto que alguns programadores, por acaso o encontraram nas florestas da aritmética de ponto flutuante da IEEE 754, aconselham seus companheiros a não viajarem nessa terra justa.

Nesta série de artigos, exploraremos o mundo da computação numérica, contrastando a aritmética de ponto flutuante com algumas das técnicas propostas como substitutos mais seguros. Aprenderemos que o território do dragão é de grande alcance e que, em geral, devemos agir com cuidado se temermos sua atenção devastadora.

Richard começa explicando a taxonomia de números reais, racionais, irracionais, algébricos e transcendentais. Ele então explica a representação da IEEE754, antes de passar para o erro de cancelamento e problemas de ordem de execução.

Se você não ler mais do que isso, terá uma excelente base nos problemas associados aos números de ponto flutuante.

Se você quiser saber mais, no entanto, ele continua com

Ele então muda para tentar ajudá-lo a curar seu Calculus Blues

e por último mas não menos importante, existe

Vale a pena examinar toda a série de artigos e, com 66 páginas no total, ainda são menores que as 77 páginas do artigo de Goldberg .

Embora esta série cubra muito do mesmo terreno, achei-a bastante mais acessível que o artigo de Goldberg . Também achei mais fácil entender as partes mais complexas do artigo depois de ler os artigos anteriores de Richards e, depois desses primeiros artigos, Richard ramifica-se em muitas áreas interessantes não abordadas pelo artigo de Goldberg.


Como assim falou ak mencionado nos comentários:

Como autor desses artigos, gostaria de mencionar que criei versões interativas deles no meu blog www.thusspakeak.com, começando com thusspakeak.com/ak/2013/06 .

Mark Booth
fonte
11
Como autor desses artigos, gostaria de mencionar que criei versões interativas deles no meu blog www.thusspakeak.com, começando com thusspakeak.com/ak/2013/06 .
assim falou ak
Obrigado @ thusspakea.k. Adicionei uma nota à minha resposta e esses elementos interativos funcionam muito bem.
Mark Booth
12

Bem, thorsten tem o link definitivo . Eu adicionaria:

Qualquer forma de representação terá algum erro de arredondamento para algum número. Tente expressar 1/3 no ponto flutuante IEEE ou decimal. Nem pode fazê-lo com precisão. Isso vai além da resposta à sua pergunta, mas usei essa regra prática com êxito:

  • Armazene os valores inseridos pelo usuário em decimal (porque eles certamente o inseriram em uma representação decimal - muito poucos usuários usarão binário ou hexadecimal). Dessa forma, você sempre tem a representação exata inserida pelo usuário.
  • Se você precisar armazenar frações inseridas pelo usuário, armazene o numerador e o denominador (também em decimal)
  • Se você possui um sistema com várias unidades de medida para a mesma quantidade (como Celsius / Fahrenheit) e o usuário pode inserir ambos, armazene o valor digitado e as unidades em que inseriram. Não tente converter e salvar como uma única representação, a menos que você possa fazê-lo sem perda de precisão / exatidão. Use o valor e as unidades armazenados em todos os cálculos.
  • Armazene valores gerados por máquina no ponto flutuante IEEE (podem ser números gerados por um dispositivo de medição eletrônico, como um sensor analógico com um conversor A / D ou o resultado não arredondado de um cálculo). Observe que isso não se aplica se você estiver lendo um sensor em uma conexão serial e ele já estiver fornecendo o valor em um formato decimal (por exemplo, 18,2 C).
  • Armazene totais visíveis ao usuário etc. em decimal (como um saldo de conta bancária). Arredonde adequadamente, mas use esse valor como o valor definitivo para todos os cálculos futuros.
Scott Whitlock
fonte
Eu acrescentaria: Considere usar um pacote matemático de precisão arbitrária como ARPREC ou decNumber.
Blrfl
Eu não decimal (em oposição a binário) tem muito benefício para valores inteiros, como o numerador e o denominador de uma fração. Qualquer um pode armazenar valores inteiros exatos, e o binário é mais eficiente. Há algum custo na conversão para entrada e saída, mas é provável que seja sobrecarregado pelo custo da execução física da E / S.
Keith Thompson
10

O que parece não ter sido mencionado até agora são os conceitos de um algoritmo instável e um problema mal condicionado . Vou abordar o primeiro primeiro, pois isso parece ser uma armadilha mais frequente para numericistas novatos.

Considere o cálculo dos poderes da proporção áurea (recíproca) φ=0.61803…; Uma maneira possível de fazer isso é usar a fórmula de recursão φ^n=φ^(n-2)-φ^(n-1), começando com φ^0=1e φ^1=φ. Se você executar essa recursão no seu ambiente de computação favorito e comparar os resultados com os poderes avaliados com precisão, encontrará uma erosão lenta de números significativos. Aqui está o que acontece, por exemplo, no Mathematica :

ph = N[1/GoldenRatio];  
Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51]  
{0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, 
-2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 
1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, 
-5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 
2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, 
-9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 
3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, 
-1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 
6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, 
-2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 
1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, 
-5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 
2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, 
-9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 
3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, 
-1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 
7.136559332847351*^-7, -1.1547195563277288*^-6}

O resultado pretendido para φ^41tem o sinal errado e, ainda mais cedo, os valores reais e calculados para φ^39compartilhar sem dígitos em comum ( 3.484899258054952* ^ - 9 for the computed version against the true value7.071019424062048 *^-9). O algoritmo é, portanto, instável, e não se deve usar essa fórmula de recursão em aritmética inexata. Isso se deve à natureza inerente da fórmula de recursão: existe uma solução "decadente" e "crescente" para essa recursão, e tenta-se calcular a solução "decadente" por solução direta quando existe uma solução "crescente" alternativa que está implorando para sofrimento numérico. Portanto, deve-se garantir que seus algoritmos numéricos sejam estáveis.

Agora, sobre o conceito de um problema mal condicionado : embora possa haver uma maneira estável de fazer algo numericamente, pode muito bem ser que o problema que você possui simplesmente não possa ser resolvido pelo seu algoritmo. Isso é culpa do problema em si, e não do método de solução. O exemplo canônico em numérica é a solução de equações lineares envolvendo a chamada "matriz de Hilbert":

Matriz de Hilbert

A matriz é o exemplo canônico de uma matriz mal condicionada : tentar resolver um sistema com uma matriz Hilbert grande pode retornar uma solução imprecisa.

Aqui está uma demonstração do Mathematica : compare os resultados da aritmética exata

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}]
{{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 
  1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1,
   1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 
  1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

e aritmética inexata

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}]
{{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.},  
  {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, 
  {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.},  
  {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 
  0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 
  1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 
  0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 
  1.00342}}

(Se você testou no Mathematica , notará algumas mensagens de erro avisando sobre o mau condicionamento que aparece.)

Nos dois casos, simplesmente aumentar a precisão não é cura; apenas atrasará a inevitável erosão das figuras.

Isto é o que você pode enfrentar. As soluções podem ser difíceis: pela primeira vez, você volta à prancheta ou vasculha revistas / livros / o que quer que seja para descobrir se alguém encontrou uma solução melhor do que a sua; no segundo, você desiste ou reformula seu problema para algo mais tratável.


Vou deixar você com uma citação de Dianne O'Leary:

A vida pode nos lançar alguns problemas mal condicionados, mas não há boas razões para aceitar um algoritmo instável.


fonte
9

porque os números decimais da base 10 não podem ser expressos na base 2

ou, em outras palavras, 1/10 não pode ser transformado em uma fração com uma potência de 2 no denominador (que é essencialmente o que são os números de ponto flutuante)

catraca arrepiante
fonte
11
Não exatamente verdade: 0,5 e 0,25 podem ser expressos na base 2. Acho que você quer dizer "nem todos os números decimais da base 10".
Scott Whitlock
3
Mais precisamente. Nem todos os números fracionários podem ser representados exatamente usando uma notação de ponto flutuante (ou seja, com o. Tanto a base 2 quanto a base 10 têm esse problema exato). Tente fazer 9*3.3333333em decimal e comapre9*3 1/3
Martin York
11
Essa é a fonte mais comum de confusão de ponto flutuante. .1 + .1 != .2porque a codificação binária de ponto flutuante é usada, não decimal.
Sean McMillan
@SeanMcMillan: E 1.0/3.0*3.0 != 1.0, porque a codificação binária de ponto flutuante é usada, não trinária.
Keith Thompson
8

Em matemática, existem infinitos números racionais. Uma variável de 32 bits pode ter apenas 2 32 valores diferentes e uma variável de 64 bits apenas 2 64 valores. Portanto, existem infinitos números racionais que não têm representação precisa.

Poderíamos criar esquemas que nos permitissem representar 1/3 perfeitamente, ou 1/100. Acontece que, para muitos propósitos práticos, isso não é muito útil. Há uma grande exceção: nas finanças, as frações decimais geralmente aparecem. Isso ocorre principalmente porque o financiamento é essencialmente uma atividade humana, não física.

Portanto, geralmente escolhemos usar ponto flutuante binário e arredondamos qualquer valor que não possa ser representado em binário. Mas, nas finanças, às vezes escolhemos o ponto flutuante decimal e arredondamos os valores para o valor decimal mais próximo.

MSalters
fonte
2
Pior ainda, enquanto uma quantidade infinita (contada infinitamente) de memória permitiria representar todos os racionais, não seria suficiente para representar os reais. Pior ainda, quase todos os números reais não são números computáveis. O melhor que podemos fazer com uma quantidade finita de memória é aproximar um subconjunto de intervalos finitos dos reais.
David Hammen
4
@ Kevin: Você está falando dos números computáveis, que é um pequeno subconjunto (um subconjunto com a medida zero) dos reais.
David Hammen
11
+1 para a explicação mais básica: você está tentando representar uma quantidade infinita de números com um número finito de bits.
Raku
11
@DavidHammen: Os números computáveis ​​são um pequeno subconjunto (da medida zero) dos reais - mas todos os números com os quais você trabalha em um programa são, por definição, computáveis.
Keith Thompson
3
@Giorgio: Se você escolher a representação correta, a raiz quadrada de 2 é representável, por exemplo, como a string "√2". (Minha antiga calculadora HP-48 foi capaz de fazer exatamente isso, e a quadratura desse valor resultou exatamente 2.0.) Há apenas uma infinidade contável de números reais representáveis ​​para qualquer representação finita - mas nenhum cálculo pode produzir um número que não seja, em princípio, representável. Na prática, o ponto flutuante binário limita drasticamente o conjunto de números representáveis, com o benefício da velocidade impressionante e do armazenamento minúsculo em relação às representações simbólicas.
Keith Thompson
-2

o único "problema de arredondamento" realmente óbvio com números de ponto flutuante em que penso é nos filtros da média móvel:

$$ \ begin {align} y [n] e = \ frac {1} {N} \ sum \ limits_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] - x [nN]) \ \ end {align}

Para que isso funcione sem o acúmulo de ruído, você deve certificar-se de que o $ x [n] $ adicionado nas amostras atuais seja exatamente igual ao $ x [nN] $ que você subtrairá $ N $ amostras no futuro. se não for, o que é diferente é um pouco de cocô que fica preso na linha de atraso e nunca sai. isso ocorre porque esse filtro de média móvel é realmente construído com um IIR que possui um pólo marginalmente estável em $ z = 1 $ e um zero que o cancela por dentro. mas, é um integrador e qualquer porcaria que seja integrada e não totalmente removida existirá na soma do integrador para sempre. é aqui que o ponto fixo não tem o mesmo problema que os números de ponto flutuante.

Robert Bristow-Johnson
fonte
hey, a marcação matemática $ LaTeX $ não funciona no fórum prog.SE ??? isso é realmente manco, se não acontecer.
precisa
11
Veja isso em meta.SO e ligados perguntas
AakashM