Transcript Essence of Computation - Department of Computer and Information

Essence of Computation
CSCI N201: Programming Concepts
Copyright ©2005  Department of Computer & Information Science
Goals
By the end of the unit, you should understand
• How to define a computer
• The differences between analog and digital
machines
• Understand why we use positional numbering
systems
• Understand how to convert from Base-10 to
Base-2
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Goals (continued)
• Understand how to convert from Base-2 to
Base-10
• Understand how to do simply binary
arithmetic
• How computers encode data
• How computers manipulate data using
the elemental commands
• How the Fetch & Execute Cycle works
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
What is a Computer?
“A computer is a digital machine that is a
universal information manipulator”
Digital Machine – Has tons of accuracy but
limited precision
• Universal – Deals with multiple different types
of data
• Information Manipulator – Has the ability to
take raw data and make it meaningful in
some way
•
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
A Paradox …
“A computer is a digital machine that is a
universal information manipulator”
Does a computer really deal with multiple types
of information?
• Remember, a computer consists of a series of
switches that represent changes in electrical
voltages.
• High voltages are considered “ON” (1) and
low voltages are considered “OFF” (0)
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Computers & Binary Numbering
• Computers are made
of a series of switches
• Each switch has two
states: ON or OFF
• Each state can be
represented by a
number:
– ON is represented by “1”
– Off is represented by “0”
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Starting with Numbers
• Each switch can either have sufficient voltage (“ON”) or
have insufficient voltage (“OFF”).
• Another way of stating voltage: 1 or 0
• This is a common approach in science – to use abstract,
notational systems to describe things.
“1”
“0”
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Light Switch Demo
• Web site:
http://www.cs.iupui.edu/~aharris/binTut/tester.html
• What patterns do you recognize when we add a
switch?
• 1 switch – 2 states; 2 switches – 4 states; 3
switches – 8 states; 4 switches – 16 states …
• There seems to be a “magic” pattern related to
two …
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Using Two Switches
A
B
A
B
OFF
OFF
0
0
OFF
ON
0
1
ON
OFF
1
0
ON
ON
1
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Using Three Switches
A
B
C
A
B
C
OFF
OFF
OFF
0
0
0
OFF
OFF
ON
0
0
1
OFF
ON
OFF
0
1
0
OFF
ON
ON
0
1
1
ON
OFF
OFF
1
0
0
ON
OFF
ON
1
0
1
ON
ON
OFF
1
1
0
ON
ON
ON
1
1
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Using Four Switches
• Complete the table
for four switches …
• How many rows did
you need?
• What patterns do you
recognize?
A
B
C
D
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
You’ve Got the Power (of Two)
• Each time we add a switch, we increase
the number of states by a power of two
(2n)
• And now the that “magic” pattern
unlocked …
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The Magic Pattern
n2
Result
20
21
22
23
24
25
1
2
4
8
16
32
What’s Next?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
It’s A Binary Thing …
• If our notational system is formally described, we can
use mathematics.
• Which is how, from the world of the switch, we find
ourselves doing binary math.
• Consider this shorthand notation for a bank of switch
settings: 1011
• What does it mean? Remember, we are trying to
represent numbers using switches, so how can I
interpret 1011 as a number?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Numbering Systems
• To figure the answer to this question, let’s step back and
look at numbering systems in general.
• Originally, human being counted with tally math
systems, with a mark for each sheep they were counting
– If you had 10 sheep, you made 10 marks
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Numbering Systems
• Later, there were advancements in tally math, using
special symbols for special numbers.
– Instead of 10 marks for 10 sheep, let’s make a special mark for
10 sheep …
=
X
• But this notational system was cumbersome… you had
to learn a lot of symbols, and arithmetic was difficult
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Positional Numbering Systems
• Wonderful advancement over tally math.
• Let’s keep a few, core numbers (digits).
• We can use these digits to represent REALLY big
numbers if we say that the value of a number is
now made up of 2 parts:
– A count value
– A place value
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Place Values
37
• Consider the number 37…
• The 7 stands for 7 (it’s count value) ones (it’s
positional value). Together, 7 times 1 is 7
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Place Values
37
• Consider the number 37…
• The 3 stands for 3 (it’s count value) tens (it’s
positional value). Together, 3 times 10 is thirty
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Place Values
37
• Consider the number 37…
• Total value: 7 (7 * 1, from the ones
position) and thirty (3 * 10, from the 10
position) is 37!
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Place Values
“Tens”
“Ones”
37
3 * 10
7*1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Once More
• Consider 238:
– 8 times 1 = 8
– 3 times 10 = 30
– 2 times 100 = 200
• Grand total = 238
• What do all of our expressions (8 * 1, 3 *
10, 2 * 100) have in common?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Base-10 (Decimal)
• A base refers to the number of digits (counting
numbers) available in a numbering scheme.
• The highest single digit in base is one less than
the base number.
• In Base-10, the digits are:
– 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Base-10 (Decimal)
• What happens after 9?
• The counter in the right column resets itself to
“0” and 1 is added to the value of the next leftmost column:
09
10
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Base-10 (Decimal)
• Interpreting a multiple digit number simply means to expand
its notation, and write it out by each positional value:
742
“Hundreds” “Tens” “Ones”
7 * 100
4 * 10
2*1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Base-10 (Decimal)
• What about using some math to describe the number:
742
102
7 * 102
101
100
4 * 101 2 * 100
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Using Expanded Notation
• We can use our expanded notation to figure the
value of a number:
2
7*10
= 7*100 = 700
1
4*10 = 4*10 = 40
2*100 =
2*1 =
2
= 74210
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
A Note on Subscripts
• We’ve seen superscripts in expressions
before today. In math, they are used to
indicate an exponent in an expression:
y
x
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
A Note on Subscripts
• Let’s introduce one more notation – the
subscript. It is used to indicate the base of
a number (the number of digits available
in a numbering system):
xy
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
A Note on Subscripts
• Remember our previous example?
74210
• It had a subscript of “10”, meaning that the
number we use the Base-10 (Decimal)
numbering system to decode this number.
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Understanding Placeholders
• Each numbering system has
placeholders
• The possible values of each
place holder depends on the
maximum number of singledigit numbers available for
that numbering system
• In the Base-10 world (aka
Decimal), there are ten
possible digits that each
placeholder can take (0-9)
Think of placeholders like an
odometer in a car …
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
From Base-10 to Other Bases
• We can apply the same rules we’ve
learned for Base-10 to all other bases.
• Positional notational systems work the
same, we just need to change our
expressions from Base-10 to the new base
number!
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Base-2 Placeholders
1
Placeholder
Name:
“Ones”
0
“Twos”
1
“Fours”
Number:
n10 Value:
4*1
2*0
1*1
22*1
21*0
20*1
n10 Exponential
Expression:
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Thinking in Binary (Base-2)
• Instead of having 10 digits, the binary (Base-2)
numbering systems has 2 base digits (0 and 1).
– Counting in Base-2: 0, 1, 10, 11, 100, 101, 110, 111, 1000,
1001, 1010 …
• In binary, after the right-most placeholder reaches one,
it resets to 0 and advances the next left-most
placeholder.
• Our base number in binary is 2, therefore we can use
exponents of 2 for placeholder notation
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Placeholders
• Let’s deconstruct 10112:
“Ones”
“Twos”
“Fours”
“Eights”
1011
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Placeholders
• Now, let’s use exponents:
1011
23
22
21
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-2 to Base-10
• Let’s convert 10112.
• STEP 1: Find all
switches that are
turned “OFF”. Cross
them out and bring
down the zero.
1011
23
22
21
20
0
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-2 to Base-10
• STEP 2: For each
placeholder turned
“ON”, calculate its
exponential
expression.
1011
23
22
21
20
8 0 2 1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-2 to Base-10
• STEP 3: Add the
results of the
exponents. The sum
is the Base-10
equivalent.
1011
23
22
21
20
8 + 0 + 2 + 1=
1110
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Review …
• Switches can represent numbers! The notational
system for switches is Base-2
• In Base-2, the digits are 0 and 1; the highest
single number is a 1
• To convert from Base-2 to Base-10, just re-write
the base two number in its expanded form, and
then add the positional values.
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Try a Conversion
• Convert 110102 to it’s Base-10 equivalent.
11010
24
23
22
21
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Try a Conversion
• STEP ONE:
11010
24
23
22
0
21
20
0
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Try a Conversion
• STEP TWO:
11010
24
23
22
21
20
16 8
0
2
0
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Try a Conversion
• STEP THREE:
11010
24
23
22
21
20
16+ 8 + 0 + 2 + 0 =
2610
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Base-10 Placeholders
3
6
Value:
100*4
10*3
1*6
Exponential
Expression:
102*4
101*3
100*6
Placeholder
Name:
“Hundreds”
“Ones”
4
“Tens”
Number:
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
• There are two methods:
– Using exponents of two - n2
– Successive division
• Let’s try exponents first …
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP ONE: Find the largest exponent of two
that is less than or equal to the Base-10
number:
2310=
16
24 23
22
21
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP TWO: Calculate the value of each
exponent and place that value above it:
2310=
16 8
24 23
4
22
2
21
1
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP THREE: Place a “1” above the leftmost placeholder:
2310=
1
16 8
24 23
4
22
2
21
1
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP FOUR: Add left-most value to the next
place-holder. Put a “0” above is the sum is
greater than the number being converted,
otherwise put a “1” above:
2310=
1
0
16 8
24 23
4
22
2
21
1
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP FIVE: Add subsequent placeholders.
If the sum is greater than than the number
being converted, put a “0” above and
disregard it. Otherwise, put a “1” above
and including it in your running total.
2310=
1 0
16 8
24 23
1
4
22
1
2
21
1
1
20
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP SIX: The resulting 1s and 0s in the
top row form the binary equivalent of the
Base-10 number with which we started:
2310 = 101112
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
Now, let’s try successive division …
Remember our problem:
2310 = ?2
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP ONE: Draw a
table with three
columns. Label the
last two columns
quotient and
remainder,
respectively.
Q
R
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP TWO: In the first
available left-most
column, put the
expression 23/2.
Calculate the division and
put the quotient and
remainder in their
respective columns.
23/2
Q
R
11
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP THREE: Take the
quotient of the
previous expression
and divide it by two.
Repeat until have 0
for a quotient.
Q
R
23/2
11
1
11/2
5
1
5/2
2
1
2/2
1
0
1/2
0
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
STEP FOUR: Read the
REMAINDER column
from the bottom to
the top. The 1s and
0s in the remainder
column represent the
binary number.
Q
R
23/2
11
1
11/2
5
1
5/2
2
1
2/2
1
0
1/2
0
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Converting Base-10 to Base-2
2310 = 101112
Q
R
23/2
11
1
11/2
5
1
5/2
2
1
2/2
1
0
1/2
0
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Arithmetic
• Computer processing requires a little more
capability in binary math, notably
arithmetic.
• Let’s consider addition and subtraction …
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
• Just a few combinations are
possible:
– 02 + 02 = 02
– 02 + 12 = 12
– 12 + 02 = 12
• What about 12 + 12?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
12 + 12 = 102
• Remember what that 10 means: it means a
zero in the right column, and a one in the left
column
• When you carry in base two, you are bringing
a power of two to the left…
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Addition
1+ 1+
11102
+10112
=1410
110012
=2510
=1110
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Subtraction
• Subtraction in base two is similar to
addition
– 112 – 112 = 002
– 112 – 002 = 112
– 102 – 002 = 102
• What about 102 - 12?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Subtraction
102 - 12 = 12
• Think about borrowing in decimal – you are really
borrowing a power of your base …
• In Base-10, we borrow 10 from the left column and
give it to the next column to the right. So …
• In Base-2, we borrow 2 from the left column and give
it to the next column to the right.
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Subtraction
0
1
0
1
1
001100112
-000101102
0 0 0 1 1 1 01 2
=5110
=2210
=2910
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Binary Borrowing: A Little Trick
• Many students find it convenient to just mentally convert
the binary number to decimal, complete the subtraction,
and then convert the answer back to binary.
• Consider 102 – 12 = ?
– A one in binary is still a one in decimal
– When you borrow for the zero, you bring over a power of two, which is
equal to two
– The decimal conversion for the borrowing is 2-1, which is 1
– And 110 = 12
• Be sure to add your answer back up as a check
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Computer Data
• Computers are very good
at representing data in
binary (1s and 0s)
• However, computers can
also deal with other data
types:
–
–
–
–
–
Text
Numbers
Graphics
Music
Video
• How?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Storing Integer Numbers
• Convert the integer to binary
• Add a switch for positive/negative
-1910 = -101012
-
1
0
1
0
1
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Storing Floats (Real Numbers)
• Uses two memory positions:
– Store the number, without the decimal point, in one slot
– Store the number of digits to the LEFT of the decimal point in
another slot
123.456710
1234567
3
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Storing Strings
• Need to convert strings to ASCII (American
Standard Code for Information Interchange)
code first
• ASCII code is then converted to Base-2
equivalent:
CHAR
A
B
C
DEC
65
66
67
BIN
1000001
1000010
1000011
D
68
1000100
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Memory
• When a computer works on data, it
processes the data while the data is
housed in memory
• Memory provides very fast access to data
• Memory is volatile (this can be both an
advantage and disadvantage)
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Memory Components
• Memory
– Where data is stored when
a computer is not
processing that data
– Similar to the parking lot in
front of a car repair shop
• Registers
– Where data is stored when
the computer is processing
that data
– Similar to a repair bay
inside a car repair shop
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The Elemental Commands
• Understood by ALL digital computers
• Used to manipulate data
• Commands:
–
–
–
–
–
–
LOAD
STORE
ADD
TEST (COMPARE)
JUMP
HALT
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The LOAD Command
• Take data from a
MEMORY slot and put
the data into a
REGISTER
• Opposite of the
STORE command
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The STORE Command
• Take data from a
REGISTER and put
the data into a
MEMORY slot
• Opposite of the LOAD
command
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The ADD Command
• Add the values of two
REGISTERS
• All other arithmetic
operations can be
derived from add!
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The COMPARE Command
• Compare (test) two
REGISTER values
• Used in conjunction
with the JUMP
command
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The JUMP Command
• Tells the computer to
move to another
command in the list
of instructions
• Used when the
computer’s behavior
should change based
on certain
circumstances
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
The HALT Command
• Indicates the list of
commands is finished
• Without the HALT, the
computer would
process until the end
of memory is reached
– “Out of memory
errors”
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Fetch & Execute Cycle
• Together, a command
list is called the Fetch
& Execute Cycle
• Computer gets
(fetches) a command,
executes it and then
moves on to the next
command
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
ABNIAC
• Computer simulator
• Uses commands similar to the Elemental
Commands
• Includes output options
http://klingon.cs.iupui.edu/~aharris/abniac/java/
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science
Questions?
CSCI N201: Programming Concepts
Copyright ©2004  Department of Computer & Information Science