Positional
number systems
Whole numbers
Fractions
Accuracy
Copyright
ã 199395, Thomas P. Sturm

Concept
of a Position Number System
What
does 4,752 (base 10) represent (in base 10)?
4 x 1000 4000 4 x 103
+ 7 x 100 700 7 x 102
+ 5 x 10 50 5 x 101
+ 2 x 1 2 2 x 100
So what does 1011 (base 2) represent
(in base 10)?
1 x 8 8 1 x 23
0 x 4 0 0 x 22
1 x 2 2 1 x 21
1 x 1 1 1 x 20
While this makes a nice definition, it
is far too much work for "practical" use  binary numbers get
to be long

Counting
Revisited
Decimal
Binary Octal Hexadecimal
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13
20 10100 24 14
21 10101 25 15
22 10110 26 16
23 10111 27 17
24 11000 30 18
25 11001 31 19
26 11010 32 1A
27 11011 33 1B
28 11100 34 1C
29 11101 35 1D
30 11110 36 1E
31 11111 37 1F
32 100000 40 20

Faster
Conversion of Binary to Decimal
DibbleDabble,
Horner's Method, Algorithm 1.1
1. Start at the left, start with 0
2. Add in leading digit
3. If there's another digit, multiply
total by 2, add in next digit, repeat this step until you reach the radix
(binary) point.
Ex: 11010 (binary) converted to base 10
is:
0
+ 1
1
x 2
2
+ 1
3
x 2
6
+ 0
6
x 2
12
+ 1
13
x 2
26
+ 0
26

Even
Faster in Your Head
Ex:
11010010110 (binary) converted to base 10 is:
(in your head
1,3,6,13,26,52,105,210,421,843,1686)
Which has just got to be a lot quicker
than
1024
+ 512
+ 128
+ 16
+ 4
+ 2
(not even counting the time it takes to
generate the powers of 2)

