É possível obter 0 subtraindo dois números desiguais de ponto flutuante?

131

É possível obter divisão por 0 (ou infinito) no exemplo a seguir?

public double calculation(double a, double b)
{
     if (a == b)
     {
         return 0;
     }
     else
     {
         return 2 / (a - b);
     }
}

Em casos normais, isso não acontecerá, é claro. Mas, ae se bestiver muito próximo, pode (a-b)resultar em 0precisão do cálculo?

Observe que esta pergunta é para Java, mas acho que se aplicará à maioria das linguagens de programação.

Thirler
fonte
49
Eu teria que tentar todas as combinações de duplas, que vai levar um tempo :)
Thirler
3
@Thirler parece um tempo para usar o JUnit Testing para mim!
Matt Clark
7
@bluebrain, meu palpite é que o seu número literal 2.000 etc contém muitas casas decimais a serem representadas por um float. Portanto, os últimos não serão representados pelo número real usado na comparação.
Thirler
4
@ Thirler provavelmente. 'você não pode realmente garantia de que o número que você atribui à bóia ou dupla é exato
guness
4
Observe que retornar 0 nesse caso pode levar a uma ambiguidade difícil de depurar; portanto, verifique se realmente deseja retornar 0 em vez de gerar uma exceção ou retornar um NaN.
M0skit0

Respostas:

132

Em Java, a - b nunca é igual a 0se a != b. Isso ocorre porque o Java exige operações de ponto flutuante IEEE 754 que suportam números desnormalizados. Das especificações :

Em particular, a linguagem de programação Java requer suporte de números de ponto flutuante desnormalizados IEEE 754 e subfluxo gradual, o que facilita a comprovação das propriedades desejáveis ​​de algoritmos numéricos específicos. As operações de ponto flutuante não "zeram" se o resultado calculado for um número desnormalizado.

Se uma FPU trabalha com números desnormalizados , subtrair números desiguais nunca pode produzir zero (ao contrário da multiplicação), também veja esta pergunta .

Para outros idiomas, isso depende. Em C ou C ++, por exemplo, o suporte ao IEEE 754 é opcional.

Dito isto, é possível que a expressão 2 / (a - b)ultrapasse, por exemplo, com a = 5e-308e b = 4e-308.

Nwellnhof
fonte
4
No entanto, o OP quer saber sobre 2 / (ab). Isso pode ser garantido como finito?
Taemyr
Obrigado pela resposta, adicionei um link à Wikipedia para a explicação dos números desnormalizados.
Thirler
3
@ Taemyr Veja minha edição. A divisão realmente pode transbordar.
Nwellnhof 12/02
@Taemyr (a,b) = (3,1)=> 2/(a-b) = 2/(3-1) = 2/2 = 1Se isso é verdade com IEEE ponto flutuante, eu não sei
Cole Johnson
1
O @DrewDormann IEEE 754 também é opcional para o C99. Veja o Anexo F da norma.
Nwellnhof
50

Como solução alternativa, o que dizer do seguinte?

public double calculation(double a, double b) {
     double c = a - b;
     if (c == 0)
     {
         return 0;
     }
     else
     {
         return 2 / c;
     }
}

Dessa forma, você não depende do suporte da IEEE em nenhum idioma.

malarres
fonte
6
Evite o problema e simplifique o teste de uma só vez. Eu gosto.
Joshua
11
-1 Se a=bvocê não deveria estar retornando 0. A divisão 0no IEEE 754 leva ao infinito, não uma exceção. Você está evitando o problema, portanto, retornar 0é um bug que está esperando para acontecer. Considere 1/x + 1. Se x=0isso resultasse 1, não o valor correto: infinito.
Cole Johnson
5
@ColeJohnson, a resposta correta também não é infinito (a menos que você especifique de que lado o limite vem, lado direito = + inf, lado esquerdo = -inf, não especificado = indefinido ou NaN).
Nick T
12
@ChrisHayes: Esta é uma resposta válida para a questão reconhecendo que a questão pode ser um problema XY: meta.stackexchange.com/questions/66377/what-is-the-xy-problem
slebetman
17
@ColeJohnson Voltar 0não é realmente o problema. É isso que o OP faz na pergunta. Você pode colocar uma exceção ou o que for apropriado para a situação nessa parte do bloco. Se você não gosta de voltar 0, isso deve ser uma crítica à pergunta. Certamente, fazer como o OP não garante uma resposta negativa à resposta. Esta questão não tem nada a ver com cálculos adicionais após a conclusão da função especificada. Pelo que você sabe, os requisitos do programa exigem retorno 0.
Jpmc26 13/02/2015
25

