Unary and BinarySlide 2Mathematical Prehistory: 30,000 BCPrehistoric UnaryPowerPoint UnarySlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17nth Triangular Numbernth Square NumberSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Look at the columns!Slide 32High School NotationSlide 34Slide 35area of new square is ( n)2Slide 37Slide 38Slide 39Slide 40Sumerians [modern Iraq]Slide 42Babylonians absorb SumeriansEgyptiansHarrappans [Indus Valley Culture] Pakistan/IndiaChinaRhind Papyrus: Scribe Ahmes was the Martin Gardener of his day!Rhind Papyrus had 87 Problems.Slide 49A Frequently Arising CalculationAction Shot: Mult by X is a SHIFTThe Geometric SeriesThe Geometric Series for X=2The Geometric Series for X=3The Geometric Series for X=½Slide 56Strings Of Symbols.Strings over the alphabet .Slide 59The set *Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72No Leading Zero Binary (NLZB)Slide 74Slide 75Slide 76BASE X representationBases In Different CulturesSlide 79Fundamental Theorem For Binary: Each of the numbers from 0 to 2n-1 is uniquely represented by an n-bit number in binary.Fundamental Theorem For Base-X: Each of the numbers from 0 to Xn-1 is uniquely represented by an n-“digit” number in base-X.Slide 82Other Representations: Egyptian Base 3Slide 84Slide 85Slide 86Study BeeUnary and BinaryGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 4 Sept 8, 2005 Carnegie Mellon UniversityYour Ancient HeritageLet’s take a historical view on abstract representations.Mathematical Prehistory:30,000 BCPaleolithic peoples in Europe record unary numbers on bones.1 represented by 1 mark2 represented by 2 marks3 represented by 3 marks4 represented by 4 marks…Prehistoric Unary1234PowerPoint Unary1234Hang on a minute! Isn’t unary a bit literal as a representation? Does it deserve to be viewed as an “abstract” representation?In fact, it is important to respect the status of each representation, no matter how primitive. Unary is a perfect object lesson.Consider the problem of finding a formula for the sum of the first n numbers. We already used induction to verify that the answer is ½n(n+1)Consider the problem of finding a formula for the sum of the first n numbers. First, we will give the standard high school algebra proof…1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S 21)(n n S1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2SLet’s restate this argument using a UNARY representationAlgebraic argument1 2 . . . . . . . . n= number of white dots.1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S 1 2 . . . . . . . . n= number of white dots= number of yellow dots n . . . . . . . 2 11 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S n+1 n+1 n+1 n+1 n+1= number of white dots= number of yellow dotsnnnnnnThere are n(n+1) dots in the grid1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S n+1 n+1 n+1 n+1 n+1= number of white dots= number of yellow dotsnnnnnn21)(n n SVery convincing! The unary representation brings out the geometry of the problem and makes each step look very natural.By the way, my name is Bonzo. And you are?Odette.Yes, Bonzo. Let’s take it even further…nth Triangular Numbern = 1 + 2 + 3 + . . . + n-1 + n = n(n+1)/2nth Square Numbern = n + n-1 = n2Breaking a square up in a new way.Breaking a square up in a new way. 1Breaking a square up in a new way. 1 + 3Breaking a square up in a new way. 1 + 3 + 5Breaking a square up in a new way. 1 + 3 + 5 + 7Breaking a square up in a new way. 1 + 3 + 5 + 7 + 9The sum of the first 5 odd numbers is 5 squared 1 + 3 + 5 + 7 + 9 = 52The sum of the first n odd numbers is n squared.PythagorasHere is an alternative dot proof of the same sum….nth Square Numbern = n + n-1 = n2nth Square Numbern = n + n-1 = n2Look at the columns!n = n + n-1Look at the columns!n = n + n-1 = Sum of first n odd numbers.High School Notationn + n-1 = 1 + 2 + 3 + 4 ... + 1 + 2 + 3 + 4 + 5 ... 1 + 3 + 5 + 7 + 9 … Sum of odd numbersHigh School Notationn + n-1 = 1 + 2 + 3 + 4 ... + 1 + 2 + 3 + 4 + 5 ... 1 + 3 + 5 + 7 + 9 … Sum of odd numbersCheck the next one out…( n-1)2 n-1n-1nnnnnnnn + + nnn-1n-1 = n (= n (n n + + n-1n-1)) = n = n nn ==nnNew shaded area = (( nn))2 =2 = (( n-1n-1))2 2 ++nnarea of new square is ( n)2(( nn))2 =2 = (( n-1n-1))2 2 ++nn (( nn))2 2 = = 11 + + 22 + … + + … + nn(( nn))2 =2 = (( n-1n-1))2 2 ++nn ((nn))2 2 = 1= 133 + 2 + 233 + 3 + 333 + … + + … + nn33 = [ = [ n(n+1)/2n(n+1)/2 ] ]22Can you find a formula for the sum of the first n squares? The Babylonians needed this sum to compute the number of blocks in their pyramids.The ancients grappled with problems of abstraction in representation and reasoning. Let’s look back to the dawn of symbols…Sumerians [modern Iraq]Sumerians [modern Iraq]8000 BC Sumerian tokens use multiplesymbols to represent numbers3100 BC Develop Cuneiform writing2000 BC Sumerian tablet demonstrates:base 10 notation (no zero)solving linear equationssimple quadratic equationsBiblical timing: Abraham born in the Sumerian city of UrBabylonians absorb Sumerians1900 BC Sumerian/Babylonian TabletSum of first n numbersSum of first n squares“Pythagorean Theorem”“Pythagorean Triplets”, e.g., 3-4-5some bivariate equations1600 BC Babylonian TabletTake square rootsSolve system of n linear equations6000 BC Multiple symbols for numbers3300 BC Developed Hieroglyphics1850 BC Moscow Papyrus Volume of truncated pyramid1650 BC
View Full Document
Unlocking...