¿Es posible obtener 0 restando dos números desiguales de coma flotante?

131

¿Es posible obtener la división por 0 (o infinito) en el siguiente ejemplo?

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

En casos normales no lo hará, por supuesto. Pero, ¿qué pasa si ay bestán muy cerca, puede (a-b)resultar en la 0precisión del cálculo?

Tenga en cuenta que esta pregunta es para Java, pero creo que se aplicará a la mayoría de los lenguajes de programación.

Thirler
fuente
49
Tendría que probar todas las combinaciones de dobles, eso llevará un tiempo :)
Thirler
3
¡@Thirler me parece un momento para usar JUnit Testing!
Matt Clark
77
@bluebrain, supongo que su número literal 2.000, etc. contiene muchos decimales para ser representado por un flotador. Por lo tanto, los últimos no estarán representados por el número real utilizado en la comparación.
Thirler
44
@Thirler probablemente. "realmente no puedes garantizar que el número que asignas al flotador o al doble sea exacto"
guness
44
Solo tenga en cuenta que devolver 0 en ese caso puede generar una ambigüedad difícil de depurar, así que asegúrese de que realmente desea devolver 0 en lugar de lanzar una excepción o devolver un NaN.
m0skit0

Respuestas:

132

En Java, a - bnunca es igual a 0if a != b. Esto se debe a que Java exige operaciones de punto flotante IEEE 754 que admiten números desnormalizados. De la especificación :

En particular, el lenguaje de programación Java requiere el soporte de números de punto flotante desnormalizados IEEE 754 y un flujo descendente gradual, lo que hace que sea más fácil probar las propiedades deseables de algoritmos numéricos particulares. Las operaciones de punto flotante no se "vuelven a cero" si el resultado calculado es un número desnormalizado.

Si una FPU funciona con números desnormalizados , restar números desiguales nunca puede producir cero (a diferencia de la multiplicación), también vea esta pregunta .

Para otros idiomas, depende. En C o C ++, por ejemplo, el soporte IEEE 754 es opcional.

Dicho esto, es posible que la expresión se 2 / (a - b)desborde, por ejemplo con a = 5e-308y b = 4e-308.

nwellnhof
fuente
44
Sin embargo, OP quiere saber acerca de 2 / (ab). ¿Se puede garantizar que esto sea finito?
Taemyr
Gracias por la respuesta, agregué un enlace a wikipedia para la explicación de los números desnormalizados.
Thirler
3
@Taemyr Ver mi edición. La división en realidad puede desbordarse.
nwellnhof
@Taemyr (a,b) = (3,1)=> 2/(a-b) = 2/(3-1) = 2/2 = 1Si esto es cierto con el punto flotante IEEE, no lo sé
Cole Johnson
1
@DrewDormann IEEE 754 también es opcional para C99. Ver Anexo F de la norma.
nwellnhof
50

Como solución alternativa, ¿qué pasa con lo siguiente?

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

De esa manera no dependerá del soporte IEEE en ningún idioma.

malarres
fuente
66
Evite el problema y simplifique la prueba de una vez. Me gusta
Joshua
11
-1 Si a=b, no deberías volver 0. Dividir 0en IEEE 754 te da infinito, no una excepción. Estás evitando el problema, por lo que regresar 0es un error que espera suceder. Considere 1/x + 1. Si x=0, eso resultaría 1, no el valor correcto: infinito.
Cole Johnson
55
@ColeJohnson la respuesta correcta tampoco es infinita (a menos que especifique de qué lado proviene el límite, lado derecho = + inf, lado izquierdo = -inf, no especificado = indefinido o NaN).
Nick T
12
@ChrisHayes: Esta es una respuesta válida a la pregunta que reconoce que la pregunta puede ser un problema XY: meta.stackexchange.com/questions/66377/what-is-the-xy-problem
slebetman
17
@ColeJohnson Regresar 0no es realmente el problema. Esto es lo que hace el OP en la pregunta. Puede poner una excepción o lo que sea apropiado para la situación en esa parte del bloque. Si no le gusta regresar 0, eso debería ser una crítica de la pregunta. Ciertamente, hacer lo que hizo el OP no garantiza un voto negativo a la respuesta. Esta pregunta no tiene nada que ver con cálculos posteriores después de que se complete la función dada. Por lo que sabes, los requisitos del programa requieren que regreses 0.
jpmc26
25

