1*104 + 2*103 + 5*102 + 7*101 + 3*100
It turns out that there's absolutely nothing sacred about our choice of 10 for a number radix -- the ancient Babylonians used 60, and the Hebrews used 10 for some purposes and 12 for others (our clock is a vestige of both of these pieces of historical trivia). So, instead of 10, we could use 8, 16, 79, 13... as we please.
In general, we can define any number radix r we want: the digits go from 0 to r-1, and the base is r (so it's 10 for decimal, and so forth).
Let's take a number like 54 10 (5*101 + 4*100). It's easy to verify that 54 = 3*16 + 6, or 3*161 + 6*160. Notice that this has the same form as we used above to ``decode'' a number in radix 10; this tells us that 54 10 = 36 16 . And, it turns out that there is a simple algorithm for converting numbers between any two radixes. We'll get to that in a minute.
A spectacularly useful radix for our purposes is binary: base 2. This is because
Let's take a look at a number like 3510. The first number less than or equal to 35 that is a power of 2 is 32 -- that's 25. So 35 = 32 + 3. We won't use 16, 8, or 4, but we will use use 2 and 1. So 35 is
1*25 + 0 * 24 + 0 * 23 + 0 * 22 + 1*21 + 1*20,which we'll write as
1000112
A little bit later, we'll show a better algorithm for converting between radixes.
Even though binary is a good radix to use in a computer, as we will see more later, to say the least, it's not very convenient for us - writing all those 1's and 0's gets very tedious, very quickly. Fortunately, we can use another radix for our work, which is convenient for us (though not as convenient as decimal!), and also easily converted to binary.
Notice that in a binary number, a group of four bits (this is called a nybble, by the way) can represent a value from 0 to 15. Also, notice that if we divide a number into nybbles, the nybbles start at the 160, 161, 162, ... 16n positions. In other words, nybbles act just like digits in radix 16! That's great - it means we can divide a number up into nybbles, translate each nybble, and have a radix 16 number. More compact to write, easy to translate.
We can see a slight problem with this scheme if we translate 43 into hexadecimal: we get 2*161 + 11*160. But if we look at the number 21116, how can we tell whether it's supposed to be 2*161 + 11*160, or 2*162 + 1*161 + 1*160?
The solution is that we need to come up with some more digits. The convention is to use letters of the alphabet for the numbers from 10 to 15, giving us:
Decimal | Binary | Hexadecimal |
---|---|---|
0 | 0000 | 0 |
1 | 0001 | 1 |
2 | 0010 | 2 |
3 | 0011 | 3 |
4 | 0100 | 4 |
5 | 0101 | 5 |
6 | 0110 | 6 |
7 | 0111 | 7 |
8 | 1000 | 8 |
9 | 1001 | 9 |
10 | 1010 | a |
11 | 1011 | b |
12 | 1100 | c |
13 | 1101 | d |
14 | 1110 | e |
15 | 1111 | f |
One little thing - remember that hexadecimal is a shorthand we use. All numbers internal to the computer are really binary.
We start by looking at what happens when we divide a decimal number by 10. For an example, we'll use 12,573. If we divide it by 10 we get 1,257, with a remainder of 3. The remainder of the division is the least significant digit of the original number. If we divide 1,257 by 10, we get 125 with a remainder of 7 This gave us the next digit. If we keep dividing by the radix, each remainder in turn is another digit.
Let's take our 37 10 and see what happens when we do a bunch of divisions by 2. A convenient way to show this is with a table, where we have one column for the current number we're working with, second for the radix, r, number base, another column for the result of dividing that number by r, and a fourth column for the digits we obtain. It looks like this:
Old | Radix | New | Digit |
---|---|---|---|
37 | 2 | 18 | 1 |
18 | 2 | 9 | 0 |
9 | 2 | 4 | 1 |
4 | 2 | 2 | 0 |
2 | 2 | 1 | 0 |
1 | 2 | 0 | 1 |
Since we obtained the results starting from the least significant digit, we read it starting at the bottom of the rightmost column of the table and working up, and the result is 1001012
This algorithm for converting a number from decimal to binary is called the division algorithm, because we divide on every step. In general, we can convert from decimal to any radix we want using this algorithm, dividing by our intended radix on every step.
Surprisingly, there is a number radix in which this is correct. Let's see if we can find it by using algebra:
Given that the answer in radix 10 is 5410 and is 42r, we want to find r. We can setup the following equation:
4*r + 2 = 54
4*r = 52
r = 13
This algorithm is for converting a number from decimal to a new radix r where we know the digits of the answer. It is called the algebric algorithm, because we set up an algebra equation. In general, we can convert from decimal to any radix we want using this algorithm, given that we know the final digits for the new radix.
Old | Digit | New | Radix |
---|---|---|---|
0 | 1 | 2 | |
0 | 2 | ||
0 | 2 | ||
1 | 2 | ||
0 | 2 | ||
1 |
The way we fill in the table is we do the following on each row:
Old | Digit | New | Radix |
---|---|---|---|
0 | 1 | 1 | 2 |
2 | 0 | 2 | 2 |
4 | 0 | 4 | 2 |
8 | 1 | 9 | 2 |
18 | 0 | 18 | 2 |
36 | 1 | 37 |
The decimal result is in the bottow of the ``New'' column.
I actually don't make any claim that this is easier for people to do than just looking at the positions and multiplying by the right powers. But it's a whole lot easier to put in a computer program!
This is called the multiplication algorithm, as we multiply in each step.
1111 01101010 +01011001 --------- 11000011
3-input lookup table
Inputs | Outputs | |||
---|---|---|---|---|
C in | X | Y | S | C out |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
Hey! Easily defined in terms of logic!
C out = majority(C in , X, Y)