O que causa erros de arredondamento de ponto flutuante?

Isso ocorre porque algumas frações precisam de uma quantidade muito grande (ou mesmo infinita) de casas para serem expressas sem arredondamento. Isso vale tanto para a notação decimal quanto para a binária ou qualquer outra. Se você limitar a quantidade de casas decimais a usar em seus cálculos (e evitar fazer cálculos em notação de fração), terá que arredondar até mesmo uma expressão simples para 1/3 + 1/3. Em vez de escrever 2/3 como resultado, você teria que escrever 0,33333 + 0,33333 = 0,666666 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 conseguem 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

Comentários

• Spot on. Mas eu também observaria que alguns números que termina em decimal don ‘ t termina 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.
• Flutuante os pontos não são ‘ úteis apenas para muitas casas decimais. Os inteiros de 32 bits podem contar apenas até cerca de 4 bilhões, mas um float de 32 bits pode ser quase infinitamente grande.
• Em particular, as frações que podemos expressar como decimais finitos são aqueles cujos denominadores ‘ a fatoração principal contém apenas 2 e 5 (por exemplo, podemos expressar 3/10 e 7/25 , mas não 18/11). Quando mudamos para o binário, perdemos o fator de 5, de modo que apenas os racionais diádicos (por exemplo, 1/4, 3/128) podem ser expressos exatamente.

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 parte da memória, como uma única variável de ponto flutuante , então muitos números armazenados são apenas aproximações do número que pretendem representar.

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

O importante coisa é perceber quando é provável que eles causem um problema e tomar medidas para atenuar os riscos .

Além de David Goldberg “é essencial O que todos os cientistas da computação Deve-se saber sobre aritmética de ponto flutuante (republicado pela Sun / Oracle como um apêndice de seu Numérico Guia de computação ), que foi mencionado por thorsten , o ACCU diário Sobrecarga publicou uma excelente série de artigos de Richard Harris sobre o Floating Point Blues .

A série começou com

• Você vai ter que pensar! em Sobrecarga # 99 ( pdf , p5-10):

Co numérico mputar tem muitas armadilhas. Richard Harris começa a procurar uma bala de prata.

O dragão do erro numérico nem sempre é despertado de seu sono, mas se abordado de forma incauta, ele ocasionalmente infligirá danos catastróficos aos cálculos do programador incauto.

Tanto é verdade que alguns programadores, tendo-o encontrado por acaso nas florestas da aritmética de ponto flutuante IEEE 754, aconselham seus colegas a não viajarem naquela bela terra.

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 que foram propostas como substitutos mais seguros para ele. Aprenderemos que o território do dragão é de fato de longo alcance e que, em geral, devemos pisar com cuidado se tememos seu atenção devastadora.

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

Se você não leu mais profundamente do que isso, terá um excelente conhecimento dos problemas associados aos números de ponto flutuante .

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

• Por que o ponto fixo não curou seus pontos flutuantes em Sobrecarga # 100 ( pdf , p15-22)
• Por que os Racionais não Cure Your Floating Point Blues in Sobrecarga # 101 ( pdf , p9-13)
• Por que a álgebra computacional não cura seus pontos flutuantes em Sobrecarga # 102 ( pdf , p9- 14).
• Por que a aritmética de intervalo não cura seus pontos flutuantes em Sobrecarga 103 ( pdf , p19-24)

Ele então começa a tentar ajudá-lo a curar seu Calculus Blues

• Por que [inserir algoritmo aqui] não vai curar sua tristeza de cálculo em Sobrecarga 104 ( pdf , p22-24).
• Por que diferenças finitas não curam sua tristeza de cálculo em Sobrecarga 105 ( pdf , p5-12).
• Por que a aproximação polinomial ganhou “t curar sua tristeza de cálculo em Sobrecarga 106 ( pdf , p16-25).
• Por que a álgebra computacional não cura a tristeza do cálculo em Sobrecarga 107 ( pdf , p15-20).

e por último, mas não menos importante, há

• Por que a diferenciação automática não cura a tristeza do cálculo em Sobrecarga 108 ( pdf , p4-11).

Toda a série de artigos é vale a pena dar uma olhada, e com 66 páginas no total, eles ainda são menores do que as 77 páginas do papel de Goldberg .

Enquanto isso a série cobre muito do mesmo terreno, achei-a bem mais acessível do que o papel de Goldberg “s . 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 se ramificou em muitas áreas interessantes não abordadas pelo artigo de Goldberg.

Como assim falou ak mencionado nos comentários:

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

Comentários

• Como autor desses artigos, ‘ gostaria de mencionar que criei versões interativas deles em meu blog www.thusspakeak.com começando com thusspakeak.com/ak/2013/06 .
• Obrigado @ thusspakea.k. Eu ‘ adicionei uma observação à minha resposta, e embora se os elementos interativos funcionam muito bem.

Bem, thorsten tem o link definitivo. Eu acrescentaria:

Qualquer forma de representação terá algum erro de arredondamento para algum número. Tente expressar 1/3 em ponto flutuante IEEE ou em decimal. Nenhum deles pode fazer isso com precisão. Isso vai além de responder à sua pergunta, mas usei esta regra prática com sucesso:

• Armazene os valores inseridos pelo usuário em decimal (porque quase certamente eles inseriram em uma representação decimal – muito poucos usuários usará binário ou hex). Dessa forma, você sempre tem a representação exata inserida pelo usuário.
• Se você tiver que armazenar frações inseridas pelo usuário, armazene o numerador e denominador (também em decimal)
• Se você tiver um sistema com várias unidades de medida para a mesma quantidade (como Celsius / Fahrenheit), e o usuário pode inserir ambos, armazenar o valor inserido e as unidades em que inseriu. Não tente converter e salvar como uma representação única, a menos que você possa fazer isso sem perda de precisão / exatidão. Use as unidades de valor armazenado e em todos os cálculos.
• Armazene os valores gerados por máquina em 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 dando você o valor em formato decimal (por exemplo, 18,2 C).
• Armazene totais visíveis pelo usuário, etc., em decimal (como uma conta bancária Saldo). Arredonde apropriadamente, mas use esse valor como o valor definitivo para todos os cálculos futuros.