No obtendría una división por cero independientemente del valor de a - b, ya que la división de coma flotante por 0 no arroja una excepción. Devuelve el infinito.

Ahora, la única manera a == bdevolvería cierto es que si ay bcontener los mismos bits exacta. Si difieren solo en el bit menos significativo, la diferencia entre ellos no será 0.

EDITAR:

Como Bathsheba comentó correctamente, hay algunas excepciones:

  1. "Ningún número se compara" falso consigo mismo, pero tendrá patrones de bits idénticos.

  2. -0.0 se define para comparar verdadero con +0.0, y sus patrones de bits son diferentes.

Entonces, si ambos ay bson Double.NaN, alcanzará la cláusula else, pero como NaN - NaNtambién regresa NaN, no se dividirá por cero.

Eran
fuente
11
Eran No es estrictamente cierto. "Ningún número se compara" falso consigo mismo, pero tendrá patrones de bits idénticos. También se define -0.0 para comparar verdadero con +0.0, y sus patrones de bits son diferentes.
Betsabé
1
@Bathsheba No consideré estos casos especiales. Gracias por el comentario.
Eran
2
@Eran, muy buen punto de que la división por 0 devolverá el infinito en un punto flotante. Lo agregó a la pregunta.
Thirler
2
@Prashant, pero la división no se llevaría a cabo en este caso, ya que a == b sería verdadero.
Eran
3
En realidad, podría obtener una excepción de FP para la división por cero, es una opción definida por el estándar IEEE-754, aunque probablemente no sea lo que la mayoría de la gente querría decir con "excepción";)
Voo
17

No hay caso en el que una división por cero pueda ocurrir aquí.

El SMT Solver Z3 admite aritmética precisa de coma flotante IEEE. Pidamos a Z3 que encuentre números ay btal 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)

El resultado es UNSAT. No hay tales números.

La cadena SMTLIB anterior también permite a Z3 elegir un modo de redondeo arbitrario ( rm). Esto significa que el resultado es válido para todos los modos de redondeo posibles (de los cuales hay cinco). El resultado también incluye la posibilidad de que cualquiera de las variables en juego sea NaNinfinita.

a == bse implementa como fp.eqcalidad para que +0fy se -0fcompare igual. La comparación con cero se implementa utilizando fp.eqtambién. Dado que la pregunta tiene como objetivo evitar una división por cero, esta es la comparación adecuada.

Si la prueba de igualdad se implementó utilizando la igualdad de bits, +0fy -0fhabría sido una forma de hacer a - bcero. Una versión anterior incorrecta de esta respuesta contiene detalles de modo sobre ese caso para los curiosos.

Z3 Online aún no es compatible con la teoría FPA. Este resultado se obtuvo utilizando la última rama inestable. Se puede reproducir utilizando los enlaces .NET de la siguiente manera:

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 a responder a las preguntas IEEE flotador es agradable porque es difícil pasar por alto casos (como NaN, -0f, +-inf) y se puede hacer preguntas arbitrarias. No es necesario interpretar y citar especificaciones. Incluso puede hacer preguntas mixtas flotantes y enteras como "¿es int log2(float)correcto este algoritmo en particular ?".

usr
fuente
¿Puede agregar un enlace a SMT Solver Z3 y un enlace a un intérprete en línea? Si bien esta respuesta parece totalmente legítima, alguien puede pensar que estos resultados son incorrectos.
AL
12

La función suministrada puede devolver 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)); 
    }
}

La salida es Result: -Infinity.

Cuando el resultado de la división es demasiado grande para ser almacenado en un doble, se devuelve el infinito incluso si el denominador no es cero.

D Krueger
fuente
6

