Integer Division

Prev: Multiplication

Next: Integer Division by Constants

Sections

• 9-1 Preliminaries
• 9-2 Multiword Division
• 9-3 Unsigned Short Division from Signed Division
• 9-4 Unsigned Long Division
• 9-5 Doubleword Division from Long Division

Problems

1. Show the real-number identity stated in exercise 1 of this chapter.

2. Find branch-free code for computing the quotient and remainder of modulus division on a basic RISC that has division and remainder instructions for truncating division.

3. Similarly, find branch-free code for computing the quotient and remainder of floor division on a basic RISC that has division and remainder instructions for truncating division.

4. How would you compute $n/d$ for unsigned integers $n$ and $d$, $0\le n\le 2^{32}-1$ and $1\le d\le 2^{32}-1$? Assume your machine has an unsigned divide instruction that computes $n/d$.

5. Theorem D3 states that for real $x$ and integer $d$,

   $$\lfloor x/d\rfloor =\lfloor \lfloor x\rfloor /d\rfloor .$$

   Show that, more generally, if a function $f(x)$ is (a) continuous, (b) monotonically increasing, and (c) has the property that if $f(x)$ is an integer then $x$ is an integer, then $f(\lfloor x\rfloor )=\lfloor f(x)\rfloor$ [GKP].