É (1 + sqrt(2))^2 = 3 + 2*sqrt(2) satisfeito em aritmética de Ponto Flutuante?

https://stackoverflow.com/questions/1995963

22-09-2019
|

Pergunta

Em matemática a identidade (1 + sqrt(2))^2 = 3 + 2*sqrt(2) é verdade.Mas em ponto flutuante (IEEE 754, usando de precisão única i.e.32 bits) cálculos que não é o caso, como sqrt(2) não tem uma exata representação em binário.

Por isso, não utilizar um valor aproximado de sqrt(2) fornecer resultados diferentes para o lado esquerdo e direito?Se sim, porquê?Não elevar o valor aproximado reduzir significativamente a precisão?

Qual das expressões equivalentes, em seguida, dá o resultado mais preciso?

Solução

Essa identidade passa a se manter quando calculada como escrita em IEEE-754 Duple Precision. Aqui está o porquê:

A raiz quadrada de dois corretamente arredondados para a dupla precisão é:

sqrt(2) = 0x1.6a09e667f3bcd * 2^0

(Estou usando hexadecimal aqui porque as representações são mais arrumadas, e a tradução para o formato IEEE754 é muito mais fácil). A multiplicação por dois é exata em ponto flutuante binário se não ocorrer transbordamento, como neste caso aqui, então:

2*sqrt(2) = 0x1.6a09e667f3bcd * 2^1

Quando adicionamos três, recebemos:

3 + 2*sqrt(2) = 0x1.7504f333f9de68 * 2^2

Isso, no entanto, não é um número de precisão dupla representável (é um pouco largo demais), portanto o resultado é arredondado para o número representável mais próximo. Acontece que esse valor está exatamente no meio do caminho entre dois números representáveis, então escolhemos um com um bit zero à direita:

3 + 2*sqrt(2) = 0x1.7504f333f9de6 * 2^2

Agora o outro lado da computação. Quando adicionamos um à raiz quadrada de precisão dupla de dois, obtemos:

1 + sqrt(2) = 0x1.3504f333f9de68 * 2^1

Este também é um estojo exato intermediário entre os números de precisão dupla representável e, novamente, é arredondado para o número representável "uniforme" mais próximo:

1 + sqrt(2) = 0x1.3504f333f9de6 * 2^1

Quando esse valor é quadrado, o resultado é:

(1 + sqrt(2))*(1 + sqrt(2)) = 0x1.7504f333f9de599cacbc97eaa4 * 2^2

Que também não é um número de precisão dupla representável. Esta está não Um estojo exato na metade, por isso apenas roda para o número representável mais próximo, que é:

(1 + sqrt(2))*(1 + sqrt(2)) = 0x1.7504f333f9de6 * 2^2

Resumo: A computação desse valor de duas maneiras diferentes incorre em duas seqüências diferentes de arredondamentos, mas o resultado final é o mesmo. No entanto, analisamos apenas a computação em dupla precisão; Este pode não ser o caso quando o cálculo é realizado usando diferentes tipos de aritméticos.

Em geral, no entanto, a expressão 3 + 2*sqrt(2) Deve-se esperar que sejam os mais precisos (nos casos em que diferem), porque incorre apenas em dois arredondamentos (a raiz quadrada e a adição) para qualquer tipo binário IEEE-754, enquanto que é (1 + sqrt(2))*(1 + sqrt(2)) incorre em três arredondamentos (raiz quadrada, adicione e multiplique). Deve -se notar também que a diferença entre os dois será no máximo um ou dois bits e provavelmente é insignificante para seus propósitos.

Outras dicas

Desde que até 0.1 + 0.2 != 0.3 Você não deve contar com igualidades tão complexas para manter para números limitados de ponto de flutuação de precisão.

Como os números são armazenados arredondados para um certo número de decimais binários, eles não são exatos se o número (como 0,1) teria infinitamente muitos dígitos binários. Portanto, também os resultados dos cálculos com esses números não serão exatos, e são esperadas pequenas diferenças para o resultado exato de um cálculo.

Então, o uso de um valor aproximado de SQRT (2) fornece resultados diferentes para os lados esquerdo e direito? Se sim, por quê?

Matematicamente, essa igualdade só funciona devido a uma relação exata entre esses números (tem a ver com comprimentos dos lados de um triângulo). Se você adicionar a imprecisão na forma de representação inexata, a igualdade não será mais verdadeira. A igualdade é uma proposição binária, então a questão não é mais "de que lado está certo", mas "esse relacionamento é verdade?". E a resposta é: "Não, não é mais verdade".

A quadra do valor aproximado reduz significativamente a precisão?

Toda operação em dois valores de ponto flutuante provavelmente reduzirá sua precisão. Um subconjunto de operações muito pequeno para certos números - aqueles com representações exatas - pode ser garantido para não piorar a precisão.

Geralmente eu uso [(1 + sqrt (2))^2] - [3 + 2*sqrt (2)] <0,00001 para testar a igualdade nessas condições (é claro que, para alguns casos, ignoro esse uso)

Existe uma maneira melhor?

Os comentários são apreciados :)

Cuidado com os caras, confiar apenas na diferença absoluta pode causar problemas. Funciona para pequenos números em torno de 1, que tem pontos decimais suficientes para poder diferir por 1E-5 ou o que você usa. Mas pense em números maiores. Seus dígitos devem ser armazenados em um espaço limitado (Mantissa). E apenas os dígitos mais significativos são armazenados. O que isso significa? Que não há espaço para armazenar dígitos que permitiriam medir diferenças como 1e-5!

Com uma comparação absoluta e relativa ao mesmo tempo.

