Page 255 - ARM 64 Bit Assembly Language

244 Chapter 8

binimals, we could be tempted to conclude that they are equal. However, that is an oversim-
plification. If we ask the question differently, we can discover some important information. A
better way to ask the question is as follows:

Question: Is the set of terminating decimals a subset of the set of terminating binimals, or
vice versa, or neither.

We start by introducing a lemma which can be used to predict whether or not a terminating
fraction in one base will terminate in another base. We introduce the notation x | y (read as “x
divides y”) to indicate that y can be evenly divided by x.
N x
Lemma 1. If x, 0 <x < 1, terminates in some base B (a product of primes), then x = ,
D x
k 1 k 2
k n
and D x = p p ...p n ,where the p i are the prime factors of B.
1 2
N x k 1 k 2 k n
Proof. Let x = ,and D x = p p ...p n ,where the p i are the prime factors of B.Then
D x 1 2
D x | N x × B k max ,where k max = max(k 1 ,k 2 ,...k n ),so x = N x terminates after k max or fewer
D x x
divisions.
N x k
Let x = terminate after k divisions. Then D x | N x × B .Since D x does not evenly divide
D x
N x , D x must be composed of some combination of the prime factors of B. Thus, D x can be
k n
k 1 k 2
expressed as p p ...p n .
1 2
Theorem 1. The set of terminating binimals is a subset of the set of terminating decimals.

N b k
Proof. Let b be a terminating binimal. Then, by Lemma 1, b = , such that D b = 2 ,for
D b
k m
some k ≥ 0. Therefore, D b = 2 5 ,for some k,m > 0, and again by the Lemma, b is also a
terminating decimal.
Theorem 2. The set of terminating decimals is not a subset of the set of terminating binimals.

N d k m
Proof. Let d be a terminating decimal such that d = ,where D d = 2 5 .If m> 0, then by
D d
the Lemma, d is a non-terminating binimal.

Answer: The set of terminating binimals is a subset of the set of terminating decimals, but
the set of terminating decimals is not a subset of the set of terminating binimals.