Is it possible to get 0 by subtracting two unequal floating point numbers?

Question

Is it possible to get division by 0 (or infinity) in the following example?

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

In normal cases it will not, of course. But what if a and b are very close, can (a-b) result in being 0 due to precision of the calculation?

Note that this question is for Java, but I think it will apply to most programming languages.

Solution 1

In Java, a - b is never equal to 0 if a != b. This is because Java mandates IEEE 754 floating point operations which support denormalized numbers. From the spec:

In particular, the Java programming language requires support of IEEE 754 denormalized floating-point numbers and gradual underflow, which make it easier to prove desirable properties of particular numerical algorithms. Floating-point operations do not "flush to zero" if the calculated result is a denormalized number.

If an FPU works with denormalized numbers, subtracting unequal numbers can never produce zero (unlike multiplication), also see this question.

For other languages, it depends. In C or C++, for example, IEEE 754 support is optional.

That said, it is possible for the expression 2 / (a - b) to overflow, for example with a = 5e-308 and b = 4e-308.

Solution 2

As a workaround, what about the following?

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

That way you don't depend on IEEE support in any language.

Solution 3

You wouldn't get a division by zero regardless of the value of a - b, since floating point division by 0 doesn't throw an exception. It returns infinity.

Now, the only way a == b would return true is if a and b contain the exact same bits. If they differ by just the least significant bit, the difference between them will not be 0.

EDIT :

As Bathsheba correctly commented, there are some exceptions:

1. "Not a number compares" false with itself but will have identical bit patterns.

2. -0.0 is defined to compare true with +0.0, and their bit patterns are different.

So if both a and b are Double.NaN, you will reach the else clause, but since NaN - NaN also returns NaN, you will not be dividing by zero.

Solution 4

There is no case where a division by zero can happen here.

The SMT Solver Z3 supports precise IEEE floating point arithmetic. Let's ask Z3 to find numbers a and b such that 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)

The result is UNSAT. There are no such numbers.

The above SMTLIB string also allows Z3 to pick an arbitrary rounding mode (rm). This means that the result holds for all possible rounding modes (of which there are five). The result also includes the possibility that any of the variables in play might be NaN or infinity.

a == b is implemented as fp.eq quality so that +0f and -0f compare equal. The comparison with zero is implemented using fp.eq as well. Since the question is aimed at avoiding a division by zero this is the appropriate comparison.

If the equality test was implemented using bitwise equality, +0f and -0f would have been a way to make a - b zero. An incorrect previous version of this answer contains mode details about that case for the curious.

Z3 Online does not yet support the FPA theory. This result was obtained using the latest unstable branch. It can be reproduced using the .NET bindings as follows:

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

Using Z3 to answer IEEE float questions is nice because it is hard to overlook cases (such as NaN, -0f, +-inf) and you can ask arbitrary questions. No need to interpret and cite specifications. You can even ask mixed float and integer questions such as "is this particular int log2(float) algorithm correct?".

Solution 5

The supplied function can indeed return infinity:

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

The output is Result: -Infinity.

When the result of the division is to big to be stored in a double, infinity is returned even if the denominator is non-zero.

View more solutions

Comments

[Bathsheba]

Eran; not strictly true. "Not a number compares" false with itself but will have identical bit patterns. Also -0.0 is defined to compare true with +0.0, and their bit patterns are different.

[Mark Pattison]

"Shouldn't ever" is a bit strong, but generally this is good advice.

[Eran]

@Bathsheba I didn't consider these special cases. Thanks for the comment.

[aviad]

It is not strong enough. Learned hard way.

[glglgl]

While you are true, abs(first - second) < error (or <= error) is easier and more concise.

[Thirler]

Thanks for the advise, I do know this, the question comes mostly from trying to understand floating point numbers better. You are very right on saying to avoid if you can't be 100% sure.

[Thirler]

@Eran, very good point that division by 0 will return infinity in a floating point. Added it to the question.

[Taemyr]

However OP wants to know about 2/(a-b). Can this be guaranteed to be finite?

[milleniumbug]

While true in most cases (not all), doesn't really answer the question.

[Thirler]

