Complements in Radix r  Euclid's Division Algorithm  Number Systems  
Java Primitive Data Types:  Integers  Reals  Homework 
In the decimal system we can represent a real number as
.
If we use another base say b then
.
We want to convert a decimal number to binary with the arithmetic calculations done in binary. We can use nested multiplication as in Horner's Algorithm to represent a number:
N = (…(a_{n× }10 + a_{n}  1)10 +… + a_{2})10 + a_{1})10 + a_{0}.
The 10 is converted to b = 1010_{2} and each of the a_{i} must be replaced by (a_{i})_{b} = a _{i} (here the computer does a table lookup).
N_{2} = (…(a _{n}× b + a _{n}  1) b +… + a _{2}) b + a _{1}) b + a _{0}.
Now the binary arithmetic is very easy for the computer.
Example
25,431 = 
(((2× 10 + 5)10 + 4)10 + 3)10 + 1, 

= 
(((10× 1010 + 101)1010 + 100)1010 + 11)1010 + 1, 
table lookups, binary arithmetic, 
= 
110001101010111, 
base 2. 
As binary arithmetic is very tedious for us we would prefer to utilize the division algorithm and perform repeated division by the base recording the remainder each time.
Consider N = (…(a
_{n}×
b
+ a
_{n}  1) b
+… + a
_{2}) b
+ a
_{1}) b
+ a
_{0}. Divide both sides of this equation by b
, the remainder is then a
_{0}, repeat and the remainder is a
_{1}, then a
_{2}, etc., until the quotient is 0 and we have recovered N_{b}
in the remainders as
a _{n}…a _{3}a _{2}a _{1}a _{0}.
Example Convert 25,431 to binary using the division algorithm.
2)25431 
2)99 
a _{7} = 0 

2)12715 
a _{0} = 1 
2)49 
a _{8} = 1 
2)6357 
a _{1} = 1 
2)24 
a _{9} = 1 
2)3178 
a _{2} = 1 
2)12 
a _{10} = 0 
2)1589 
a _{3} = 0 
2)6 
a _{11} = 0 
2)794 
a _{4} = 1 
2)3 
a _{12} = 0 
2)397 
a _{5} = 0 
2)1 
a _{13} = 1 
2)198 
a _{6} = 1 
0 
a _{14} = 1 
25,431 = 110001101010111
Converting a fraction to base b is as simple, just use repeated multiplication and recover the integer part each time until the desired accuracy is achieved.
Example Convert 0.1234 to binary.
0.1234 
b_{1} = 0 
. 9488 
b_{6} = 1 
.2468 
b_{2} = 0 
. 8976 
b_{7} = 1 
.4936 
b_{3} = 0 
. 7952 
b_{8} = 1 
. 9872 
b_{4} = 1 
. 5904 
b_{9} = 1 
. 9744 
b_{5} = 1 
. 1808 
b_{10} = 0, etc. 
0.1234 = .0001111110
Now the computer saves a lot of calculation time by using a table lookup. We can do the same thing in our math. Most of us have the binary numbers through 8 memorized. Converting from base 8 to base 2 is just a 3 digit lookup (converting from hexadecimal to binary is just a 4 digit lookup).
Example Covert 25431.1234 to binary by first converting to octal then "looking up" the octal to binary conversion. We will treat the integer and fraction parts separately for now.
8)25431 
.1234 
b_{1} = 0 

8)3178 
a_{0} = 7 
. 9872 
b_{2} = 7 
8)397 
a_{1} = 2 
. 8976 
b_{3} = 7 
8)49 
a_{2} = 5 
. 1808 
b_{4} = 1 
8)6 
a_{3} = 1 
. 4464 
b_{5} = 3 
0 
a_{4} = 6 
6 
1 
5 
2 
7 
. 
0 
7 
7 
1 
3 
110 
001 
101 
010 
111 
. 
000 
111 
111 
001 
011 
Complements in Radix r  Euclid's Division Algorithm  Number Systems  
Java Primitive Data Types:  Integers  Reals  Homework 