Transcript Math Plus Fun, Math in Computers

Math in Computers
A Lesson in the “Math + Fun!” Series
Nov. 2005
Math in Computers
Slide 1
About This Presentation
This presentation is part of the “Math + Fun!” series devised
by Behrooz Parhami, Professor of Computer Engineering at
University of California, Santa Barbara. It was first prepared
for special lessons in mathematics at Goleta Family School
during three school years (2003-06). “Math + Fun!” material
can be used freely in teaching and other educational settings.
Unauthorized uses are strictly prohibited. © Behrooz Parhami
Nov. 2005
Edition
Released
First
Nov. 2005
Revised
Math in Computers
Revised
Slide 2
Counters and Clocks
9
Math in Computers
1
8
2
7
3
6
Nov. 2005
0
5
4
Slide 3
A Mechanical Calculator
Photo of the 1874
hand-made version
Photo of production version,
made in Sweden (ca. 1940)
Odhner calculator: invented by Willgodt T. Odhner (Russia) in 1874
Nov. 2005
Math in Computers
Slide 4
The Inside of an Odhner Calculator
197
...08642
+
5365
140 07
Nov. 2005
Math in Computers
Slide 5
Decimal versus Binary Calculator
5
0 2 5
1000 100 10
1
5000 + no hundred + 20 + 5
= Five thousand twenty-five
0
1
2
1
0
1
1
8
4
2
1
8 + no 4 + 2 + 1
= Eleven
3
0
4
After movement by 10 notches
(one revolution), move the next
wheel to the left by 1 notch.
Nov. 2005
After movement by 2 notches
(one revolution), move the next
wheel to the left by 1 notch.
Math in Computers
Slide 6
Decimal versus Binary Abacus
Decimal
Binary
If all 10 beads have moved,
push them back and move
a bead in the next position
Nov. 2005
If both beads have moved,
push them back and move
a bead in the next position
Math in Computers
Slide 7
Other Types of Abacus
Each of these
beads is
worth 5 units
Each of these
beads is
worth 1 unit
3141592654
Display the digit 9 by
shifting one 5-unit bead
and four 1-unit beads
512 256 128 64 32 16
8
4
2
1
0000110110
Display the digit 1 by
shifting one bead
Nov. 2005
Math in Computers
Slide 8
Activity 1: Counting on a Binary Abacus
1. Form a binary abacus with 6 positions, using people as beads
Leader
32
16
8
4
2
A person sits for 0,
stands up for 1
1
2. The person who controls the counting stands at the right end,
but is not part of the binary abacus
3. The leader sits down any time he/she wants the count to go up
4. Each person switches pose (sitting to standing, or standing to sitting)
whenever the person to his/her left switches from standing to sitting
1
0
0
0
1
1
Questions:
What number is shown?
32
Nov. 2005
16
8
4
2
1
Math in Computers
What happens if the
leader sits down?
Slide 9
Activity 2: Adding on a Binary Abacus
1. Form a binary abacus with 6 positions, using people as beads
32
16
8
4
2
A person sits for 0,
stands up for 1
1
2. Show the binary number 0 1 0 1 1 0 on the abacus
This number is
16 + 4 + 2 = 22
32
16
8
4
2
1
0
0
1
1
0
0
This number is
8 + 4 = 12
3. Now add the
binary number
0 0 1 1 0 0 to
the one shown
This number is
32 + 2 = 34
32
Nov. 2005
16
8
4
2
1
Math in Computers
Slide 10
Activity 3: Reading a Binary Clock
Dark = 0
What time is it?
Show the time:
__:__:__
8:41:22
__:__:__
15:09:43
__:__:__
9:15:00
8
4
2
1
min
hour
sec
Light = 1
1 2:3 4:5 6
Each decimal digit is
represented as a 4-bit
binary number.
For example:
1:
6:
0 0 0 1
0 1 1 0
8
Nov. 2005
4
2
1
Math in Computers
Slide 11
Ten-State versus Two-State Devices
To remember one decimal digit,
we need a wheel with 10 notches
(a ten-state device)
IN
OUT 0
1
0
1
0
A binary digit (aka bit) needs just two states
Nov. 2005
Math in Computers
1
0
1


