Math Plus Fun, Math in Computers - UCSB

Math Plus Fun, Math in Computers - UCSB

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 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 1 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 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 Light = 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) OUT 0 1 I N 0 1 0 0 1 Math in Computers 0 1 A binary digit (aka bit) needs just two states Nov. 2005 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 0 1 Math in Computers ---30 5 8 4 2 1 0 1 1 0 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 6 0 2 7 4 9 8 5 3 1 7 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 wont 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 2 7 4 9 8 5 3 1 7 5 6 0 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

Recently Viewed Presentations

  • שקופית 1 - clarita-efraim.com

    שקופית 1 - clarita-efraim.com

    Poster for 'Cycles Perfecta' (1902) In this poster for British company Cycles Perfecta, Mucha expresses the freedom and exhilaration associated with riding a bicycle. The stylised golden hair, one of the hallmarks of his female figures, inhabits the entire poster...
  • Buffer Aggregation

    Buffer Aggregation

    Many transitions 256 transitions per state 50+ distinct transitions per state (real world datasets) Need 50+ words per state Reduce number of transitions in a DFA Three rules a+, b+c, c*d+ 1 3 a a a b b 2 5...
  • 802 LMSC Opening EC meeting - IEEE Standards Association

    802 LMSC Opening EC meeting - IEEE Standards Association

    The IEEE Standards Association reaffirms its commitment to an environment free of discrimination and harassment as stated in the IEEE Code of Conduct, IEEE Code of Ethics, and IEEE Nondiscrimination Policy. IEEE BoD meetings June 2018
  • Higher Processing of Visual Information: Lecture I ---

    Higher Processing of Visual Information: Lecture I ---

    The receptive fields of LGN neurons are concentric with a stronger surround antagonism than that in RGCs, suggesting the LGN is not a simple relay station. (Hubel & Wiesel, 1962) LGN receptive fields Retinotopic Maps Adjacent neurons in the retina...
  • Satire

    Satire

    Satire Defined: sarcasm, irony or wit used to ridicule or mock (poke fun) of something serious. What's the purpose of satire? to use humor in order to ridicule the foolishness or immoral or bad behavior of people or society -...
  • + B. Comm. (International Experience) Advisory Session February

    + B. Comm. (International Experience) Advisory Session February

    The NUI Galway Fees Office will help facilitate you in the processing of grant payments where the student is abroad and cannot sign for the grant if you made contact with them once you have been accepted for transfer to...
  • INTRODUCTION TO ESSAY TYPES By: K. Yegoryan What

    INTRODUCTION TO ESSAY TYPES By: K. Yegoryan What

    The word "essay" means "to try." It is a short piece of non-fiction: an editorial, a feature story or a critical study. The term was first used during the Renaissance ( 16. th. century) by Michel Montaigne who attempted to...
  • For Whom The Booth Tolls - UCSB Physics

    For Whom The Booth Tolls - UCSB Physics

    For Whom The Booth Tolls Brian Camley Pascal Getreuer Brad Klingenberg Problem What causes traffic jams? If there are not enough toll booths, queues will form If there are too many toll booths, a traffic jam will ensue when cars...