Thanks for the answer, I added a link to wikipedia for the explanation of denormalized numbers.

[nwellnhof]

@Taemyr See my edit. The division actually can overflow.

[Prashant]

@Eran : if a is +-0.0 and b is also +-0.0 then devision will give NaN not infinity.

[Eran]

@Prashant but the division wouldn't take place in this case, since a == b would return true.

[Prashant]

@Eran: i agree here division will not take place, but i was pointing this.

[vpalmu]

Avoid the problem and simplify the test all at once. Me like.

[supercat]

The registers holding the aligned operands for subtraction are required to hold extra two bits, called "guard bits", to deal with this situation. In the scenario where the subtraction would cause a borrow from the most significant bit, either the smaller operand's magnitude must exceed half that of the larger operand (implying that it can only have one extra bit of precision) or else the result must be at least half the magnitude of the smaller operand (implying that it will only need only one more bit, plus information sufficient to ensure correct rounding).

[Cole Tobin]

@Taemyr (a,b) = (3,1) => 2/(a-b) = 2/(3-1) = 2/2 = 1 Whether this is true with IEEE floating point, I don't know

[Cole Tobin]

-1 If a=b, you shouldn't be returning 0. Dividing by 0 in IEEE 754 gets you infinity, not an exception. You're avoiding the problem, so returning 0 is a bug waiting to happen. Consider 1/x + 1. If x=0, that'd result in 1, not the correct value: infinity.

[Nick T]

@ColeJohnson the correct answer is not infinity either (unless you specify which side the limit comes from, right side = +inf, left side = -inf, unspecified = undefined or NaN).

[Voo]

Actually you could get a FP exception for division by zero, it's an option defined by the IEEE-754 standard, although it's probably not what most people would mean with "exception" ;)

[Voo]

"You shouldn't ever compare floats or doubles for equality; because, you can't really guarantee that the number you assign to the float or double is exact" - if I just want to avoid NaN or infinity then checking to make sure a number isn't 0.0 is good enough as long as we follow the IEEE-754 spec (denormals and all).

[Cole Tobin]

@NickT I'm using the logic that +/+=+ and +/-=-. Considering 0 can be positive and negative in IEEE 754, I'd say for a positive numerator, the sign of infinity depends on the sign of 0.

[tmyklebu]

Testing floating-point numbers for equality is quite often useful. There is nothing sane about comparing with an epsilon that has not been carefully chosen, and even less sane about comparing with an epsilon when one is testing for equality.

[Chris Hayes]

-1 because the question is not about the best way to do this division, it's about whether division by zero is even possible in the example. This is answering a question which was not asked.

[Pascal Cuoq]

“Whether this can happen ultimately depends on the FPU design” No, it cannot happen because the Java definition says it can't. The FPU design does not have anything to do with it.

[slebetman]

@ChrisHayes: This is a valid answer to the question recognizing that the question may be an XY problem: meta.stackexchange.com/questions/66377/what-is-the-xy-proble‌​m

[slebetman]

@tmyklebu: By "quite often" I presume you mean "very rarely". I wouldn't consider a use case that occurs in 0.001% (or less) of all code to be "often"

[Taemyr]

This too can return infinity. If c is denormalized 2/c can be greater than the maximum double.

[malarres]

@ColeJohnson I was just trying to mimic the code of the OP, not inferring what he wanted as a result of the code but giving as result what he wanted.

[malarres]

Absolutely true @ChrisHayes, that's why I start with as a workaround... but of course you're in your right of not wanting workarounds as responses

[supercat]

@PascalCuoq: Correct me if I'm wrong, but strictfp is not enabled, it's possible for calculations to yield values which are too small for double but will fit in an extended-precision floating-point value.

[Pascal Cuoq]

@supercat The absence of strictfp only influences the values of “intermediate results”, and I am quoting from docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15‌​.4 . a and b are double variables, not intermediate results, so their values are double-precision values, thus are multiples of 2^-1074. The subtraction of these two double-precision values is consequently a multiple of 2^-1074, so the wider exponent range does change the property that the difference is 0 iff a == b.

[jpmc26]