0
1
Slide 12
Addition Table
Binary addition
table
1
+ 0
0
0
1
1
1
10
Write down
in place
Carry over
to the left
Carry over
to the left
Write down
in place
Nov. 2005
Math in Computers
Slide 13
Secret of Mind-Reading Game Revealed
1. Think of a number between 1 and 30.
2. Tell me in which of the five lists below the number appears.
List A: 1 3 5 7
List B: 2 3 6 7
List C: 4 5 6 7
List D: 8 9 10 11
List E: 16 17 18 19
9
10
12
12
20
11
11
13
13
21
13
14
14
14
22
15
15
15
15
23
17
18
20
24
24
19
19
21
25
25
21
22
22
26
26
23
23
23
27
27
25
26
28
28
28
27
27
29
29
29
29
30
30
30
30
Find the number by adding the first entries of the lists in which it appears
B
A
E
D
B
0
0
0
1
1 = 3
1
1
0
1
0 = 26
16
8
4
2
1
16
8
4
2
1
Nov. 2005
Math in Computers
Slide 14
Activity 4: Binary Addition
Binary
addition
table
1
+ 0
0
0
1
1
1
10
Wow! Binary
addition
is a snap!
32
Check:
Think of 5 numbers and add them
Nov. 2005
Math in Computers
8
4
2
1
0 0 1 1 0 0
+ 0 1 1 1 0 1
+ 0 0 0 1 1 1
+ 0 0 1 0 1 1
------------1 1 1 0 1 1
32
Rule: for every pair of 1s in a column,
put a 1 in the next column to the left
16
16
8
4
2
1
12
+ 29
+ 7
+ 11
-------57
Slide 15
Adding with a Checkerboard Binary Calculator
128
64
32
16
8
4
2
1
128
64
32
16
8
32
16
8
4
2
1
2
1
12
+ 29
+ 7
+ 11
59
1. Set up the binary numbers on different rows
2. Shift all beads straight down to bottom row
3. Remove pairs of beads and replace each
pair with one bead in the square to the left
Nov. 2005
Math in Computers
Slide 16
Multiplication Table

Binary
multiplication
table
1
 0
0
0
0
1
0
1
Carry over
to the left
Write down
in place
Nov. 2005
Math in Computers
Slide 17
Activity 5: Binary Multiplication
Binary
multiplication
table
1
 0
0
0
0
1
0
1
I ♥ this simple
multiplication
table!
0 1 1 0
 0 1 0 1
------0 1 1 0
0 0 0 0
0 1 1 0
0 0 0 0
------------0 0 1 1 1 1 0
16
Think of two 3-bit
binary numbers
and multiply them
Nov. 2005
Check:
6
 5
---30
Math in Computers
8
4
2
1
0 1 1 0
 0 1 0 1
------------------1 1 1 1 0
Slide 18
Fast Addition in a Computer
Forget for a moment that computers work in binary
Suppose we want to add the following 12-digit numbers
Is there a way to use three people to find the sum faster?
1st number:
2nd number:
2 7 2 4 3 9 7 2 5 6 2 1
3 1 7 5 6 0 2 7 4 9 8 5
Idea 1: Break the 12-digit addition into three 4-digit additions
and let each person complete one of the parts
0
0
5 8 9 9
1
9 9 9 9
0 6 0 6
This won’t work, because the three groups of digits cannot be
processed independently
Nov. 2005
Math in Computers
Slide 19
Fast Addition in a Computer: 2nd Try
1st number:
2nd number:
2 7 2 4 3 9 7 2 5 6 2 1
3 1 7 5 6 0 2 7 4 9 8 5
Idea 2: Break the 12-digit addition into two 6-digit additions;
use two people to do the left half in two different forms
0
1
5 8 9 9 9 9
0
1
0 0 0 6 0 6
Sum
5 9 0 0 0 0
Once the carry from the right half is known, the correct left-half
of the sum can be chosen quickly from the two possible values
Nov. 2005
Math in Computers
Slide 20
Next Lesson
January 2006
Nov. 2005
Math in Computers
Slide 21