15
$\begingroup$

At least in Java, if I write this code:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

the value of $e$ would be $false$. I believe this is caused by the fact that floats are very limited in the way of accurately representing numbers. But I don't understand why just changing the position of $a$ could cause this inequality.

I reduced the $b$s to one in both line 3 and 4 as below, the value of $e$ however becomes $true$:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

What exactly happened in line 3 and 4? Why addition operations with floats are not associative?

Thanks in advance.

$\endgroup$
20
$\begingroup$

In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number.

Compare $a+b$ and $b+a$: The result of each operation performed with infinite precision is the same, therefore these identical infinite precision results are rounded in an identical way. In other words, floating-point addition is commutative.

Take $b + b + a$: $b$ is a floating-point number. With binary floating point numbers, $2b$ is also a floating-point number (the exponent is larger by one), so $b+b$ is added without any rounding error. Then $a$ is added to the exact value $b+b$. The result is the exact value $2b + a$, rounded to the nearest floating-point number.

Take $a + b + b$: $a + b$ is added, and there will be a rounding error $r$, so we get the result $a+b+r$. Add $b$, and the result is the exact value $2b + a + r$, rounded to the nearest floating-point number.

So in one case, $2b + a$, rounded. In the other case, $2b + a + r$, rounded.

PS. Whether for two particular numbers $a$ and $b$ both calculations give the same result or not depends on the numbers, and on the rounding error in the calculation $a + b$, and is usually hard to predict. Using single or double precision makes no difference to the problem in principle, but since the rounding errors are different, there will be values of a and b where in single precision the results are equal and in double precision they are not, or vice versa. The precision will be a lot higher, but the problem that two expressions are mathematically the same but not the same in floating-point arithmetic stays the same.

PPS. In some languages, floating point arithmetic may be performed with higher precision or a higher range of numbers than given by the actual statements. In that case, it would be much much more likely (but still not guaranteed) that both sums give the same result.

PPPS. A comment asked whether we should ask if floating point numbers are equal or not at all. Absolutely if you know what you are doing. For example, if you sort an array, or implement a set, you get yourself into awful trouble if you want to use some notion of "approximately equal". In a graphical user interface, you may need to recalculate object sizes if the size of an object has changed - you compare oldSize == newSize to avoid that recalculation, knowing that in practice you almost never have almost identical sizes, and your program is correct even if there is an unnecesary recalculation.

$\endgroup$
  • $\begingroup$ In this particular case, b becomes periodic when converted to binary, so there are rounding errors everywhere. $\endgroup$ – André Souza Lemos Nov 8 '16 at 0:27
  • 1
    $\begingroup$ @AndréSouzaLemos b in this answer is not 0.00004, it's what you get after conversion and rounding. $\endgroup$ – Alexey Romanov Nov 8 '16 at 6:37
  • $\begingroup$ "In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number. " - that is actually mandated by the specification, much to my dismay when I tried to actually implement this in terms of logic gates (the simulator could only handle 64-bit buses). $\endgroup$ – John Dvorak Nov 8 '16 at 14:41
  • $\begingroup$ Naive question: Does testing for float equality ever make sense? Why do most programming languages allow a a==b test where both or one is a float? $\endgroup$ – curious_cat Nov 8 '16 at 14:59
  • $\begingroup$ Relevant definition from Wikipedia: "Machine Epsilon gives an upper bound on the relative error due to rounding in floating point arithmetic." $\endgroup$ – Blackhawk Nov 8 '16 at 16:09
5
$\begingroup$

The binary floating point format supported by computers is essentially similar to decimal scientific notation used by humans.

A floating-point number consists of a sign, mantissa (fixed width), and exponent (fixed width), like this:

+/-  1.0101010101 × 2^12345
sign   ^mantissa^     ^exp^

Regular scientific notation has a similar format:

+/- 1.23456 × 10^99

If we do arithmetic in scientific notation with finite precision, rounding after each operation, then we get all the same bad effects as binary floating point.


Example

To illustrate, suppose we use exactly 3 digits after the decimal point.

a = 99990 = 9.999 × 10^4
b =     3 = 3.000 × 10^0

(a + b) + b

Now we compute:

c = a + b
  = 99990 + 3      (exact)
  = 99993          (exact)
  = 9.9993 × 10^4  (exact)
  = 9.999 × 10^4.  (rounded to nearest)

In the next step, of course:

d = c + b
  = 99990 + 3 = ...
  = 9.999 × 10^4.  (rounded to nearest)

Hence (a + b) + b = 9.999 × 104.

(b + b) + a

But if we did the operations in a different order:

e = b + b
  = 3 + 3  (exact)
  = 6      (exact)
  = 6.000 × 10^0.  (rounded to nearest)

Next we compute:

f = e + a
  = 6 + 99990      (exact)
  = 99996          (exact)
  = 9.9996 × 10^4  (exact)
  = 1.000 × 10^5.  (rounded to nearest)

Hence (b + b) + a = 1.000 × 105, which is different than our other answer.

$\endgroup$
5
$\begingroup$

Java uses IEEE 754 binary floating point representation, which dedicates 23 binary digits to the mantissa, that is normalized to begin with the first significant digit (omitted, to save space).

$0.00004_{10} = 0.00000000000000101001111100010110101100010001110001101101000111..._{2} = [1.]\color{red}{01001111100010110101100}010001110001101101000111..._{2} \times 2^{-15}$

$1000_{10}+0.00004_{10} =1111101000.00000000000000101001111100010110101100010001110001101101000111..._{2}=[1.]\color{red}{11110100000000000000000}\color{blue}{1}01001111100010110101100010001110001101101000111..._{2}\times 2^{9}$

The parts in red are the mantissas, as they are actually represented (before rounding).

Because of this, $(1000_{10} +0.00004_{10})+0.00004_{10}$ will produce a rounding error that is repeated, and thus different from the error in $(0.00004_{10}+0.00004_{10})+1000_{10}$.

$\endgroup$
0
$\begingroup$

We recently ran into a similar rounding issue. The above mentioned answers are correct, however quite technical.

I found the following to be a good explanation as to why rounding errors exist. http://csharpindepth.com/Articles/General/FloatingPoint.aspx

TLDR: binary floating points can not be accurately mapped to decimal floating points. This causes inaccuracies that can compound during mathematical operations.

An example using decimal floating numbers: 1/3 + 1/3 + 1/3 would normally be equal to 1. However, in decimals: 0.333333 + 0.333333 + 0.333333 is never exactly equal to 1.000000

The same happens when doing mathematical operations on binary decimals.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.