Quotient and Remainder to Number Base
From ProofWiki
Contents |
Theorem
Let $n \in \Z: n > 0$ be an integer.
Let $n$ be expressed in base $b$:
- $\displaystyle n = \sum_{j = 0}^m {r_j b^j}$
i.e.
- $n = \left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b$
Then:
- $\displaystyle \left \lfloor {\frac n b} \right \rfloor = \left[{r_m r_{m-1} \ldots r_2 r_1}\right]_b$
- $n \,\bmod\, b = r_0$
where:
- $\left \lfloor {.} \right \rfloor$ denotes the floor function;
- $n \,\bmod\, b$ denotes the modulo operation.
General Result
- $\displaystyle \left \lfloor {\frac n {b^s}} \right \rfloor = \left[{r_m r_{m-1} \ldots r_{s+1} r_s}\right]_b$
- $\displaystyle n \,\bmod\, {b^s} = \sum_{j = 0}^{s-1} {r_j b^j} = \left[{r_{s-1} r_{s-2} \ldots r_1 r_0}\right]_b$
where $s \in \Z: 0 \le s \le m$.
Proof
From the Quotient-Remainder Theorem, we have:
- $\exists q, r \in \Z: n = q b + r$
where $0 \le b < r$.
We have that:
| \(\displaystyle \) | \(\displaystyle n\) | \(=\) | \(\displaystyle \sum_{j = 0}^m {r_j b^j}\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \sum_{j = 1}^m {r_j b^j} + r_0\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle b \sum_{j = 1}^m {r_j b^{j-1} } + r_0\) | \(\displaystyle \) |
Hence we can express $n = q b + r$ where:
- $\displaystyle q = \sum_{j = 1}^m {r_{j} b^{j-1}}$
- $r = r_0$
where:
- $\displaystyle \sum_{j = 1}^m {r_j b^{j-1}} = \left[{r_m r_{m-1} \ldots r_2 r_1}\right]_b$
The result follows from the definition of the modulo operation.
$\blacksquare$
Proof of General Result
Follows directly by induction on $s$.
Example
This result is often
Performing the above "mod and div" operations on $20100209$, we get:
| \(\displaystyle \) | \(\displaystyle 20100209 \,\bmod\, 100\) | \(=\) | \(\displaystyle 09\) | \(\displaystyle \) | which gives us the day | ||
| \(\displaystyle \) | \(\displaystyle \left \lfloor {\frac {20100209} {100} } \right \rfloor\) | \(=\) | \(\displaystyle 201002\) | \(\displaystyle \) | which we use as input into the next pass | ||
| \(\displaystyle \) | \(\displaystyle 201002 \,\bmod\, 100\) | \(=\) | \(\displaystyle 02\) | \(\displaystyle \) | which gives us the month | ||
| \(\displaystyle \) | \(\displaystyle \left \lfloor {\frac {201002} {100} } \right \rfloor\) | \(=\) | \(\displaystyle 2010\) | \(\displaystyle \) | which gives us the year. |
Notes
- ↑ So often, in some business applications, that the author of this page is utterly sick of it, truth be told.