# 1.1  Floor and Ceiling

The functions fl and cg, known as the floor and ceiling, respectively, are approximations of reals by integers. The floor is also known as the greatest integer function, because the value of may be characterized as the greatest integer not exceeding :1.1

Definition 1.1.1   (fl-def) For each , is the unique integer that satisifies

Notation: We shall abbreviate as .

The equality in Definition 1.1.1 holds if and only if is an integer:

PROOF: If , then by Definition 1.1.1. On the other hand, if , then since is the unique integer in the half-open interval , Definition 1.1.1 implies

Monotonicity is an immediate consequence of the definition:

PROOF: If , then Definition 1.1.1 implies . By a second application of the same lemma, . Hence, , and the result follows from Definition 1.1.1

PROOF: By Definition 1.1.1 and Lemma 1.1.2,

The following two lemmas are rewrite rules to be used in the simplification of floor expressions.

PROOF: Applying Definition 1.1.1 and shifting by , we have . The result now follows from Definition 1.1.1

PROOF: Since , , and by Lemma 1.1.2, . To derive the reverse inequality, note that since , we have . Now by Corollary 1.1.3, , and hence . Finally, another application of Corollary 1.1.3 yields .

The next result will used in a variety of inductive proofs pertaining to the bit vectors. (See, for example, the proof of Lemma 2.3.22.)

PROOF: It is clear that equality holds for or . If , then

If , then

The floor commutes with negation only for integer arguments:

PROOF: If , then Lemma 1.1.1 implies

Otherwise,

which implies

and by Definition 1.1.1,

When is expressed as a ratio of integers, we also have the following unconditional expression for .

PROOF: Suppose first that . Then

and

Now suppose . Then , which implies , and hence . Thus, we have

and by Definition 1.1.1, . Finally, by Lemma 1.1.7,

Examples:

The ceiling of a real number may be characterized as the least integer not exceeded by . It is defined most conveniently using the floor, as follows.

Definition 1.1.2   (cg) For all , .

Notation: We shall abbreviate as .

The following two essential properties, corresponding to Definition 1.1.1, follow immediately from Definition 1.1.2.

PROOF: By Definition 1.1.1, , which leads to . The lemma now follows from Definition 1.1.2

The next six results correspond to properties of the floor that are listed above.

PROOF: If , then by Lemma 1.1.9. On the other hand, if , then since is the unique integer in the half-open interval , Lemma 1.1.9 implies

PROOF: If , then Lemma 1.1.9 implies . By a second application of the same lemma, . Hence, , and the result follows from Lemma 1.1.9

PROOF: By Lemmas 1.1.9 and 1.1.11,

PROOF: Applying Lemma 1.1.9 and shifting by , we have . The result now follows from Lemma 1.1.9

PROOF: Since , , and by Lemma 1.1.11, . To derive the reverse inequality, note that since , we have . Now by Corollary 1.1.12, , and hence . Finally, another application of Corollary 1.1.12 yields .

The floor and the ceiling are related as follows.

PROOF: If , then of course, . Otherwise, by Lemma 1.1.1, , and hence Definition 1.1.1 yields . Rearranging these inequalities, we have . By Lemma 1.1.9,

David Russinoff 2017-08-01