Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does for loop using a double fail to terminate

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);
}
like image 714
Patidati Avatar asked Nov 11 '13 13:11

Patidati


People also ask

Can we use double in for loop?

It's possible to literally iterate through every possible double value using Math. ulp or Double.

Why are doubles inaccurate?

doubles are not exact. It is because there are infinite possible real numbers and only finite number of bits to represent these numbers.

How do you abort a for loop?

break terminates the execution of a for or while loop. Statements in the loop after the break statement do not execute. In nested loops, break exits only from the loop in which it occurs. Control passes to the statement that follows the end of that loop.

How do you exit a loop if condition met?

In situations where we want to stop the iteration before getting to the last item or before a given condition is met, we can use the break statement. The break statement will have its own condition – this tells it when to "break" the loop.


3 Answers

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.

like image 100
Richard Tingle Avatar answered Oct 10 '22 23:10

Richard Tingle


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. 64 bits floating point representation

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.

like image 41
hevi Avatar answered Oct 11 '22 01:10

hevi


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);
like image 40
Marko Topolnik Avatar answered Oct 11 '22 00:10

Marko Topolnik