Você não obteria uma divisão por zero, independentemente do valor de a - b , pois a divisão de ponto flutuante por 0 não gera uma exceção. Retorna o infinito.

Agora, a única maneira de a == bretornar true é if ae bcontém exatamente os mesmos bits. Se eles diferirem apenas pelo bit menos significativo, a diferença entre eles não será 0.

EDIT:

Como Bathsheba comentou corretamente, existem algumas exceções:

  1. "Nenhum número se compara" false com ele mesmo, mas terá padrões de bits idênticos.

  2. -0.0 é definido para comparar true com +0.0, e seus padrões de bits são diferentes.

Portanto, se ambos ae bsão Double.NaN, você alcançará a cláusula else, mas como NaN - NaNtambém retorna NaN, você não estará dividindo por zero.

Eran
fonte
11
Eran; não é estritamente verdade. "Nenhum número se compara" false com ele mesmo, mas terá padrões de bits idênticos. Também -0.0 é definido para comparar true com +0.0, e seus padrões de bits são diferentes.
Bathsheba
1
@Bathsheba Eu não considerei esses casos especiais. Obrigado pelo comentário.
Erã
2
@ Eran, ponto muito bom que a divisão por 0 retornará o infinito em um ponto flutuante. Adicionado à pergunta.
Thirler
2
@ Prashant, mas a divisão não aconteceria nesse caso, pois a == b retornaria true.
Erã
3
Na verdade, você pode obter uma exceção FP para a divisão por zero, é uma opção definida pelo padrão IEEE-754, embora provavelmente não é o que a maioria das pessoas quer dizer com "exceção";)
Voo
17

Não há nenhum caso em que uma divisão por zero possa acontecer aqui.

O SMT Solver Z3 suporta aritmética precisa de ponto flutuante IEEE. Vamos pedir ao Z3 para encontrar números ae btais que a != b && (a - b) == 0:

(set-info :status unknown)
(set-logic QF_FP)
(declare-fun b () (FloatingPoint 8 24))
(declare-fun a () (FloatingPoint 8 24))
(declare-fun rm () RoundingMode)
(assert
(and (not (fp.eq a b)) (fp.eq (fp.sub rm a b) +zero) true))
(check-sat)

O resultado é UNSAT. Não existem tais números.

A sequência SMTLIB acima também permite que o Z3 escolha um modo de arredondamento arbitrário ( rm). Isso significa que o resultado é válido para todos os modos de arredondamento possíveis (dos quais existem cinco). O resultado também inclui a possibilidade de qualquer uma das variáveis ​​em jogo ser NaNou infinita.

a == bé implementado como fp.eqqualidade para que +0fe -0fcomparar igual. A comparação com zero é implementada usando fp.eqtambém. Como a pergunta visa evitar uma divisão por zero, esta é a comparação apropriada.

Se o teste de igualdade foi implementado usando a igualdade bit a bit, +0fe-0f tivesse sido uma maneira de fazera - b zero. Uma versão anterior incorreta desta resposta contém detalhes do modo sobre esse caso para os curiosos.

O Z3 Online ainda não suporta a teoria da FPA. Este resultado foi obtido usando o último ramo instável. Ele pode ser reproduzido usando as ligações do .NET da seguinte maneira:

var fpSort = context.MkFPSort32();
var aExpr = (FPExpr)context.MkConst("a", fpSort);
var bExpr = (FPExpr)context.MkConst("b", fpSort);
var rmExpr = (FPRMExpr)context.MkConst("rm", context.MkFPRoundingModeSort());
var fpZero = context.MkFP(0f, fpSort);
var subExpr = context.MkFPSub(rmExpr, aExpr, bExpr);
var constraintExpr = context.MkAnd(
        context.MkNot(context.MkFPEq(aExpr, bExpr)),
        context.MkFPEq(subExpr, fpZero),
        context.MkTrue()
    );

var smtlibString = context.BenchmarkToSMTString(null, "QF_FP", null, null, new BoolExpr[0], constraintExpr);

var solver = context.MkSimpleSolver();
solver.Assert(constraintExpr);

var status = solver.Check();
Console.WriteLine(status);

Usando Z3 para responder a perguntas IEEE flutuador é bom porque é difícil ignorar casos (como NaN, -0f, +-inf) e você pode fazer perguntas arbitrárias. Não há necessidade de interpretar e citar especificações. Você pode até fazer perguntas inteiras de float e float, como "este int log2(float)algoritmo específico está correto?".

usr
fonte
Você pode adicionar um link para o SMT Solver Z3 e um link para um intérprete online? Embora essa resposta pareça totalmente legítima, alguém pode pensar que esses resultados estão errados.
AL
12

