Difference between revisions of "Base numbers/Conversion"

Revision as of 08:54, 18 November 2006

Converting from base b to base 10

The next natural question is: how do we convert a number from another base into base 10? For example, what does $4201_5$ mean? Just like base 10, the first digit to the left of the decimal place tells us how many $5^0$ 's we have, the second tells us how many $5^1$ 's we have, and so forth. Therefore:

$\displaystyle 4201_5 = (4\cdot 5^3 + 2\cdot 5^2 + 0\cdot 5^1 + 1\cdot 5^0)_{10}$ $=4\cdot 125 + 2\cdot 25 + 1$ $= 551_{10}$

From here, we can generalize. Let $x=(a_na_{n-1}\cdots a_1a_0)_b$ be an $\displaystyle n$ -digit number in base $b$ . In our example ( $2746_{10}$ ) $a_3 = 2, a_2 = 7, a_1 = 4$ and $\displaystyle a_0 = 6$ . We convert this to base 10 as follows:

$x = (a_na_{n-1}\cdots a_1a_0)_b$ $= (b^n\cdot a_n + b^{n-1}\cdot a_{n-1}+\cdots + b\cdot a_1 + a_0)_{10}$

Converting from base 10 to base b

It turns out that converting from base 10 to other bases is far harder for us than converting from other bases to base 10. This shouldn't be a suprise, though. We work in base 10 all the time so we are naturally less comfortable with other bases. Nonetheless, it is important to understand how to convert from base 10 into other bases.

We'll look at two methods for converting from base 10 to other bases.

Method 1

Let's try converting 1000 base 10 into base 7. Basically, we are trying to find the solution to the equation

$1000 = a_0 + 7a_1 + 49a_2 + 343a_3+3401a_4+\cdots$

where all the $\displaystyle a_i$ are digits from 0 to 6. Obviously, all the $\displaystyle a_i$ from $a_4$ and up are 0 since otherwise they will add in a number greater than 1000, and all the terms in the sum are nonnegative. Then, we wish to find the largest $a_3$ such that $343a_3$ does not exceed 1000. Thus, $a_3= 2$ since $2a_3=686$ and $3a_3=1029$ . This leaves us with

$1000 = a_0 + 7a_1 + 49 a_2 + 343(2)\Leftrightarrow 314 = a_0 + 7a_1 + 49 a_2.$

Using similar reasoning, we find that $a_2 = 6$ , leaving us with

$20 = a_0 + 7a_1.$

We use the same procedure twice more to get that $a_1=2$ and $\displaystyle a_0=6$ .

Finally, we have that $1000_{10}=2626_7$ .

An alternative version of method 1 is to find the "digits" $a_0,a_1,\dots$ starting with $a_0$ . Note that $a_0$ is just the remainder of division of $1000$ by $7$ . So, to find it, all we need to do is to carry out one division with remainder. We have $1000:7=142(R6)$ . How do we find $a_1$ , now? It turns out that all we need to do is to find the remainder of the division of the quotient $142$ by $7$ : $142:7=20(R2)$ , so $a_1=2$ . Now, $20:7=2(R6)$ , so $a_3=6$ . Finally, $2:7=0(R2)$ , so $a_4=2$ . We may continue to divide beyond this point, of course, but it is clear that we will just get $0:7=0(R0)$ during each step.

Note that both versions of this method use computations in base $10$ .

It's often a good idea to double check by converting your answer back into base 10, since this conversion is easier to do. We know that $2626_7=343\cdot 2 + 6\cdot 49 + 2\cdot 7 + 6=1000$ , so we can rest assured we got the right answer.

Method 2

We'll exhibit the second method with the same problem used to exhibit the first method.

The second method is just like how we converted from other bases into base 10. To do this, we pretend that our standard number system is base 7. In base 7, however, there is no digit 7. So 7 is actually represented as 10! Also, the multiplication rules we know do not hold. For example, $\displaystyle 3\cdot 3\neq 9$ (in base 7). For one, there is no 9 in base 7. Second, we need to go back to the definition of multiplication to fully understand what's happening. Multiplication is a shorthand for repeated addition. So, $\displaystyle 3\cdot 3 = 3 + 3 + 3 = 12_7$ .

In base 7, we have that 10 (the decimal number 10) is 13. Thus, if we view everything from base 7, we are actually converting $1000_{13}$ to base 10. So, this is just $\displaystyle 13^{3}$ . Remember that we aren't doing this in our regular decimal system, so $13^3\neq 2197$ . Instead, we have to compute $13\times 13\times 13$ as $(13\times 13)\times 13=202\times 13=2626$ .

This method can be very confusing unless you have a very firm grasp on the notion of number systems.

Binary and Hexadecimal

Two of the most common number bases are binary (base 2) and hexadecimal (base 16). Both of these are used in computer science. A binary number consists entirely of 0s and 1s. Each binary digit is called a bit. A base 16 number requires additional symbols after 9 since any positive integer less than 16 is a single digit. The standard notation is to use the letters a=10,b=11,c=12,d=13,e=14,f=15. In order to indicate that a number is written in hexadecimal, the prefix 0x is used. For instance, 0x95 is the same as $\displaystyle 95_{16}$ and is equivalent to $\displaystyle 9 \times 16^1 + 5 = 149$

Examples

1. Convert the binary number 1111 1110 to decimal. (A space is often inserted every 4 digits to improve readability of binary numbers. A group of 4 digits (bits) is called a nible and a group of 8 bits is called a byte)

We could simply add all of the digit values: $0 \times 1 + 1 \times 2 + 1 \times 4 + 1 \times 8 + 1 \times 16 + 1 \times 32 + 1 \times 64 + 1 \times 128$ . But, there is a much shorter way. Note that in base 10, 99 = 10² - 1 and 999 = 10³ - 1. Similarly, in base 2, 11 = 2² - 1, 111 = 2³ - 1, and so on. Therefore, 1111 1111 = 2⁸ -1 = 255. The number we are trying to convert is one less, so it must be 254.

2. Convert the hexadecimal number 0xA7 into decimal.

3. Convert 700 into hexadecimal.

4. Convert 0xF7B9 into binary. (hint: You can do this directly without first converting into decimal)

Resources

Books

The AoPS Introduction to Number Theory by Mathew Crawford.

The Art of Problem Solving Volume 1: the BASICS, pgs. 52-54 by Sandor Lehoczky and Richard Rusczyk.

Classes

AoPS Introduction to Number Theory Course

@@ Line 53: / Line 53: @@
 This method can be ''very'' confusing unless you have a very firm grasp on the notion of number systems.
-=== Binary and Hexadecimal ===
+== Binary and Hexadecimal ==
 Two of the most common number bases are binary (base 2) and hexadecimal (base 16).  Both of these are used in computer science.
 A binary number consists entirely of 0s and 1s.  Each binary digit is called a bit.

Page

Toolbox

Search