En una implementación de punto flotante que se ajusta a IEEE-754, cada tipo de punto flotante puede contener números en dos formatos. Uno ("normalizado") se usa para la mayoría de los valores de coma flotante, pero el segundo número más pequeño que puede representar es solo un poquito más grande que el más pequeño, por lo que la diferencia entre ellos no es representable en ese mismo formato. El otro formato ("desnormalizado") se usa solo para números muy pequeños que no son representables en el primer formato.

La circuitería para manejar el formato de punto flotante desnormalizado de manera eficiente es costosa, y no todos los procesadores lo incluyen. Algunos procesadores ofrecen una opción entre que las operaciones en números realmente pequeños sean mucho más lentas que las operaciones en otros valores, o que el procesador simplemente considere números que son demasiado pequeños para el formato normalizado como cero.

Las especificaciones de Java implican que las implementaciones deben admitir el formato desnormalizado, incluso en máquinas donde hacerlo haría que el código se ejecute más lentamente. Por otro lado, es posible que algunas implementaciones ofrezcan opciones para permitir que el código se ejecute más rápido a cambio de un manejo de valores ligeramente descuidado que para la mayoría de los propósitos sería demasiado pequeño para importar (en casos donde los valores son demasiado pequeños para importar, puede ser molesto que los cálculos con ellos tomen diez veces más tiempo que los cálculos que importan, por lo que en muchas situaciones prácticas, el vaciado a cero es más útil que la aritmética lenta pero precisa).

Super gato
fuente
6

En tiempos antiguos antes de IEEE 754, era muy posible que a! = B no implicara ab! = 0 y viceversa. Esa fue una de las razones para crear IEEE 754 en primer lugar.

Con IEEE 754 está casi garantizado. Los compiladores de C o C ++ pueden realizar una operación con mayor precisión de la necesaria. Entonces, si ayb no son variables sino expresiones, entonces (a + b)! = C no implica (a + b) - c! = 0, porque a + b podría calcularse una vez con mayor precisión y una vez sin mayor precisión

Muchas FPU se pueden cambiar a un modo en el que no devuelven números desnormalizados, sino que los reemplazan por 0. En ese modo, si ayb son pequeños números normalizados donde la diferencia es menor que el número normalizado más pequeño pero mayor que 0, a ! = b tampoco garantiza a == b.

"Nunca comparar números de punto flotante" es la programación de culto de carga. Entre las personas que tienen el mantra "necesitas un épsilon", la mayoría no tiene idea de cómo elegir ese épsilon correctamente.

gnasher729
fuente
2

Puedo pensar en un caso en el que podrías hacer que esto suceda. Aquí hay una muestra análoga en la base 10; en realidad, esto sucedería en la base 2, por supuesto.

Los números de coma flotante se almacenan más o menos en notación científica, es decir, en lugar de ver 35.2, el número almacenado sería más como 3.52e2.

Imagine por conveniencia que tenemos una unidad de coma flotante que opera en la base 10 y tiene 3 dígitos de precisión. ¿Qué sucede cuando resta 9.99 de 10.0?

1.00e2-9.99e1

Shift para dar a cada valor el mismo exponente

1.00e2-0.999e2

Redondear a 3 dígitos

1.00e2-1.00e2

¡UH oh!

Si esto puede suceder en última instancia depende del diseño de la FPU. Dado que el rango de exponentes para un doble es muy grande, el hardware tiene que redondearse internamente en algún momento, pero en el caso anterior, solo 1 dígito adicional internamente evitará cualquier problema.

