Floating point arithmetics: Possible unsafe reliance on specific comparison?

Question

The following python code calculates the number of iterations to do stuff based on some variables.

  # a - b - c is always a multiple of d.
  i = (a - b - c) / d
  while i:
    # do stuff
    i -= 1

The variables will all be of the same type, that is only ints or floats or whatever. My concern is whether it will work correctly if the values are floats. I know enough to always consider the pitfalls of relying on exact float values. But I can't tell if the above is dangerous or not. I can use i = int(round((a - b - c) / d)), but I am curious as to understand floats better.

It all comes down to the following: a - b - c is an exact multiple of d. So I am relying on (a-b-c)/d to become a value i that I can subtract 1 from and get the expected number of iterations in the while loop, with the implied assumption that i == 0 becomes true. That is, can calculated multiples like this be decremented by 1 to reach exactly 0?

I would like to not only know if it is unsafe, but more importantly, what do I need to understand about floating point to resolve a question like this? If someone knows decisively whether this is safe or not, would it be possible to explain how so?

Answer 1

You can use the decimal module to get an idea of what "hides" between a floating point number such as 0.3:

>>> from decimal import Decimal
>>> Decimal(0.3)
Decimal('0.299999999999999988897769753748434595763683319091796875')

Note that Python 2.7 changed how floating point numbers are written (how repr(f) works) so that it now shows the shortest string that will give the same floating point number if you do float(s). This means that repr(0.3) == '0.3' in Python 2.7, but repr(0.3) == '0.29999999999999999' in earlier versions. I'm mentioning this since it can confuse things further when you really want to see what's behind the numbers.

Using the decimal module, we can see the error in a computation with floats:

>>> (Decimal(2.0) - Decimal(1.1)) / Decimal(0.3) - Decimal(3) 
Decimal('-1.85037170771E-16')

Here we might expect (2.0 - 1.1) / 0.3 == 3.0, but there is a small non-zero difference. However, if you do the computation with normal floating point numbers, then you do get zero:

>>> (2 - 1.1) / 0.3 - 3
0.0
>>> bool((2 - 1.1) / 0.3 - 3)
False

The result is rounded somewhere along the way since 1.85e-16 is non-zero:

>>> bool(-1.85037170771E-16)
True

I'm unsure exactly where this rounding takes place.

As for the loop termination in general, then there's one clue I can offer: for floats less than 2⁵³, IEEE 754 can represent all integers:

>>> 2.0**53    
9007199254740992.0
>>> 2.0**53 + 1
9007199254740992.0
>>> 2.0**53 + 2
9007199254740994.0

The space between representable numbers is 2 from 2⁵³ to 2⁵⁴, as shown above. But if your i is an integer less than 2⁵³, then i - 1 will also be a representable integer and you will eventually hit 0.0, which is considered false in Python.

Answer 2

I will give you a language-agnostic answer (I don't really know Python).

There are multiple potential problems in your code. Firstly, this:

(a - b - c)

If a is (for example) 10⁹, and b and c are both 1, then the answer will be 10⁹, not 10⁹-2 (I'm assuming single-precision float here).

Then there's this:

i = (a - b - c) / d

If numerator and denominator are numbers that can't be exactly represented in floating-point (e.g. 0.3 and 0.1), then the result might not be an exact integer (it might be 3.0000001 instead of 3). Therefore, your loop will never terminate.

Then there's this:

i -= 1

Similarly to above, if i is currently 10⁹, then the result of this operation will still be 10⁹, so your loop will never terminate.

Therefore, you should strongly consider performing all the calculations in integer arithmetic.