bool equal(float a, float b)
{
    if (abs(a - b) < eps)
        return true;
    if (abs(a - b) / max(abs(a), abs(b)) < eps)
        return true;
    return false;
}

Olhe para o lado positivo: se você trabalha novamente essa equação para remover o sqrts, então como você estará lidando com números inteiros de tamanho razoavelmente, a equação será exata no ponto flutuante;)

As imprecisões são geralmente associadas a números que requerem frações decimais (exceto poderes de 0,5 e 0,2) para representar.

Para responder a outra parte da sua pergunta: não, a representação de sqrt(2) é realmente o mesmo de ambos os lados. Os erros (e diferenças) não são introduzidos até você começar a aplicar operações (diferentes) ao mesmo número de ambos os lados: adicionando 1 vs. multiplicação por 2, etc.

A pessoa que tem definido a igualdade de comparação para flutua em C++ deve ser filmado :>.Muitos razoável linguagens (como o SML) não tem um operador de comparação para os carros alegóricos.Eu uso o seguinte código:geralmente:

template < typename T >
inline bool equals( T x, T y, T precision = std::numeric_limits<T>::epsilon() ) 
{
    return abs( x - y ) <= precision;
}

Nota:abs é também um modelo de função aqui, epsilon padrão é armazenado no exterior.Igual na comparação destina-se para os meus propósitos.

Em dupla precisão, (1 + sqrt(2))^2 = 3 + 2*sqrt(2) parece segurar. Ver C Código.

Vou jogar mais uma ideia -

Sim, é verdade, essa igualdade exata de números reais é um conceito sem sentido na programação de computadores.

Mas também é verdade que a igualdade exata de números reais é um conceito sem sentido em nossa realidade física.

Os números inteiros em nossa realidade física são o resultado da contagem. Números reais em nossa realidade física são o resultado da medição. E todas as medidas incluem erros. Dizer que duas medidas físicas têm com precisão o mesmo valor é absurdo. Na melhor das hipóteses, duas medições físicas, arredondadas para algum nível de precisão apropriadas à precisão da qual a medição é capaz, são iguais.

Quando você mede o comprimento de um lápis com uma régua, você recebe um comprimento até o 16º de polegada mais próximo. Quando você o mede com um par de pinças, você recebe um comprimento até o 1000º de polegada mais próximo. As medições do mundo real sempre incluem esse tipo de arredondamento. Quando você simula as medições do mundo real em um programa de computador, você precisa fazer o mesmo.

A igualdade de números reais é um conceito significativo apenas para os matemáticos. (E mesmo lá, é um conceito diferente e mais complicado do que a igualdade de números inteiros).

O SQRT (2) não tem uma representação exata em binário.

O SQRT (2) também não possui uma representação exata no decimal, hexadecimal ou em qualquer outro sistema base-n; É um número irracional.

A única representação exata do SQRT (2) é SQRT (2). Ou, como uma solução para a equação x² = 2.

Ao comparar valores de ponto flutuante, acho melhor comparar o valor absoluto da diferença com uma determinada tolerância. Você sempre pode contar com isso.

Então, o uso de um valor aproximado de SQRT (2) fornece resultados diferentes para os lados esquerdo e direito? Se sim, por quê? A quadra do valor aproximado reduz significativamente a precisão?

A adição e a multiplicação têm aproximação de erros. A multiplicação é empírica, especialmente quando está aninhada.

A seguir, não é uma representação precisa, mas ajuda a entender meu ponto:

example of addition:
(float1 * float2 + float3)
float1 * float2 + float3 + mult_approximation + add_approximation

example multiplication
(float1 * (float2 + float3))
(float1 * (float2 + float3 + add_apporiximation)
float1 * (float2 + float3) + add_approximation * float1 + mult_approximation

É porque representar funções contínuas (infinitas) como o SQRT (x) não podem ser feitas exatamente em uma máquina de estado discreta (finita). Em vez disso, as funções contínuas são traduzidas para funções discretas via expansão da série Taylor de 0 para n, onde n é o número mais alto que você pode representar (neste caso 2^32). Como você não pode levar a soma de 0 para o infinito em um computador, fica com algum restante de erro. Este erro pode ser calculado para que você possa determinar o quão perto sua função discreta é da função contínua.

Para obter mais informações e belas representações tex das equações envolvidas:http://en.wikipedia.org/wiki/taylor_series

Em geral, dois lados vão lhe dar resultados diferentes. A matemática de ponto flutuante não atende à propriedade comutativa e associada. Há vários fatores envolvidos, incluindo opções e hardware do compilador.

Para sua equação, você provavelmente pode descobrir qual lado é mais preciso (meu lado multiplicado), mas não vai se manter em geral se você decidir usar valores diferentes, ou seja, um lado pode ser mais preciso para certos valores, enquanto os Outro lado é mais preciso para outros valores.

O quadrado não deve afetar significativamente os resultados no seu caso.

Surpreendentemente, se, por algum motivo, você precisar de uma representação precisa dos números não racionais (dica: você provavelmente não o ouve), há algo que você pode fazer: frações contínuas aritméticas. A idéia vai para 1972 e é devido ao super -hacker Bill Gosper - Google It Up. A propósito, aspectos mais avançados dessa idéia são uma questão de pesquisa atual em matemática; Veja por exemplo este papel.

Em geral, as operações de ponto flutuante são exatamente até FLT_EPSILON, ou seja, dentro do bit menos significativo, o que para IEEE 32 bits flutuando é 2⁻²³.

Veja também: A precisão do tipo duplo não era de 15 dígitos em C#?

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow