Quotient and Remainder to Number Base
From ProofWiki
Contents |
[edit] Theorem
Let 
be an integer.
Let n be expressed in base b:
i.e.
![n = \left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b](/w/images/math/9/4/3/943344e7802e7ee42078984b85871328.png)
Then:
![\left \lfloor {\frac n b} \right \rfloor = \left[{r_m r_{m-1} \ldots r_2 r_1}\right]_b](/w/images/math/5/4/1/541ab5d9fe61750d6635d295e6cc7846.png)
where:
-
denotes the floor function;
-
denotes the modulo operation.
[edit] General Result
![\left \lfloor {\frac n {b^s}} \right \rfloor = \left[{r_m r_{m-1} \ldots r_{s+1} r_s}\right]_b](/w/images/math/b/f/6/bf661ce1dfd008eb3c8c469d11e54973.png)
![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](/w/images/math/b/2/2/b22682d3c5adb8cf545851590f290a88.png)
where 
.
[edit] Proof
From the Quotient-Remainder Theorem, we have:
where 
.
We have that:
| n | = | 
| ||||
| = | 
| |||||
| = | 
|
Hence we can express n = qb + r where:
-
- r = r0
where ![\sum_{j = 1}^m {r_{j} b^{j-1}} = \left[{r_m r_{m-1} \ldots r_2 r_1}\right]_b](/w/images/math/2/4/4/24498afcb94b02b71f33f466e08b8aaa.png)
.
The result follows from the definition of the modulo operation.
[edit] Proof of General Result
Follows directly by induction on s.
This article is a stub. Left as an exercise for the student. You can help Proof Wiki by expanding it. If this page/section has already been completed, please remove {{Stub}} from the code.
[edit] Example
This result is often[1] used in computer algorithms for converting a date (in yyyymmdd format) into a date object with separate day, month and year.
Performing the above "mod and div" operations on 20100209, we get:
| = | 09 | which gives us the day | |||
| = | 201002 | which we use as input into the next pass | |||
| = | 02 | which gives us the month | |||
| = | 2010 | which gives us the year. |
[edit] Notes
- ↑ So often, in some business applications, that the author of this page is utterly sick of it, truth be told.
