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.
- Read off the rightmost coefficient
- Shift all the terms rightwards while eliminating the rightmost term
- 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
.