Converting to base k

Revision en2, by ebanner, 2018-04-24 04:58:42

Let's consider the problem of converting a number to base k. Initially I was confused by this algorithm, but the more I think about it the more it makes sense.

The algorithm is this. For a number n in base 10, if we wish to convert n to base k then we do the following.

digits = []
while n > 0:
    digit = n%k
    digits.append(digit)
    n /= k
n_k = reversed(digits)

where n_k is the number n in base k.

Why does this work? Well the first thing to notice is that for any k \in N we can write a number n in base 10 in the following way.

n = sum of i from 0 to infinity of c_i*(k^i)

where 0 <= c_i < k.

For instance if we wish to write 11 in base three we can write it is

11 = 1*3^2 + 0*3^1 + 2*3^0

A proof of this fact is outside the scope of this guide (I'm sure there is a proof out there somewhere).

Now why is this useful? Well if you read off the coefficients from left to right of the above expression that is 11 in base 3!

11_10 = 101_3

where n_k is the number n in base k.

So given this fact, we just need a way to read off the coefficients of each of these terms. Here is an algorithm for doing so.

  1. Read off the rightmost coefficient
  2. Shift all the terms rightwards while eliminating the rightmost term
  3. Go back to step 1

We can accomplish step 1 by doing n % k.

10 % 3 =
(1*3^2 + 0*3^1 + 2*3^0) % 3 = 2

To see why this is the case note that all the terms except the rightmost term have a modulus of zero. This is because each of those terms have a factor of three. So doing the modulus reads off the rightmost coefficient.

Now how do we do step 2. We just do n / k. Let's look and see what that does.

10 / 3 = (1*3^2      + 0*3^1       + 2*3^0) / 3
       = (1*3^2)/3   + (0*3^1)/3   + (2*3^0)/3
       = 1*(3^2)/3   + 0*(3^1)/3   + 2*(3^0)/3
       = 1*[(3^2)/3] + 0*[(3^1)/3] + 2*[(3^0)/3]
       = 1*(3^1)     + 0*3^0 + 0
       = 1*(3^1)     + 0*3^0

Notice the last term zeros out because there is no factor of 3.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English ebanner 2018-04-24 20:34:36 2
en4 English ebanner 2018-04-24 05:16:29 3
en3 English ebanner 2018-04-24 05:13:25 955 (published)
en2 English ebanner 2018-04-24 04:58:42 1326
en1 English ebanner 2018-04-24 04:41:10 1433 Initial revision (saved to drafts)