4

I was working on question 33 of Project Euler in Python when I noticed something I do not understand.

The answer to the question needed the denominator given in its lowest common terms. So I thought I would use the float.as_integer_ratio() to check what the denominator was. It turns out that 0.01.as_integer_ratio() returns (5764607523034235, 576460752303423488) and 0.1.as_integer_ratio() returns (3602879701896397, 36028797018963968) instead of the expected 1/100 and 1/10.

Why does it behave like this? I am guessing it has something to do with how these numbers are stored on the computer. I have also tried the Fractions library from Python but this gives the same results. I hope someone can explain why it behaves like this to me.

colidyre
  • 4,170
  • 12
  • 37
  • 53
thomasvdz
  • 43
  • 3

2 Answers2

4

As colidyre mentioned, the problem is with the inaccuracies of floating point representation. You can use the limit_denominator method in the fractions library to get the correct result.

>>> from fractions import Fraction
>>> Fraction(0.01).limit_denominator(100000)
1/100
izhang05
  • 744
  • 2
  • 11
  • 26
0

A computer cannot usually calculate with decimal numbers to the base 10. I am not sure if it is different for a quantum computer, but normally numbers are calculated internally to base 2.

Without that knowledge, this can be a shocking moment:

>>> 0.1 + 0.1 + 0.1 == 0.3
False

That means that normally an approximation is used to get a good representation of that numbers. Because of these approximations, 0.1 + 0.1 + 0.1 is not 0.3.

So a simple 0.1 (base 10) becomes 0.0001 1001 1001 1001... (base 2, endless). But fractions for the rescue and to get rid of the approximations! float.as_integer_ratio() wants to be exact:

Return a pair of integers whose ratio is exactly equal to the original float and with a positive denominator.

(See Python documentation, emphasis mine.)

So the method is using an algorithm to calculate the exact ratio, e.g. from 0.1 and the best numbers the algorithm can found is 3602879701896397 and 36028797018963968. It seems that the numbers are good, because the fractions library gets the same results (as you said).

BTW: Everything is fine in base 10 if you're calculating on decimal numbers which you can handle also in base 2, e.g. 0.5 (=0.1 to base 2):

>>> 0.5.as_integer_ratio()
(1, 2)

If you want to read more, there is also a good site with many detailed information and further links in the Python tutorials.

colidyre
  • 4,170
  • 12
  • 37
  • 53