ebanner's blog

By ebanner, history, 6 years ago, In English

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 natural number base k 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. ***

As a concrete example consider writing 11 in base 3. By the above declaration we can write the following.

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

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 = 102_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.

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

To see why this is the case note that all the terms except the rightmost term have a modulus of zero (because they contain at least one factor of 3). So doing the modulus has the effect of reading 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^1)     +  0*3^0     + 0
       = 1*(3^1)     +  0*3^0

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

So it looks like we've done the main things required to convert to base k. As a last (and small) order of business notice that we've accumulated digits from right to left and hence they are backwards. We only need to reverse them to straighten them out.

*** A proof of this fact is outside the scope of this guide (I'm sure there is a proof out there somewhere). To convince you that this is true, consider that if it was not true then we wouldn't be able to use binary nor octal nor hexadecimal to represent numbers (why?).

  • Vote: I like it
  • -16
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it