Ancient Wisdom Unary and Binary 15 251 Lecture 5 September 11 2007 Great Theoretical Ideas in Computer Science Prehistoric Unary 1 2 3 Consider the problem of finding a formula for the sum of the first n numbers You already used induction to verify that the answer is n n 1 4 1 1 2 3 n 1 n n n 1 n 2 2 1 S 1 2 3 n 1 n S n n 1 n 2 2 1 S S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S S n n 1 2S n n 1 2 n 2 1 1 nth Triangular Number n 1 2 3 n 1 n n n 1 2 2 n nth Square Number n n 2 n n 1 2 1 Breaking a square up in a new way 1 3 Breaking a square up in a new way Breaking a square up in a new way 1 3 5 Breaking a square up in a new way 3 1 3 5 7 Breaking a square up in a new way 1 3 5 7 9 Breaking a square up in a new way The sum of the first n odd numbers is n2 1 3 5 7 9 52 Pythagoras Breaking a square up in a new way 4 nth Square Number Here is an alternative dot proof of the same sum nth Square Number n n n 1 n n n 1 n2 nth Square Number n n n 1 n2 5 nth Square Number n n n 1 Check the next one out Sum of first n odd numbers Area of square n 2 Area of square n 2 n 1 n n n 1 n n 6 Area of square n 2 n 1 Area of square n 2 n 1 n 1 n n n 1 n n n n Area of square n 2 Area of square n 2 n 1 2 n n 1 n n n 1 2 n n 1 n n 1 2 n n 1 n 1 n n n n n 1 n 1 2 n n n 1 n 1 n n n n 1 2 n n3 n n 7 n 2 n3 n 1 2 n3 n 1 3 n 2 2 n 2 1 3 2 3 3 3 n3 n n 1 2 2 n3 n 1 3 n 2 3 n 3 2 n3 n 1 3 n 2 3 13 Can you find a formula for the sum of the first n squares Babylonians needed this sum to compute the number of blocks in their pyramids Rhind Papyrus Scribe Ahmes was Martin Gardener of his day A man has 7 houses Each house contains 7 cats Each cat has killed 7 mice Each mouse had eaten 7 ears of spelt Each ear had 7 grains on it What is the total of all of these Sum of powers of 7 8 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 A Frequently Arising Calculation X 1 X 1 1 X1 X2 X3 Xn 2 Xn 1 X1 X2 X3 Xn 1 Xn We ll use this fundamental sum again and again The Geometric Series 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 1 X1 X2 X3 Xn 2 Xn 1 when x 1 Xn 1 X 1 BASE X Representation Geometric Series for X 2 S an 1 an 2 a1 a0 represents the number an 1 Xn 1 an 2 Xn 2 a0 X0 1 21 22 23 2n 1 2n 1 Base 2 Binary Notation 101 represents 1 2 2 0 21 1 20 1 X1 X2 X3 Xn 2 Xn 1 when x 1 Xn 1 X 1 Base 7 015 represents 0 7 2 1 71 5 70 9 BASE X Representation Bases In Different Cultures Sumerian Babylonian 10 60 360 Egyptians 3 7 10 60 Maya 20 Africans 5 10 French 10 20 English 10 12 20 S an 1 an 2 a1 a0 X represents the number an 1 Xn 1 an 2 Xn 2 a0 X0 Largest number representable in base X with n digits X 1 X 1 X 1 X 1 X 1 X 1 X X 1 Xn 1 Xn 2 X0 Xn 1 Fundamental Theorem For Binary Each of the numbers from 0 to 2n 1 is uniquely represented by an n bit number in binary k uses log2k 1 digits in base 2 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 k uses logXk 1 digits in base X 10 n has length n in unary but has length log2n 1 in binary Unary is exponentially longer than binary Other Representations Egyptian Base 3 Conventional Base 3 Each digit can be 0 1 or 2 Here is a strange new one Egyptian Base 3 uses 1 0 1 Example 1 1 1 9 3 1 5 We can prove a unique representation theorem How could this be Egyptian Historically negative numbers first appear in the writings of the Hindu mathematician Brahmagupta 628 AD One weight for each power of 3 Left negative Right positive 11 Unary and Binary Triangular Numbers Dot proofs 1 x x2 xn 1 xn 1 x 1 Base X representations k uses log2k 1 log2 k 1 digits in base 2 Here s What You Need to Know 12
View Full Document
Unlocking...