I ran across a blog post called Why 0.1 Does Not Exist In Floating-Point. The author uses long division in binary to demonstrate his point. This is understandable, given that the host blog is called Exploring Binary, but there is a an easier way to determine whether the fraction p/q has a terminating floating point representation for a given base.

Say we want to know whether p/q = 20/24 terminates in when expressed in base B=18. First divide out any common factors of p/q; in our case we are left with p/q = 5/6. Now we can forget p; it plays no further role. The fraction terminates if and only if q divides B. Here q 6 divides 18, so the fraction does terminate. On the other hand, 5/6 does not terminate in base 10, because 6 does not divide 10.

Let’s see why this works. What I’m going to show you works in any base, so we might as well use the familiar base 10.

Consider 1/8 = .125 ; what that means is that 1/8 = 125/1000. To say that the fraction p/q has a terminating representation in base B means that p/q = x/(B^k) for some integers x and k. By looking at the prime factors of q and B, it is easy to either construct x and k, or see that the construction fails. Here are some examples.

1/8 = (1/2)(1/2)(1/2)
    = (1/2)(5/5) (1/2)(5/5) (1/2)(5/5)
    = (5/10)(5/10)(5/10)
    = 125/(10^3)

Here’s the 5/6 in base 18 example.

5/6 = (5/2)(1/3)
    = (5/2)(9/9) (1/3)(6/6)
    = (45/18)(1/18)
    = 45/(18^2)

I mentioned that 5/6 does not terminate in base 10. Here’s what happens if you try as above.

5/6 = (5/2)(1/3)
    = (5/2)(5/5) (1/3)
    = (25/10)(1/3)

There is no integer x such that 3x = 10, so the process fails. I hope this intuitively clear.

The failure case is the more interesting one, so I say want to say a bit more about it. We tried to show that p/q = x/(B^k), where all the variables must be integers. This is the same as saying that p(B^k)/q is an integer, and so q must be a divisor of p(B^k). Let m be an integer. It is a trivial fact that if m divides q and q divides p(B^k), then m divides p(B^k). Now suppose m is a prime divisor of q. It is a deep and non-trivial fact that if a prime m divides a product p(B^k), then either m divides p or m divides B^k (or both). Recall that we began by dividing out common factors of p and q, so m does not divide p. Then m must divide (B^k), and by the same argument, m must divide B. To recap, the only way q can be a divisor of p(B^k) is if each of its prime factors divides B

That’s all folks.