Transcript 5 - Number Theory 1

Number Systems - Part I
CS 215 Lecture # 5
Motivation



The representation of numbers is
made difficult because of the
discrete nature of computer
representation
Not all numbers can be represented
in a computer
The chosen method of
representation affects the ease by
which arithmetic operations are
performed
Unary Representation


In a unary representation, the
number one is represented by a
single mark, the number two by two
marks, etc.
Unary has limitations:


the number of symbols necessary to
represent a number grows directly with
the value
negative numbers can not be
represented
Roman Numerals
I
V
X
L
C
D
M
1
5
10
50
100
500
1000
•Roman numerals are sorted by decreasing
values
•A symbol representing a smaller value
preceding a symbol representing a larger value
means we have to subtract the smaller value
from the larger value
•Only a single smaller symbol may precede a
larger one
•Only symbols representing powers of ten
(I,X,C) may be placed out of order
Addition in Roman Numerals?
A possible algorithm
 Convert all position sensitive symbols
into
position insensitive form
 Sort by values of symbols
 Merge the two position-insensitive
representations into a single positioninsensitive representation
 Combine lowest-value types into higher valuetypes
 Create legal Roman numerals by converting
back to the unique format
Example 5.1
XIX
(19)
+ MXMV (1995)
 XIX
=
XVIIII
MXMV =
MDCCCCLXXXXV
 XVIIII + MDCCCCLXXXXV = MDCCCCLXXXXXVVIIII
 MDCCCCLXXXXXVVIIII = MDCCCCLXXXXXXIIII =
MDCCCCLLXIIII = MDCCCCCXIIII
= MDCCCCCXIIII = MDDXIIII = MMXIIII
 MMXIIII = MMXIV (2014)
Weighted Positional Notation
Use the position of the symbol to
indicate the value
 By assigning each position the
appropriate power of the base, we
can get a unique representation of
numbers in that base
Decimal System (Base 10)

Given a sequence of n digits d0,d1,…,dn-1
dn-1.10n-1 + … + d1.101 + d0.100

In general, given a sequence of n
digits s0,s1,…,sn-1 and a base b,
sn-1.bn-1 + … + s1.b1 + s0.b0
yields a unique integer N
 s0 is the least significant digit
 sn-1 is the most significant digit
 The most significant symbol can not
be zero



Any positive integer value can be
used as the base or radix for a
weighted positional notation
For bases less than or equal to 10,
a subset of the ten decimal digits
can be used, e.g., binary (base 2)
and octal (base 8)
For bases more than 10, new
symbols will have to be introduced,
e.g., hexadecimal (base16)




We use a subscript to indicate the
base of the number when we are
writing.
In programming languages, octal
representation may be preceded with
a zero (0), e.g., 033.
A hexadecimal representation may be
preceded with 0x, e.g., 0x1b
SAL and MAL use these for
hexadecimal and decimal numbers;
octal is not recognized
Representations in different
radices
binary octal
000
0
001
1
010
2
011
3
100
4
1111
17
hexa
0
1
2
3
4
F
decimal
0
1
2
3
4
15
Hexadecimal and Octal
Hex
Octal
Decimal
Binary
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111


Discriminating only between two
symbols would be far cheaper in
digital circuitry than three, four, etc.
thus binary is the chosen
representation for computers.
Since bits can be grouped into three to
obtain octal value and into four to
obtain hexadecimal value, it is much
easier for humans to work with octal
and hexadecimal representations.
hexadecimal, octal, and binary
To convert the octal or hexadecimal
representation from binary simply group
them starting from the least significant bit
into three for octal and into four for
hexadecimal
Example
binary
11011
octal
011 011
3
3
hexa
0001
1011
1
B
hence: 11011 is 338 or 1B16 or 0x1B or 033
Example 5.2
Convert 11101 to octal
_________
Convert 11101 to hexadecimal
_________
Convert 100110 to octal
_________
Convert 11001100 to hexadecimal_________
Zero and negative numbers



To represent zero, we violate the
rule that says the most significant
symbol can not be zero, and use the
single symbol ‘0’
We can specify, a symbol ‘-’ that is
placed only at the beginning of the
sequence to signify negative
numbers
The absence of or presence of the
symbol ‘+’ signify positive numbers
Conversion into Decimal
Given a sequence of base-r digits sn1...s1s0
convert the sequence into a decimal
number N using:
N = sn-1.bn-1 + … + s1.b1 + s0.b0
Example 5.3
Convert 10 01102 to decimal.
N = 1*25 + 0*24 + 0*23 + 1*22 + 1*21 + 0*20
= 3810
Convert 3b216 to decimal.
N = 3*162 + 1110*161 + 2*160
= 94610
Convert 3708 to decimal.
N = 3*82 + 7*81 + 0*80 = 192 + 56 + 0
= 24810
Example 5.4
Convert the following to decimal:
1. 3467
_______
2. 123
_______
4. 1448
_______
5. 6A16
_______
6. 1002
_______