A função fornecida pode realmente retornar o infinito:

public class Test {
    public static double calculation(double a, double b)
    {
         if (a == b)
         {
             return 0;
         }
         else
         {
             return 2 / (a - b);
         }
    }    

    /**
     * @param args
     */
    public static void main(String[] args) {
        double d1 = Double.MIN_VALUE;
        double d2 = 2.0 * Double.MIN_VALUE;
        System.out.println("Result: " + calculation(d1, d2)); 
    }
}

A saída é Result: -Infinity.

Quando o resultado da divisão é grande demais para ser armazenado em um dobro, o infinito é retornado mesmo se o denominador for diferente de zero.

D Krueger
fonte
6

Em uma implementação de ponto flutuante em conformidade com a IEEE-754, cada tipo de ponto flutuante pode conter números em dois formatos. Um ("normalizado") é usado para a maioria dos valores de ponto flutuante, mas o segundo menor número que ele pode representar é apenas um pouquinho maior que o menor e, portanto, a diferença entre eles não é representável no mesmo formato. O outro formato ("desnormalizado") é usado apenas para números muito pequenos que não são representáveis ​​no primeiro formato.

Os circuitos para lidar com o formato de ponto flutuante desnormalizado com eficiência são caros e nem todos os processadores o incluem. Alguns processadores oferecem uma escolha entre ambos que têm operações em muito pequeno número seja muito mais lentas que operações em outros valores, ou fazer com que o processador simplesmente considere zero os números pequenos demais para o formato normalizado.

As especificações Java implicam que as implementações devem suportar o formato desnormalizado, mesmo em máquinas onde isso faria o código rodar mais lentamente. Por outro lado, é possível que algumas implementações ofereçam opções para permitir que o código seja executado mais rapidamente em troca de um tratamento levemente desleixado de valores que, na maioria dos casos, seriam muito pequenos para importar (nos casos em que valores são muito pequenos para importar, pode ser irritante ter cálculos com eles dez vezes mais do que os cálculos que importam; portanto, em muitas situações práticas, a descarga para zero é mais útil do que a aritmética lenta, mas precisa).

supercat
fonte
6

Antigamente, antes da IEEE 754, era bem possível que a! = B não implicasse ab! = 0 e vice-versa. Essa foi uma das razões para criar o IEEE 754 em primeiro lugar.

Com o IEEE 754, é quase garantido. Compiladores C ou C ++ podem executar uma operação com maior precisão do que o necessário. Portanto, se aeb não são variáveis, mas expressões, (a + b)! = C não implica (a + b) - c! = 0, porque a + b pode ser calculado uma vez com maior precisão e uma vez sem maior precisão.

Muitas FPUs podem ser alteradas para um modo em que não retornam números desnormalizados, mas os substituem por 0. Nesse modo, se aeb forem pequenos números normalizados em que a diferença seja menor que o menor número normalizado, mas maior que 0, a ! = b também não garante a == b.

"Nunca compare números de ponto flutuante" é a programação do culto à carga. Entre as pessoas que têm o mantra "você precisa de um epsilon", a maioria não tem idéia de como escolher esse epsilon corretamente.

gnasher729
fonte
2

Posso pensar em um caso em que você possa causar isso. Aqui está uma amostra análoga na base 10 - realmente, isso aconteceria na base 2, é claro.

Os números de ponto flutuante são armazenados mais ou menos em notação científica - ou seja, em vez de ver 35.2, o número sendo armazenado seria mais parecido com 3.52e2.

Imagine, por uma questão de conveniência, que temos uma unidade de ponto flutuante que opera na base 10 e tem 3 dígitos de precisão. O que acontece quando você subtrai 9,99 de 10,0?

1.00e2-9.99e1

Shift para dar a cada valor o mesmo expoente

1.00e2-0.999e2

Arredondar para 3 dígitos

1.00e2-1.00e2

Oh!

Se isso pode acontecer em última análise, depende do design da FPU. Como o intervalo de expoentes para um duplo é muito grande, o hardware precisa arredondar internamente em algum momento, mas no caso acima, apenas 1 dígito extra internamente impedirá qualquer problema.

