Quotient and Remainder to Number Base

From ProofWiki

Jump to: navigation, search

Contents

[edit] Theorem

Let n \in \Z: n > 0 be an integer.

Let n be expressed in base b:

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:

  • \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:


[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
  • 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.

[edit] 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:

n = \sum_{j = 0}^m {r_j b^j}                    
= \sum_{j = 1}^m {r_j b^j} + r_0                    
= b \sum_{j = 1}^m {r_{j} b^{j-1}} + r_0                    

Hence we can express n = q b + r where:

  • q = \sum_{j = 1}^m {r_{j} b^{j-1}}
  • r = r_0

where \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


[edit] Proof of General Result

Follows directly by induction on s.


[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:

20100209 \,\bmod\, 100 = 09          which gives us the day          
\left \lfloor {\frac {20100209} {100}} \right \rfloor = 201002          which we use as input into the next pass          
201002 \,\bmod\, 100 = 02          which gives us the month          
\left \lfloor {\frac {201002} {100}} \right \rfloor = 2010          which gives us the year.          


[edit] Notes

  1. ↑ So often, in some business applications, that the author of this page is utterly sick of it, truth be told.
Retrieved from "http://www.proofwiki.org/wiki/Quotient_and_Remainder_to_Number_Base"
Personal tools