Bases

Bennett Haselton, 2007/03/24

It is possible to memorize algorithms for, for example, converting a base-10 number into base-7. However, it is easier in the long run to understand what bases really represent, and what we mean when we say a number is written in base 10 as "3,264" for example. Once you understand that, it is easy to figure out how to convert from base-10 to base-7 or any other base, without memorizing formulas.

Example problem

Andreea, Erika, and Katharyn are organizing the first national convention for the Organization Of Girls Who Spell Their Own Names Wrong. From the hotel to the convention center, the available forms of transportation are:

The rules are that the available transportation vehicles have to be filled from largest to smallest, and each type of vehicle can only leave when it is completely full.

So, the girls start by filling up the cruise ships (each with a capacity of 1,000) until 3 ships are completely filled, but there aren't enough girls remaining to fill a 4th ship, so the 3 cruise ships depart fully loaded.

At this point, there must be less than 1,000 girls remaining (since there aren't enough to fill up another cruise ship). They start piling into the buses until 2 buses are filled (each with 100 girls), but there aren't enough girls to fill a 3rd bus, so the two buses leave.

We know there are less than 100 girls left (because there weren't enough girls to fill another bus), so the girls start filling the minivans, until 6 minivans are completely full, and those depart. At this point there are only 4 girls left, so they hop onto 4 of the unicycles.

Thus the girls have been divided into groups as follows:

which means of course that the total number of girls is (3 x 1,000) + (2 x 100) + (6 x 10) + 4 = 3,264.

All of which should be obvious using 4th grade math. But suppose you change the capacity of the transportation vehicles:

(In this example, I'm just giving you the fact that the largest vehicle you need -- i.e. the largest power of 7 that you need -- is 74= 2401. Later we'll come back to how you would determine this.)

We know that the total number of girls to transport is 3,264, and we want to transport them using the same rules as before, filling the vehicles from largest to smallest. So we start by filling 1 of the aircraft carriers with 2,401 girls, leaving 3,264 - 2,401 = 863 girls remaining.

With those 863 girls, we can fill 2 cruise ships with 343 girls apiece (but there aren't enough girls to fill a third cruise ship after that). So after filling 2 cruise ships with 343 girls apiece, the number of girls remaining is 863 - (2 x 343) = 177 girls left.

With 177 girls, we can completely fill 3 buses that carry 49 girls apiece. After filling those three buses, the number of girls remaining is 177 - (3 x 49) = 30.

Out of those 30 girls, we can fill 4 buses with 7 girls apiece. Those 4 buses depart, taking 4 x 7 = 28 girls with them, leaving only 2 girls left, and those 2 girls each get their own unicycle.

So the same group of girls has now been divided into groups as follows:

(Note, it is just a coincidence that the first four bolded numbers in this example, turn out to be 1, 2, 3, 4.)

If you add up the sizes of all of those groups, you get (1 x 2,401) + (2 x 343) + (3 x 49) + (4 x 7) + (2 x 1) = 3,264, the number of girls you started with -- which of course is what you'd expect, so that's one way to check your work. But by dividing the girls into groups that are powers of 7, which is what we did above, we also came up with the base-7 representation of the number. This base-7 representation is 123427, which is just the digits written in bold above.

The meaning of the digits in the base-7 number 123427 is similar to the meaning of the base-10 number 3,264. In base 10, we were taught in 2nd grade to think of the "1's digit", the "10's digit", and so on. But if you're learning about bases, by that time you would understand exponents, and it's more organized to think of the 1's digit as the "100 digit", the 10's digit as the "101 digit", the 100's digit as the "102 digit", etc. -- since by this point you know that 100 = 1, and 101 = 10:

This is what the digits mean when the same number is written in base-7:

Some important things to note:

A common source of error is to forget one of those facts -- for example, people see a 5-digit number in base 7, and think the left-most digit is the 75 digit (WRONG, it's the 74 digit!), or think that the right-most digit is the 7's digit (WRONG, it's the 1's digit!).

To convert to base n, finding the highest power of base n that divides that number

In the example above where we had to transport 3,264 people using vehicles whose capacities were powers of 7, I just gave you the fact that the largest required vehicle would carry 74 = 2,401 people. In general though, to convert a number X into base 7, you would have to find the highest power of 7 that is less than or equal to X. For relatively small numbers, this is easy -- start with the number 7, and keep multiplying by 7 until you get a power of 7 that's larger than the number you want to represent:

If you're allowed to use a calculator and you're familiar with logs, then there is a shortcut. Compute log73264 = 4.158. By the laws of logs, this tells you that:

The algorithm for converting a base-10 number X into a different base n

  1. Find the highest power of n that is less than or equal to X. (This can be done by multiplying n by itself until you get a number that is greater than X, or by using the calculator log shortcut above.)
  2. Once you know the highest power of n that divides X, divide X by that power of n. The quotient, the number of times that that power of n goes into X, becomes the first digit of your base-n number. (It's a good idea to label it as you're working -- for example label it as the 74 digit.)
  3. The remainder you carry over to the next step of the problem. Take the next-highest power of n (for example, if you divided by 74 in the last step, this time divide by 73.). Taking the remainder from the last phase of the problem, divide it by the current power of n. The quotient becomes the next digit of your base-n number, and the new remainder you carry over to the next step.
  4. Repeat this cycle until the final remainder you are left with, is less than n. This becomes the last digit of your base-n number. If you haven't made any mistakes, and you've been labelling the digits with decreasing powers of n (the 74 digit, the 73 digit, and so on), then when you fill in the last digit of your result, it should be labeled as the 70 digit, or 1's digit.
  5. (Optional) Check your work by taking the answer and converting back into base 10, to make sure you get the same number you started with.

If you go back to the story problem involving transporting girls on aircraft carriers, ships, buses, minivans and unicycles, this is in fact exactly what we were doing.

Remember to fill in zeroes!

If at any stage in the above algorithm, you do a division and find that the quotient is zero, don't forget to fill in that zero as one of the digits in your answer.

For example, suppose you are transporting 102 girls using the network of unicycles, minivans, etc. listed above where their carrying capacities are powers of 7. The highest power of 7 that is less than 102, is 72 = 49, and 49 fits into 102 twice. So 2 becomes the first digit of our answer, the 72 digit:

We subtract (49 x 2) from 102, leaving a remainder of 4. Now, since in the last round we divided by 72, in this round we divide by 71. 7, of course, does not fit into 4, which means that when you divide 4 by 7, the quotient is 0 and the remainder is 4. But that 0 has to go into the answer -- since we are dividing by 71, the 0 becomes the 71 digit:

As usual, we carry the remainder 4 to the next round. But now we have arrived at the 70 digit (i.e. the "1's digit"), so we just fill in the 4 (what we're really doing is dividing 4 by 70, i.e. dividing 4 by 1, but that amounts to the same thing as just filling in the number 4):

And, remember to fill in the zeroes on the end as well!

If at any stage of the division, you find that your remainder is zero, then don't forget to fill in any remaining digits with zeroes that haven't been filled in yet.

For example, suppose you're transporting 98 girls using the same available vehicles. The highest power of 7 that is less than 98, is 49 again, and 49 goes into 98 exactly twice, with no remainder. So, as before, you fill in the 72 digit:

But now your remainder is zero. In terms of the problem, you have no more girls to transport, so you need zero minivans and zero unicycles. But you still have to fill those digits in, representing the 71 digit and the 70 digit:

Converting from a non-standard base into base 10

Converting from a non-standard base into base 10 is easier. Simply label the digits according to the power of n that they represent, then multiply each digit by the corresponding power of n, and add them all together.

For example, to convert the base-5 number 31025 into base-10, label the digits appropriately, starting from the right:

so the total, converted to base 10, equals:
(3 x 53) + (1 x 52) + (0 x 51 + (2 x 50)
= 375 + 25 + 0 + 2
= 402.

Remember, the digit n never appears in a base-n number! For example, in base 7, you would never actually write the number 7 (or 8 or 9), except the "7" that appears as a subscript that indicates a base-7 number: 123427. In the number itself, the only digits that are available are 0, 1, 2, 3, 4, 5, and 6.

The reason for this is clear if you think back to the examples of aircraft carriers, ships, buses, etc. and remember that vehicles are filled from largest to smallest, and that you can't move on to filling up a smaller class of vehicle until the number of people you have left is not enough to fill up any larger vehicle. (You have to fill ships until you don't have enough girls left to fill a complete ship, and then you move on to filling up buses.) Using the example where the capacities of the vehicles were powers of 7, suppose you've finished filling up the ships and you're now filling up the buses, which can hold 73 girls apiece. A digit of "7" in that column would mean that you were able to fill up 7 buses. But if you filled up 7 buses with 73 girls apiece, that means you must have had 7 x 73 = 74 girls available, and that means that you really could have filled up one more cruise ship (which holds 74 girls) before moving on to the buses. So if you do follow the rules, you'll never end up filling 7 or more buses (or 7 or more minivans, or 7 or more of anything else), because that means you could have filled up one more of the larger vehicles. And that's why the digit 7 never appears in a base-7 number.

This rule is true in everyday base 10 as well, by the way -- no "digit" or "symbol" for the number 10 ever appears in a base-10 number. ("10" is not a symbol, it's the combination of the symbols 1 and 0.)

Binary numbers

Binary, or base-2 numbers, follow all the rules for bases described above. The only two digits in a binary number are 1 and 0.

Converting a base-10 number into binary (and back again) is just a special case of the algorithm given above for converting a base-10 number into a different base. For example, to convert the number 42 into binary:

  1. The highest power of 2 that is less than 42, is 25 = 32. So the first digit of your binary number is 1, the 25 digit. Subtract 32 and you're left with a remainder of 10.
  2. The next-highest power of 2 is 24 = 16. 16 doesn't go into 10. So the 24 digit is 0. The entire remainder, 10, gets carried over to the next step.
  3. The next-highest power of 2 is 23 = 8. 8 goes into 10, once, so the 23 digit is entered as 1. Subtract 8 from 10 and get a remainder of 2.
  4. The next-highest power of 2 is 22 = 4. 4 doesn't go into 2. So the 22 digit is 0. The entire remainder, 2, gets carried over to the next step.
  5. The next-highest power of 2 is 21 = 2. 2 goes into 2, one time, so we enter the digit 1. The remainder is 0, however we're not done yet -- see the section above, "And, remember to fill in the zeroes on the end as well!".
  6. We still have to fill in the 20 digit, so we enter that as 0.
Therefore, 42 in binary would be written as 101010, taking all the digits in bold above, and assembling them together.

Questions

1. All of the previous examples used bases that were less than 10. It is also possible to use bases that are greater than 10, however in that case you need more digits than are available in the normal numbering system, and you need symbols to represent the digit 10, the digit 11, and so on.

By far the most commonly used numbering system with a base higher than 10 is the hexadecimal system used in computers, base 16 ("hexadecimal" i.e. "hex" for 6 and "deci" for 10, where 6 + 10 = 16, get it?). In this system, the digits 10 through 15 are represented by letters:
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15

But otherwise, all the usual rules for converting bases still apply. Knowing this, show that the base-10 number 300, converted into base 16, would be written 12C16. Convert back to base-10 to check your work.


2. We showed that for whole numbers in base-10, the right-most digit represents the 100 digit or "1's digit", the next digit from the right represents the 101 digit, etc., and showed how numbers could be written in base 7 for example using the same rules, but using powers of 7 instead of powers of 10.

Similarly, consider fractional numbers in base 10, such as 4.23. In this number, the 4 is the 100 digit -- and the 2 is the 10-1 digit, and the 3 is the 10-2 digit.

Following the same logic, what do you think the different digits represent in the base-3 fractional number 2.1023? Show that this number equals 211/27 when written as a fraction in the usual way in base 10.


3. You already know that 0.99999... = 1. Similarly, show that the base-2 number which continues forever, 0.111111...2, is equal to 1. Hint: each digit represents a fraction. Write the binary number as an infinite sum of fractions, where it becomes a geometric series.


4. Consider this binary number which continues forever:
0.101010101010...2
Show that this is equal to the fraction 2/3. Hint: again, write the binary number as a sum of fractions so that it becomes another geometric series, this time with a different common ratio from the last problem.