Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: UNCW Home

Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: UNCW Home

 CSC 133 - Discrete Mathematical Structures

Complements in Radix r
Number Systems
Java Primitive Data Types:  Integers Reals Practice

Conversion of Bases

In the decimal system we can represent a real number as

Sigma notation for a floating point decimal..

If we use another base say b then

Sigma notation for a floating point decimal base B.

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 = (…(an 10 + an - 1)10 +… + a2)10 + a1)10 + a0.

The 10 is converted to b = 10102 and each of the ai must be replaced by (ai)b = a i (here the computer does a table lookup).

N2 = (…(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 Nb in the remainders as

a na 3a 2a 1a 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
x 2
0
.2468

 

b1 = 0

. 9488
x 2
1
.8976

 

b6 = 1

.2468
x 2
0
.4936

 

b2 = 0

. 8976
x 2
1
.7952

 

b7 = 1

.4936
x 2
0
.9872

 

b3 = 0

. 7952
x 2
1
.5904

 

b8 = 1

. 9872
x 2
1
.9744

 

b4 = 1

. 5904
x 2
1
.1808

 

b9 = 1

. 9744
x 2
1
.9488

 

b5 = 1

. 1808
x 2
0
.3616

 

b10 = 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
x 8
0
.9872

 

b1 = 0

8)3178

a0 = 7

. 9872
x 8
7
.8976

 

b2 = 7

8)397

a1 = 2

. 8976
x 8
7
.1808

 

b3 = 7

8)49

a2 = 5

. 1808
x 8
1
.4464

 

b4 = 1

8)6

a3 = 1

. 4464
x 8
3
.5712

 

b5 = 3

0

a4 = 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
Number Systems  
Primitive Data Types:  Integers Reals Practice

Back by J. A. Tompkins tompkinsj@uncw.edu