Fast
Decimal to Binary Conversion
(DibbleDabble,
Horner's Method, Algorithm 1.2)
Since all even numbers end in 0
(binary), and all odd numbers end in 1 (binary), and since division by 2
yields a 0 remainder for even numbers and a 1 remainder for odd numbers,
the remainder after division by 2 gives you the LSB (least significant
bit) of the corresponding binary number.
Just repeat this process until you get
a 0 quotient
Ex: Convert 75 (decimal) to binary
2  75
2  37 + 1
2  18 + 1
2  9 + 0
2  4 + 1
2  2 + 0
2  1 + 0
0 + 1
Now, the trick to remember, the LSB is
ON TOP, so read the answer from the bottom up:
75 (decimal) = 1001011 (binary)

Converting
Other Bases
Ex:
Convert 17 (base 9) to base 6.
Solution: First convert 17 (base 9) to
base 10, using the first fast conversion algorithm:
1
x9
9
+7
16
Next, convert 16 (base 10) to base 6,
using the second fast conversion algorithm:
6  16
6  2 + 4
0 + 2
Reading up, 17 (base 9) equals 24 (base
6), which both equal 16 (base 10)

Base
8 has a Special Relationship to Base 2
Conversion
between octal and binary is particularly fast and trivial, if you are
careful. Since 23 = 8, every 3 binary digits converts to 1 octal
digit, but you have to start in the correct place  the radix point
The conversion is
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7
Ex. Convert 10110011001111101000 to
octal
Solution: starting at the RIGHT, block
off into groups of 3
10110011001111101000
Now convert groupbygroup to
2631750 (octal)
Conversion from octal to binary is even
easier.
Ex. Convert 307125 to binary
Solution: 011000111001010101, or,
removing the dividing bars and the (useless for now) preceding 0,
11000111001010101

Hexadecimal
to Binary
Hex to
binary is just as quick and trivial, except, since 16 = 24, the
binary numbers are grouped by 4's, and a longer conversion table needs to
be "remembered"



Binary

Hexadecimal


0000

0


0001

1


0010

2


0011

3


0100

4


0101

5


0110

6


0111

7


1000

8


1001

9


1010

A


1011

B


1100

C


1101

D


1110

E


1111

F

Ex: Convert 1011010100001110101101010110011 to hex
Solution: 1011010100001110101101010110011 converts to 5A875AB3
(hex)
Ex: Convert ACD01BF to binary
Solution: 1010110011010000000110111111

Binary
Numbers in Real Machines
Real
computers have a fixed length space for the storage of positive whole
numbers in binary.
First question: How do we store numbers
that are "too short to fit"?
Solution: Add preceding zeroes.
Ex: Show how 5 will be represented in 8
bits
Solution: 101 is only 3 bits long, so
add 5 preceding zeroes to obtain 00000101
Ex: Show how 5 will be represented in
32 bits
Solution:
00000000000000000000000000000101
Second question: What is the largest
number you can store this way in a fixed number of bits?
Solution: In binary it is all 1's,
which is 1 less than 2 to the power of the number of bits!
Ex: What's the largest number that can
be stored in 8 bits
Solution: 11111111 = 100000000  1 =
255
Third question: How many different
numbers can be stored in a fixed number of bits?
Solution: 2 to the number of bits (all
the combinations)
Ex: How many values can be stored in 8
bits
Solution: 256

Estimating
Large Powers of 2
Most
real computers frequently deal with larger collections of bits than 8. The
VAX routinely handles 32 bits at a time (it prefers it to anything
shorter), and can handle collections of 64, 128, and, on rare occasion,
numbers than occupy 256 bits in length. How many combinations of these
numbers are there?
Repeatedly multiplying by 2 to get the
answer will take a long time  and is a waste of time.
Note: 210 = 1024 = 1K @ 1,000
Note: 220 = 210 x 210 = 1024
x 1024 = 1 Meg @ 1,000,000
Note: 230 = 210 x 210 x 210 = 1 Gig
@ 1,000,000,000
250 would have 5 commas
2120 would have 12 commas
Now, all you need to do is get the
LEADING DIGITS of the answer by looking at the power of two of the
TRAILING DIGIT of the exponent
Ex: Estimate 236
Solution: 64,000,000,000
Ex: Estimate 245
Solution: 32,000,000,000,000
Ex: Estimate 2123
Solution:
8,000,000,000,000,000,000,000,000,000,000,000,000

Positional
Number System for Values Less than 1
What
does .475 (base 10) represent (in base 10)?
4 x 101 4 x .1 .4
7 x 102 7 x .01 .07
5 x 103 5 x .001 .005
So what does .1101 (base 2) represent
(in base 10)?
1 x 21 1 x .5 .5
1 x 22 1 x .25 .25
0 x 23 0 x .125 .0
1 x 24 1 x .0625 .0625
This is a totally unreasonable way of
doing this conversion  and there is a way just as fast for fractionals
as there is for whole numbers

Faster
Conversion of Binary Fractions to Decimal
0 + 1 2 1 0.5 + 0 2 0.5 0.25 + 1 2 1.25 0.625 + 1 2 1.625 0.8125
(DibbleDabble, Horner's Method,
Extension of Algorithms 1.1 and 1.2)
1. Start at the right, start with 0
2. Add in the digit
3. Divide by 2
4. If there are more digits to the left, (but to the right of the
binary point), go back to step 2
Ex: .1101 (binary) converted to base 10 is:

Fast
Decimal Fraction to Binary Conversion
(Horner's Method, DibbleDabble,
Extension of Algorithms 1.1 and 1.2)
Use the "inverse" of the method used for integers
Note:
 if a number is between 1/2 and 1, then the first binary digit after
the binary point is a 1
 otherwise , if the number is less than 1/2, the first binary digit
is a 0.
Note:
 if we multiply the decimal number by 2, the whole number we
get is the first binary digit after the binary point.]
Ex: Convert .40625 (decimal) to binary
.40625
x2
0.8125
x2
1.625
x2
1.25
x2
0.5
x2
1.0
Now, the trick to remember is that the MSB is ON TOP, so read the
answer from the top down:
.40625(decimal) = .01101 (binary)

Accuracy
between Binary and Decimal
Note that 0.1 (decimal) does not come
out evenly when converted to binary
.1
x2
0.2
x2
0.4
x2
0.8
x2
1.6
x2
1.2
x2
0.4
x2
0.8
x2
1.6
x2
1.2
x2
0.4
...
.1 (decimal) = .0001100110011001100110011... (binary)
Also, .2, .3, .4, .6, .7, .8, and .9 are not exact
This poses a problem when trying to represent decimal fractions in a
binary computer  always need to worry about accuracy

Accuracy
Conversion
How many binary digits are necessary
to represent a given decimal accuracy?
The proper relationship to examine is
If we know n, solve for m
So, to obtain 8 decimal place accuracy, we need 8/.3 = 26.7 bits of
binary accuracy (in practice, we need at least 27 bits).
Remember quick power of 2 estimation:
3 decimal digits = 10 binary digits
So, going the other way, 60 binary digits will yield 20 decimal place
accuracy.

                               