Keldor314
fuente
1
Los registros que contienen los operandos alineados para la sustracción deben contener dos bits adicionales, llamados "bits de protección", para tratar esta situación. En el escenario donde la resta causaría un préstamo del bit más significativo, la magnitud del operando más pequeño debe exceder la mitad de la del operando más grande (lo que implica que solo puede tener un bit adicional de precisión) o el resultado debe ser al menos la mitad de la magnitud del operando más pequeño (lo que implica que solo necesitará un bit más, más información suficiente para asegurar el redondeo correcto).
supercat
1
"Si esto puede suceder en última instancia depende del diseño de la FPU" No, no puede suceder porque la definición de Java dice que no puede. El diseño de FPU no tiene nada que ver con eso.
Pascal Cuoq
@PascalCuoq: corrígeme si me equivoco, pero strictfpno está habilitado, es posible que los cálculos produzcan valores que son demasiado pequeños doublepero que caben en un valor de punto flotante de precisión extendida.
supercat
@supercat La ausencia de strictfpsolo influye en los valores de "resultados intermedios", y estoy citando de docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.4 . ay bson doublevariables, no resultados intermedios, por lo que sus valores son valores de doble precisión, por lo tanto, son múltiplos de 2 ^ -1074. La sustracción de estos dos valores de doble precisión es, en consecuencia, un múltiplo de 2 ^ -1074, por lo que el rango de exponente más amplio cambia la propiedad de que la diferencia es 0 si f a == b.
Pascal Cuoq
@supercat Esto tiene sentido: solo necesitarías un poco más para hacer esto.
Keldor314
1

Nunca debe comparar flotadores o dobles para la igualdad; porque, realmente no puede garantizar que el número que asigna al flotante o al doble sea exacto.

Para comparar flotadores para la igualdad sensatamente, debe verificar si el valor está "lo suficientemente cerca" del mismo valor:

if ((first >= second - error) || (first <= second + error)
aviad
fuente
66
"No debería" es un poco fuerte, pero generalmente es un buen consejo.
Mark Pattison
1
Si bien es cierto, abs(first - second) < error(o <= error) es más fácil y más conciso.
glglgl
3
Si bien es cierto en la mayoría de los casos ( no en todos ), en realidad no responde la pregunta.
milleniumbug
44
Probar números de coma flotante para la igualdad es bastante útil. No hay nada de sensato en comparar con un épsilon que no se haya elegido cuidadosamente, y menos aún de compararlo con un épsilon cuando se está probando la igualdad.
tmyklebu
1
Si ordena una matriz en una clave de punto flotante, puedo garantizarle que su código no funcionará si intenta usar trucos que comparan números de punto flotante con un épsilon. Porque la garantía de que a == by b == c implica que a == c ya no existe. Para tablas hash, exactamente el mismo problema. Cuando la igualdad no es transitiva, sus algoritmos simplemente se rompen.
gnasher729
1

La división por cero no está definida, ya que el límite de los números positivos tiende al infinito, el límite de los números negativos tiende al infinito negativo.

No estoy seguro si esto es C ++ o Java ya que no hay una etiqueta 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
fuente
1

El problema central es que la representación de la computadora de un doble (también conocido como flotante o número real en lenguaje matemático) está mal cuando tienes "demasiado" decimal, por ejemplo, cuando manejas un doble que no puede escribirse como un valor numérico ( pi o el resultado de 1/3).

Entonces a == b no se puede hacer con ningún valor doble de a y b, ¿cómo lidiar con a == b cuando a = 0.333 yb = 1/3? Dependiendo de su SO vs FPU vs número vs idioma versus conteo de 3 después de 0, tendrá verdadero o falso.

De todos modos, si hace un "cálculo de doble valor" en una computadora, debe tratar con precisión, por lo que, en lugar de hacerlo a==b, debe hacerlo absolute_value(a-b)<epsilon, y epsilon es relativo a lo que está modelando en ese momento en su algoritmo. No puede tener un valor épsilon para toda su doble comparación.

En resumen, cuando escribe a == b, tiene una expresión matemática que no se puede traducir en una computadora (para cualquier número de coma flotante).

PD: hum, todo lo que respondo aquí está más o menos en otras respuestas y comentarios.

Jean Davy
fuente
1

Basado en la respuesta de @malarres y el comentario de @Taemyr, aquí está mi pequeña contribución:

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;
     }
}

Mi punto es decir: la forma más fácil de saber si el resultado de la división es nan o inf es realmente realizar la división.

Orace
fuente