Comentários

• Eu acrescentaria: Considere o uso de um pacote matemático de precisão arbitrária como ARPREC ou decNumber.
• Eu não ‘ t decimal (em oposição ao binário) tem muitos benefícios para valores inteiros, como o numerador e denominador de uma fração. Ambos podem armazenar valores inteiros exatos e o binário é mais eficiente. Há ‘ s algum custo na conversão de entrada e saída, mas que ‘ é provável que seja inundado pelo custo de fisicamente realizar o I / O.

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

Considere o cálculo das potências da razão de ouro (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=1 e φ^1=φ. Se você executar esta recursão em seu ambiente de computação favorito e comparar os resultados com os poderes avaliados com precisão, você encontrará uma erosão lenta de algarismos significativos. Veja 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 φ^41 tem o sinal errado e, mesmo antes, os valores computados e reais para φ^39 não compartilham dígitos em comum (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Portanto, o algoritmo é instável e não se deve usar esta fórmula de recursão em aritmética inexata. Isso se deve a a natureza inerente da fórmula de recursão: há uma solução “decadente” e “crescente” para essa recursão e tentar calcular a solução “decadente” por meio de solução direta quando há uma solução alternativa “crescente” está implorando por sofrimento numérico. Deve-se, portanto, garantir que seus algoritmos numéricos sejam estáveis.

Agora, vamos ao conceito de um problema mal condicionado : mesmo que possa haver uma maneira estável de fazer algo numericamente, pode muito bem ser que o problema que você tem Simplesmente não pode ser resolvido por seu algoritmo. Isso é culpa do problema em si, e não do método de solução. O exemplo canônico em numérico é a solução de equações lineares envolvendo a chamada “matriz de Hilbert”:

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

Aqui “sa Mathematica demonstração: 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 da 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ê experimentou no Mathematica , você notará algumas mensagens de erro alertando sobre o aparecimento de mau condicionamento.)

Em ambos os casos, simplesmente aumentando o precisão não é cura; isso apenas atrasará a inevitável erosão das figuras.

Isso é o que você pode enfrentar. As soluções podem ser difíceis: para a primeira, ou você volta para a prancheta ou vasculha diários / livros / qualquer coisa para descobrir se outra pessoa encontrou uma solução melhor do que a sua; para o segundo, você desiste ou reformula seu problema para algo mais tratável.

Vou deixá-lo com uma citação de Dianne O “Leary:

A vida pode nos lançar alguns problemas mal condicionados, mas não há um bom motivo para se conformar com um algoritmo instável.

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

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

Comentários

• Não exatamente verdadeiro: 0,5 e 0,25 pode ser expresso na base 2. Acho que você quer dizer ” nem todos os números decimais de base 10 “.
• 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). Experimente e faça 9*3.3333333 em decimal e comapre-o em 9*3 1/3
• Esta é a fonte mais comum de ponto flutuante confusão. .1 + .1 != .2 porque a codificação binária de ponto flutuante é usada, não decimal.
• @SeanMcMillan: E 1.0/3.0*3.0 != 1.0, porque flutuante codificação binária de pontos é usada, não trinária.

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

Podemos criar esquemas que nos permitam 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: em finanças, as frações decimais costumam aparecer. Isso ocorre principalmente porque as finanças são essencialmente uma atividade humana, não física.

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

Comentários

• Pior ainda, enquanto uma quantidade infinita (infinita contável) de memória permitiria representar todos os racionais, não suficiente para representar os reais. Pior ainda, quase todos os números reais não são computáveis. O melhor que podemos fazer com uma quantidade finita de memória é aproximar um subconjunto de real de intervalo finito.
• @Kevin: Você ‘ está falando sobre os números computáveis, que é um pequeno subconjunto (um subconjunto com medida zero) dos reais.
• +1 para o explicação mais básica: você ‘ está tentando representar uma quantidade infinita de números com um número finito de bits.
• @DavidHammen: Os números computáveis são um subconjunto minúsculo ( da medida zero) dos reais – mas cada número com que ‘ trabalhará em um programa é, por definição, computável.
• @Giorgio: If você escolhe a representação correta, a raiz quadrada de 2 é representável, por exemplo, como a string "√2". (Minha velha calculadora HP-48 era capaz de fazer exatamente isso, e elevar ao quadrado esse valor resultou exatamente em 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 de uma velocidade incrível e armazenamento mínimo em relação às representações simbólicas.

o único “problema de arredondamento” realmente óbvio com números de ponto flutuante que penso é com filtros de média móvel:

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

para fazer este trabalho sem o acúmulo de ruído, você deseja ter certeza de que $ x [n] $ adicionado nas amostras atuais é precisamente o mesmo que $ x [nN] $ que você subtrairá $ N $ amostras no futuro. se não for, o que é diferente é um pequeno bosta que fica preso na sua linha de retardo e nunca vai sair. isso ocorre porque esse filtro de média móvel é, na verdade, construído com um IIR que possui um pólo marginalmente estável em $ z = 1 $ e um zero que o cancela internamente. mas, é um integrador e qualquer porcaria que for 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 têm.

Comentários

• hey, não ‘ t $ LaTeX $ marcação matemática funciona no fórum prog.SE ??? div id = “0934d2d03f”>