@ColeJohnson Returning 0 is not really the issue. This is what the OP does in the question. You could put an exception or whatever is appropriate for the situation in that part of the block. If you don't like returning 0, that should a criticism of the question. Certainly, doing as the OP did doesn't warrant a downvote to the answer. This question has nothing to do with further computations after the given function completes. For all you know, the program's requirements necessitate returning 0.

[aviad]

@tmyklebu, the value of your comments about 'quite often useful' is very close to 'an epsilon that has not been carefully chosen' as long as they are not supported by a single example.

[slebetman]

@tmyklebu: Then I'd have to say that the value of testing floating point numbers for equality is very rarely useful. There is nothing sane about testing floating point numbers for equality except in a very, very, very (very) small number of use cases (if you can give me an example, that would be very useful).

[tmyklebu]

@aviad: One clear example of where equality comparison is useful is when you're building a hash table with doubles as keys. Another is when you're trying to test whether a given simple function that takes double input and produces double output and has a tight enough contract works correctly. Another is exactly what's in this question; you can test whether you're evaluating a function at one of its singularities so you can handle that case appropriately. The uses of equality comparison of floating-point numbers are more diverse and not limited to these three.

[aviad]

@tmyklebu, your clear example with hash table with double keys is not very common (otherwise it would be really awkward), because the 1st thing that will happen in hashCode function... shall I tell you? Ok... here is something you might not know: public int hashCode() { long bits = doubleToLongBits(value); return (int)(bits ^ (bits >>> 32)); }

[tmyklebu]

@aviad: How doubles are hashed is implementation-dependent and not always at odds with equality comparison. You gave the hashCode method for Java's Double class, which is not the same as its double primitive.

[Orace]

@ColeJohnson I think you miss the point, the question is not about what should be returned in case of a div by 0 (the OP want it to be zero, that it). The question is about how to detect a div by zero.

[gnasher729]

If you sort an array on a floating-point key, I can guarantee that your code won't work if you try to use tricks comparing floating-point numbers with an epsilon. Because the guarantee that a == b and b == c implies a == c isn't there anymore. For hash tables, the exact same problem. When equality isn't transitive, your algorithms just break.

[aviad]

@tmyklebu, this is how it is implemented in Java (haven't checked ALL implementations, but familiar with many of them). What hashCode method will be called by default on double key? Have you heard about auto-boxing?

[tmyklebu]

@aviad: Have you heard about programming languages other than Java?

[A.L]

Can you please add a link to SMT Solver Z3 and a link to an online interpreter? While this answer seems totally legit, someone can think that these results are wrong.

[Dewi Morgan]

If, in this question, the numerator were one, then the only valid error value (that is, one that would only fall into the "return zero instead of INF" branch if it would otherwise return INF) would be zero. So, this question itself is a good example of the "quite often" where an epsilon error value makes no sense.

[aviad]

@tmyklebu, yes. Few of them. However,the question is about Java. as it is stated in the last line. quote: 'Note that this question is for Java....'

[tmyklebu]

@DewiMorgan: I think you need to pick a number smaller than 1 for that. Something like 2^(-23) ought to work. The smallest subnormal is somewhat smaller than the biggest subnormal is big.

[Keldor314]

@supercat This makes sense - you'd only need one extra bit to do this.

[supercat]

@PascalCuoq: Call m the smallest positive double. If two numbers are both representable as double, the difference will be a multiple of m. Then certainly double d=m*1.125; would set d to m, but I'm not sure if m==m*1.125; would be guaranteed to return true.

[Pascal Cuoq]

@supercat I know this, but the equality in the question is variable == variable, not expression == expression. A variable is not an “intermediate result”.

[supercat]

@PascalCuoq: The sample code is of that form, but I did not interpret that to mean that was the only case of interest. In cases where a subexpression is used exactly twice, it's pretty common for it to be repeated rather than assigned to a variable that would serve no other purpose, so if (a-b*c != 0) doSomething(a-b*c); would not seem implausible.

[Drew Dormann]

A small correction: IEEE-754 is not required of any existing C++ standard, but C99 does demand IEEE-754 compliance.

[nwellnhof]

@DrewDormann IEEE 754 is also optional for C99. See Annex F of the standard.