[Tutor] while loop ends prematurly

[Hugo Arts]

On Mon, Jan 2, 2012 at 3:48 AM, brian arb <brianjamesarb at gmail.com> wrote:
> Hello,
> Can some please explain this to me?
> My while loop should continue while "owed" is greater than or equal to "d"
>
> first time the function is called
> the loop exits as expected
> False: 0.000000 >= 0.010000
> the next time it does not
> False: 0.010000 >= 0.010000
>
> Below is the snippet of code, and the out put.
>
> Thanks!
>
> def make_change(arg):
>   denom = [100.0, 50.0, 20.0, 10.0, 5.0, 1.0, 0.25, 0.10, 0.05, 0.01]
>   owed = float(arg)
>   payed = []
>   for d in denom:
>     while owed >= d:
>       owed -= d
>       b = owed >= d
>       print '%s: %f >= %f' % (b, owed, d)
>       payed.append(d)
>   print sum(payed), payed
>   return sum(payed)
>
> if __name__ == '__main__':
>   values = [21.48, 487.69] #, 974.41, 920.87, 377.93, 885.12, 263.47,
> 630.91, 433.23, 800.58]
>   for i in values:
>     make_change(i))
>
>
> False: 1.480000 >= 20.000000
> False: 0.480000 >= 1.000000
> False: 0.230000 >= 0.250000
> True: 0.130000 >= 0.100000
> False: 0.030000 >= 0.100000
> True: 0.020000 >= 0.010000
> True: 0.010000 >= 0.010000
> False: 0.000000 >= 0.010000
> 21.48 [20.0, 1.0, 0.25, 0.1, 0.1, 0.01, 0.01, 0.01]
> True: 387.690000 >= 100.000000
> True: 287.690000 >= 100.000000
> True: 187.690000 >= 100.000000
> False: 87.690000 >= 100.000000
> False: 37.690000 >= 50.000000
> False: 17.690000 >= 20.000000
> False: 7.690000 >= 10.000000
> False: 2.690000 >= 5.000000
> True: 1.690000 >= 1.000000
> False: 0.690000 >= 1.000000
> True: 0.440000 >= 0.250000
> False: 0.190000 >= 0.250000
> False: 0.090000 >= 0.100000
> False: 0.040000 >= 0.050000
> True: 0.030000 >= 0.010000
> True: 0.020000 >= 0.010000
> False: 0.010000 >= 0.010000
> 487.68 [100.0, 100.0, 100.0, 100.0, 50.0, 20.0, 10.0, 5.0, 1.0, 1.0, 0.25,
> 0.25, 0.1, 0.05, 0.01, 0.01, 0.01]
>

What happened is that you ran into the weirdness that we call the IEEE
754-2008 standard, otherwise known as floating point numbers. in quite
simple terms, the way the computer represents floating point numbers
means that inaccuracies sneak in when performing math on them, and
some numbers can't even be represented correctly, like 0.1. You can
notice this in some of the simplest calculations:

>>> 0.1
0.1
>>> # seems normal? Well, python is actually tricking you. Let's force it to show us this number with some more accuracy:
>>> "%.32f" % 0.1 # force it to show 32 digits after the period
'0.10000000000000000555111512312578'
>>> # whoops! that's not quite 0.1 at all! let's try some more:
>>> 9 * 0.1
0.9
>>> 0.9
0.9
>>> 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1
0.8999999999999999
>>> "%.32f" % 0.9
'0.90000000000000002220446049250313'
>>> # what?! those aren't even the same numbers!!
>>> 0.1 + 0.2
0.30000000000000004
>>> # what the hell?

Usually this doesn't really matter, because we don't really care about
what happens after you get way far into the decimal spaces. But when
you compare for equality, which is what you're doing here, this stuff
can bite you in the ass real ugly. If you replace the %f with %.32f in
that debugging statement, you'll see why the loop bails:

False: 0.0099999999999977 >= 0.0100000000000000

That kinda sucks, doesn't it? floating point errors are hard to find,
especially since python hides them from you sometimes. But there is a
simple solution! Multiply all numbers by 100 inside that function and
then simply work with integers, where you do get perfect accuracy.

HTH,
Hugo

P.S.: this problem is not in inherent to python but to the IEEE
standard. The sacrifice in accuracy was made deliberately to keep
floating point numbers fast, so it's by design and not something that
should be "fixed." Pretty much all languages that use floats or
doubles have the same thing. If you really want decimal numbers, there
is a Decimal class in Python that implements 100% accurate decimal
numbers at the cost of performance. Look it up.

P.P.S.: for more information you should read these. The first link is
a simple explanation. The second is more complicated, but obligatory
reading material for every programmer worth his salts:
the floating point guide: http://floating-point-gui.de/
what every computer scientist should know about floating-point
arithmetic: http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html