Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 5 CS 15 251 Sept 13 2005 Fall 2005 Carnegie Mellon University Ancient Wisdom On Raising A Number To A Power 15 15 a Egyptian Multiplication The Egyptians used decimal numbers but multiplied and divided in binary Egyptian Multiplication a times b by repeated doubling b has some n bit representation bn 1bn 2 b1b0 Starting with a repeatedly double largest number so far to obtain a 2a 4a 2n 1a Sum together all the 2ka where bk 1 Why does that work b b020 b121 b 222 bn 12n 1 ab b020a b121a b222a bn 12n 1a If bk is 1 then 2ka is in the sum Otherwise that term will be 0 Wait How did the Egyptians do the part where they converted b to binary They used repeated halving to do base conversion Consider Egyptian Base Conversion Output stream will print right to left Input X repeat if X is even then print 0 else X X 1 print 1 X X 2 until X 0 Sometimes the Egyptian combined the base conversion by halving and multiplication by doubling into a single algorithm Rhind Papyrus 1650 BC 70 13 70 140 280 560 13 6 3 1 70 350 910 Rhind Papyrus 1650 BC 70 13 70 140 280 560 13 6 3 1 70 350 910 Binary for 13 is 1101 23 22 20 70 13 70 23 70 22 70 20 Rhind Papyrus 1650 BC Division 184 17 17 34 68 136 184 48 14 1 2 4 8 Rhind Papyrus 1650 BC Division 184 17 17 34 68 136 1 2 4 8 184 48 14 184 17 8 17 2 14 184 17 10 with remainder 14 This method is called Egyptian Multiplication Division or Russian Peasant Multiplication Division Wow Those Russian peasants were pretty smart Standard Binary Multiplication Egyptian Multiplication 110 1 Our story so far We can view numbers in many different but corresponding ways Representation Understand the relationship between different representations of the same information or idea 1 2 3 Our story so far Induction is how we define and manipulate mathematical ideas Inductionhas many guises Master their interrelationship Formal Arguments Loop Invariants Recursion Algorithm Design Recurrences Let s Articulate A New One Abstraction Abstract away the inessential features of a problem or solution Even very simple computation al problems can be surprisingly subtle Compiler Translation A compiler must translate a high level language e g C with complex operations e g exponentiation into a lower level language e g assembly that can only support simpler operations e g multiplication b a b a a b b a b b a b b a b b a b b a b b a 8 b a a b b b b b b This method costs only 3 multiplications The savings are significant if b a8 is executed often General Version Given a constant n how do we implement b an with the fewest number of multiplications Powering By Repeated Multiplication Input Output a n A sequence starting with a ending with an such that each entry other than the first is the product of two previous entries Example Input Output or Output or Output a 5 a a2 a3 a4 a5 a a2 a3 a5 a a2 a4 a5 Definition of M n M n The minimum number of multiplications required to produce an from a by repeated multiplication What is M n Can we calculate it exactly Can we approximate it Exemplification Try out a problem or solution on small examples Some Very Small Examples What is M 1 M 1 0 a What is M 0 M 0 is not clear how to define What is M 2 M 2 1 a a2 M 8 a a2 a4 a8 is one way to make a8 in 3 multiplications What does this tell us about the value of M 8 M 8 a a2 a4 a8 is one way to make a8 in 3 multiplications What does this tell us about the value of M 8 M 8 3 Upper Bound M 8 3 3 M 8 Exhaustive Search There are only two sequences with 2 multiplications Neither of them make 8 a a2 a3 a a2 a4 3 M 8 Lower Bound 3 Upper Bound M 8 3 Applying Two Ideas Abstraction Abstract away the inessential features of a problem or solution Representation Understand the relationship between different representations of the same information or idea 1 2 3 What is the more essential representation of M n Abstraction Abstract away the inessential features of a problem or solution Representation Understand the relationship between different representations of the same information or idea 1 2 3 The a is a red herring ax ay is ax y Everything besides the exponent is inessential This should be viewed as a problem of repeated addition rather than repeated multiplication Addition Chains M n Number of stages required to make n where we start at 1 and in each subsequent stage we add two previously constructed numbers Examples Addition Chain for 8 12358 Minimal Addition Chain for 8 1248 Addition Chains Are A Simpler Way To Represent The Original Problem Abstraction Abstract away the inessential features of a problem or solution Representation Understand the relationship between different representations of the same information or idea 1 2 3 15 15 a M 30 Some Addition Chains For 30 1 2 4 8 16 24 28 1 2 4 5 10 20 30 1 2 3 5 10 15 30 1 2 4 8 10 20 30 30 M 30 6 M n Binary Representation Let Bn be the number of 1 s in the binary representation of n E g B5 2 since 101 binary representation of 5 Proposition Bn b log2 n c 1 It is at most the number of bits in the binary representation of n Binary Method Repeated Squaring Method Repeated Doubling Method Phase I Repeated Doubling For log2 n stages Add largest so far to itself 1 2 4 8 16 Phase II Make n from bits and pieces Expand n in binary to see how n is the sum of Bn powers of 2 Use Bn 1 stages to make n from the powers of 2 created in phase I Total cost b log2 nc Bn 1 Binary Method Applied To 30 30 Binary 11110 Phase I 1 1 2 10 4 100 8 1000 16 10000 Phase II 6 14 30 Cost 7 additions Rhind Papyrus 1650 BC What is 30 times 5 1 5 2 10 4 20 8 40 16 80 24 120 28 140 30 150 30 by a chain of 7 1 2 4 8 16 24 28 30 Repeated doubling is the same as the Egyptian binary multiplication Rhind Papyrus 1650 BC Actually used faster chain for 30 5 1 2 4 8 10 20 30 5 10 20 40 50 100 150 30 by a chain of 6 1 2 4 8 10 20 30 The Egyptian Connection A shortest addition chain for n gives a shortest method for the Egyptian …
View Full Document
Unlocking...