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.