Strange behavior of int()

[Dan Bishop]

Brian wrote:
> Hello,
>
> Can someone tell me what I am doing wrong in this code.
>
> If I create a file change.py with the following contents:
>
> def intTest(M, c):
>         r = M
>         for k in c:
>                 print 'int(r/k) = ', int(r/k), 'r =', r, 'k =', k, 'r/k
> =', r/k
>                 r = r - (k*int(r/k))
>
> intTest(2.30, [0.25, 0.10, 0.05, 0.01])
>
> and execute it, I get the output:
>
> int(r/k) =  9 r = 2.3 k = 0.25 r/k = 9.2
> int(r/k) =  0 r = 0.05 k = 0.1 r/k = 0.5
> int(r/k) =  0 r = 0.05 k = 0.05 r/k = 1.0
> int(r/k) =  4 r = 0.05 k = 0.01 r/k = 5.0

The important thing to remember is that, as far as your computer is
concerned, there are no such numbers as 2.30, 0.10, 0.05, or 0.01.
What's actually stored is the closest binary equivalents.  So your
intTest call is equivalent to

intTest(5179139571476070*2**(-51), [0.25, 7205759403792794*2**(-56),
7205759403792794*2**(-57), 5764607523034235*2**(-59)])

The first time through the loop, r = 5179139571476070*2**(-51) and k =
0.25, so r/k = 5179139571476070*2**(-49), which equals
9.199999999999999289457264239899814128875732421875.  This is as close
to the desired 9.2 as you can get.  So far, so good.

Now, it happens that the value k*int(r/k) = 2.25 is computed exactly.
Subtracting this from r gives

r = 5179139571476070*2**(-51) - 2.25
  = 5179139571476070*2**(-51) - 5066549580791808*2**(-51)
  = (5179139571476070 - 5066549580791808) * 2**(-51)
  = 112589990684262*2**(-51)
  = 7205759403792768*2**(-57)

My last computation here is to normalize the result to 53 significant
bits.  But note that the last 6 of those are zero, because the result
was shifted by 6 places.

00000011001100110011001100110011001100110011001100110 * 2**(-51)
     /                                              /
    /                                              /
   /                                              /
  /                                              /
 /                                              /
/                                              /
11001100110011001100110011001100110011001100110000000 * 2**(-57)
                                               ^^^^^^
                                               padding

The loss of 6 significant bits means that this approximation of 0.05 is
slightly different from the direct approximation of 0.05.  The worst
part is, it's slightly *less*

7205759403792768*2**(-57) # result of the computation
7205759403792794*2**(-57) # 0.05 as stored in the computer

This causes r/k to be slightly *less* than one, which makes int(r/k)
zero and f's up the rest of your computations.

The way to fix this is to use numbers that can be stored exactly in
binary.  The simplest way is to represent monetary amounts as integer
numbers of cents

>>> intTest(230, [25, 10, 5, 1])
int(r/k) =  9 r = 230 k = 25 r/k = 9.2
int(r/k) =  0 r = 5 k = 10 r/k = 0.5
int(r/k) =  1 r = 5 k = 5 r/k = 1.0
int(r/k) =  0 r = 0 k = 1 r/k = 0.0

You might also consider using the decimal.Decimal class.  (Of course,
you'll still have roundoff problems if working with nondecimal amounts
like 1/3 or 1/7.  In that case, use a Rational class.)