Keldor314
fonte
1
Os registradores que mantêm os operandos alinhados para subtração precisam manter dois bits extras, chamados "bits de guarda", para lidar com essa situação. No cenário em que a subtração causaria um empréstimo do bit mais significativo, a magnitude do operando menor deve exceder a metade do operando maior (implicando que ele pode ter apenas um bit extra de precisão) ou o resultado deve ser pelo menos metade da magnitude do operando menor (o que implica que ele precisará apenas de mais um bit, além de informações suficientes para garantir o arredondamento correto).
Supercat
1
“Se isso pode acontecer em última análise, depende do design da FPU” Não, isso não pode acontecer porque a definição de Java diz que não pode. O design da FPU não tem nada a ver com isso.
Pascal Cuoq 13/02/2015
@PascalCuoq: Corrija-me se eu estiver errado, mas strictfpnão estiver ativado, é possível que os cálculos produzam valores muito pequenos, doublemas que se ajustem a um valor de ponto flutuante de precisão estendida.
22715
@supercat A ausência de strictfpapenas influencia os valores de "resultados intermediários", e estou citando docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.4 . ae bsão doublevariáveis, não resultados intermediários, portanto, seus valores são valores de precisão dupla, portanto, são múltiplos de 2 ^ -1074. A subtração desses dois valores de precisão dupla é consequentemente um múltiplo de 2 ^ -1074; portanto, o maior intervalo de expoentes altera a propriedade de que a diferença é 0 se a == b.
Pascal Cuoq
@ supercat Isso faz sentido - você precisaria apenas de um bit extra para fazer isso.
Kelvin314
1

Você nunca deve comparar carros alegóricos ou duplos pela igualdade; porque, na verdade, você não pode garantir que o número atribuído ao float ou double seja exato.

Para comparar flutuações de igualdade de maneira saudável, é necessário verificar se o valor está "próximo o suficiente" do mesmo valor:

if ((first >= second - error) || (first <= second + error)
aviad
fonte
6
"Deveria nunca" é um pouco forte, mas geralmente esse é um bom conselho.
22415 Mark Pattison
1
Enquanto você é verdadeiro, abs(first - second) < error(ou <= error) é mais fácil e conciso.
glglgl
3
Embora verdadeiro na maioria dos casos ( não todos ), na verdade não responde à pergunta.
milleniumbug
4
Testar números de ponto flutuante quanto à igualdade é muitas vezes útil. Não há nada sensato em comparar com um epsilon que não tenha sido cuidadosamente escolhido e menos ainda em comparar com um epsilon quando se está testando a igualdade.
tmyklebu
1
Se você classificar uma matriz em uma chave de ponto flutuante, posso garantir que seu código não funcionará se você tentar usar truques para comparar números de ponto flutuante com um epsilon. Porque a garantia de que a == eb == c implica a == c não existe mais. Para tabelas de hash, exatamente o mesmo problema. Quando a igualdade não é transitiva, seus algoritmos simplesmente quebram.
gnasher729
1

A divisão por zero é indefinida, uma vez que o limite de números positivos tende ao infinito, o limite de números negativos tende ao infinito negativo.

Não tenho certeza se este é C ++ ou Java, pois não há tag de idioma.

double calculation(double a, double b)
{
     if (a == b)
     {
         return nan(""); // C++

         return Double.NaN; // Java
     }
     else
     {
         return 2 / (a - b);
     }
}
Khaled.K
fonte
1

O principal problema é que a representação por computador de um duplo (também conhecido como número flutuante ou número real na linguagem matemática) está errado quando você tem um número decimal "demais", por exemplo, quando você lida com um número duplo que não pode ser escrito como um valor numérico ( pi ou o resultado de 1/3).

Portanto, a == b não pode ser feito com nenhum valor duplo de aeb, como lidar com a == b quando a = 0,333 eb = 1/3? Dependendo do seu sistema operacional vs FPU vs número vs idioma e contagem de 3 após 0, você terá uma verdadeira ou falsa.

De qualquer forma, se você fizer "cálculo de valor duplo" em um computador, precisará lidar com precisão; portanto, em vez de fazê- a==blo, precisará fazê-lo absolute_value(a-b)<epsilon, e o epsilon é relativo ao que você está modelando naquele momento em seu algoritmo. Você não pode ter um valor epsilon para toda a sua comparação dupla.

Em resumo, quando você digita a == b, você tem uma expressão matemática que não pode ser traduzida em um computador (para qualquer número de ponto flutuante).

PS: hum, tudo o que respondo aqui é mais ou menos em outras respostas e comentários.

Jean Davy
fonte
1

Com base na resposta @malarres e no comentário @Taemyr, aqui está minha pequena contribuição:

public double calculation(double a, double b)
{
     double c = 2 / (a - b);

     // Should not have a big cost.
     if (isnan(c) || isinf(c))
     {
         return 0; // A 'whatever' value.
     }
     else
     {
         return c;
     }
}

Meu argumento é o seguinte: a maneira mais fácil de saber se o resultado da divisão é nan ou inf é realmente executar a divisão.

Orace
fonte