27

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);
}
Raedwald
  • 46,613
  • 43
  • 151
  • 237
Patidati
  • 1,048
  • 2
  • 12
  • 19
  • 13
    C'mon, he means why the loop never ends, instead of blocking at 100 as it should be supposed to. A bit of flexibility never killed the cat ;) – Andrea Ligios Nov 11 '13 at 13:16
  • Ye sorry, I had tried saying this is another way, but every time stackoverflow said "i wasn't allowed to use that word" :P – Patidati Nov 11 '13 at 13:20
  • 1
    @Patidati You mean you tried to say Pr*blem *gasps*. In all fairness you could say "What causes this for loop to fail to exit" – Richard Tingle Nov 11 '13 at 13:22
  • @RichardTingle Haha yes that was it, well ye... I guess.. didn't think too much about it :p Still got some good answers that explained it:)! – Patidati Nov 11 '13 at 13:24
  • 3
    *"I understand that it skips 100.0 because of a rounding-error or something? But why?"* - It sounds like you don't actually understand it at all... – BlueRaja - Danny Pflughoeft Nov 11 '13 at 19:40
  • A good next question would be: how would you solve this? The best answer would be to replace "double" with "BigDecimal" (although due to Java's lack of operator overloading, you would need to change more than that) – JoelFan Nov 11 '13 at 20:18
  • 5
    Easy way to avoid this kind of errors: remember that `==` and `!=` are simply *wrong* when used with `double`/`float`s, in *every* language you write. You either want to check if a result is within a certain tolerance from a point, in which case do something like `abs(result - x) < tolerance`, or you simply want to use `<`, `>` etc. (in your case `< 100` or `<= 100` instead of `!= 100`). – Bakuriu Nov 11 '13 at 22:07
  • @JoelFan There are a huge number of better solutions to this than big decimal, marko's answer for example. – Richard Tingle Nov 11 '13 at 23:08
  • @RichardTingle, why is that solution better? BigDecimal is ideal because it keeps the exact value. – JoelFan Nov 12 '13 at 02:24
  • @JoelFan Because using big decimal is to completely miss the lesson. The point is to make sure that if you don't care about extreme precision make sure your program doesn't either; otherwise people will go back to exact equality and then they will divide 1 by 3 and it will all go wrong again (and thats not even to consider the overhead of big decimal). Big decimal has it's place, but 99.9% of the time is unnessisary – Richard Tingle Nov 12 '13 at 10:49
  • @RichardTingle, I totally disagree that it's unnecessary that much. Any time you are dealing with money, you should be using BigDecimal. – JoelFan Nov 12 '13 at 12:51
  • @JoelFan Yes, could be part of the 0.1% (for accountants it's probably >0.1%, but I've never used money in a program a all; don't check my maths 99.9% is for illustration only). That said; holding money in Pence/Cents seems like a wiser choice unless situations of 0.1 cents is acceptable (which it sometimes is) – Richard Tingle Nov 12 '13 at 12:55
  • @RichardTingle, why hold in cents / pence? You are doing BigDecimal's work for it. Is the performance really that horrible for addition and subtraction? – JoelFan Nov 12 '13 at 12:57
  • @JoelFan You seem to be suggesting a Pound/Euro/Dollar is by default a more fundamental unit and should be used preferentially. Regardless, the important point is; is 0.001 Pounds an acceptable value? If it is then BigDecimal is the way forward, if its not then BigDecimal will hide problems in your code that you should probably deal with explicitly (ok, if we discount each chocolate bar (sold in a shop, not in bulk) by 10%, so £1.229 each and we sold 10 of them, how much money did we make?) – Richard Tingle Nov 12 '13 at 13:04
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/41021/discussion-between-richard-tingle-and-joelfan) – Richard Tingle Nov 12 '13 at 13:04
  • See also http://stackoverflow.com/questions/17373965/why-would-you-use-double-variables-at-all-in-a-for-loop – Raedwald Nov 17 '13 at 20:57
  • See also http://stackoverflow.com/questions/6837007/comparing-float-double-values-using-operator – Raedwald Nov 17 '13 at 21:01
  • possible duplicate of [Is floating point math broken?](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) – phuclv Mar 14 '15 at 12:30

5 Answers5

42

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.

Community
  • 1
  • 1
Richard Tingle
  • 16,906
  • 5
  • 52
  • 77
  • Thank you so much for taking your time to answer:)! – Patidati Nov 11 '13 at 13:22
  • "someone with a base-3 system would find it strange that we struggled to represent 1/3" I still say we should be using base 12. – Cruncher Nov 11 '13 at 14:53
  • "It should not be seen as a weakness of floating point numbers as our own system has the same difficulties" - which system are you referring to? Decimal as opposed to binary? – LarsH Nov 11 '13 at 15:36
  • 1
    @LarsH Exactly, I'm trying to get away from people going "ahhh! doubles have errors, lets use BigDecimal because thats correct" when actually its just the same problem they've accepted since they were children – Richard Tingle Nov 11 '13 at 15:41
  • @BartoszKP Ahh, I see. My point was just that no one is suprised when 1/3 is troublesome because they are used to it. But then they are suprised when 1/10 is troublesome – Richard Tingle Nov 14 '13 at 14:25
12

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.

hevi
  • 2,432
  • 1
  • 32
  • 51
11

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);
Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
  • Thank you, ye I know, but that was how the question was phrased in the exam:p I guess this is what they wanted us to realise:)! – Patidati Nov 11 '13 at 13:22
  • 2
    Using floating-point numbers isn't specifically a problem for an iterator variable; the problem is using `!=` as the termination condition! If the loop were structured `for(double i = 0.0; i < 100; i = i +0.1)` it would terminate just fine. I'd suggest a _better_ general rule is to always use inequalities with floating-point numbers. Many languages have a built-in constant called "Epsilon" or similar (check the documentation for your language of choice), which you would use like so: `if (myDouble - double.Epsilon < target && target < myDouble + double.Epsilon) {...}` – Brian S Nov 11 '13 at 20:21
  • 1
    @BrianS Floating-point iteration *is* a problem due to the accumulation of error, which is avoided if the floating-point number is freshly calculated in each step. – Marko Topolnik Nov 11 '13 at 21:02
  • 1
    @MarkoTopolnik, Oh, good point. I didn't consider accumulation of errors. That would certainly be a problem in a majority of situations where you might want to do this. (And if there's any corner case where it would still work, generating the floating-point should still work perfectly fine.) – Brian S Nov 11 '13 at 21:25
  • 2
    @BrianS If you had i=(10*i+1)/10 you would have no accumulation error (or any other way of not accumulating, but rather just assigning). Not that it is a particularly good idea, but just mentioning it. – soandos Nov 12 '13 at 01:27
8

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.110 and 0.110 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.

nanofarad
  • 40,330
  • 4
  • 86
  • 117
0

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

Try and see if this works instead