Why does for loop using a double fail to terminate

Question

I'm looking through old exam questions (currently first year of uni.) and I'm wondering if someone could explain a bit more thoroughly why the following for loop does not end when it is supposed to. Why does this happen? I understand that it skips 100.0 because of a rounding-error or something, but why?

for(double i = 0.0; i != 100; i = i +0.1){
    System.out.println(i);
}

Answer 1

First of all, I'm going to explain some things about doubles. This will actually take place in base ten for ease of understanding.

Take the value one-third and try to express it in base ten. You get 0.3333333333333.... Let's say we need to round it to 4 places. We get 0.3333. Now, let's add another 1/3. We get 0.6666333333333.... which rounds to 0.6666. Let's add another 1/3. We get 0.9999, not 1.

The same thing happens with base two and one-tenth. Since you're going by 0.1₁₀ and 0.1₁₀ is a repeating binary value(like 0.1666666... in base ten), you'll have just enough error to miss one hundred when you do get there.

1/2 can be represented in base ten just fine, and 1/5 can as well. This is because the prime factors of the denominator are a subset of the factors of the base. This is not the case for one third in base ten or one tenth in base two.

Answer 2

It should be for(double a = 0.0; a < 100.0; a = a + 0.01)

Try and see if this works instead

Answer 3

Computers (at least current ones) works with binary data. Moreover, there is a length limitation for computers to process in their arithmetic logic units (i.e. 32bits, 64bits etc). Representing integers in binary form is simple on the contrary we cant say the same thing for floating points.

As shown above there is a special way of representing floating points according to IEEE-754 which is also accepted as defacto by processor producers and software guys that's why it is important for everyone to know about it.

If we look at the maximum value of a double in java (Double.MAX_VALUE) is 1.7976931348623157E308 (>10^307). only with 64 bits, huge numbers could be represented however problem is the precision.

As '==' and '!=' operators compare numbers bitwise, in your case 0.1+0.1+0.1 is not equal to 0.3 in terms of bits they are represented.

As a conclusion, to fit huge floating point numbers in a few bits clever engineers decided to sacrifice precision. If you are working on floating points you shouldn't use '==' or '!=' unless you are sure what you are doing.

Answer 4

As a general rule, never use double to iterate with due to rounding errors (0.1 may look nice when written in base 10, but try writing it in base 2—which is what double uses). What you should do is use a plain int variable to iterate and calculate the double from it.

for (int i = 0; i < 1000; i++)
  System.out.println(i/10.0);

Answer 5

The number 0.1 cannot be exactly represented in binary, much like 1/3 cannot be exactly represented in decimal, as such you cannot guarantee that:

0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1

This is because in binary:

0.1=(binary)0.00011001100110011001100110011001....... forever

However a double cannot contain an infinite precision and so, just as we approximate 1/3 to 0.3333333 so must the binary representation approximate 0.1.

Expanded decimal analogy

In decimal you may find that

1/3+1/3+1/3
=0.333+0.333+0.333
=0.999

This is exactly the same problem. It should not be seen as a weakness of floating point numbers as our own decimal system has the same difficulties (but for different numbers, someone with a base-3 system would find it strange that we struggled to represent 1/3). It is however an issue to be aware of.

Demo

A live demo provided by Andrea Ligios shows these errors building up.