Great Theoretical Ideas In Computer Science Steven Rudich Lecture 5 CS 15 251 Jan 27 2004 Spring 2004 Carnegie Mellon University On Raising A Number To A Power 15 15 a So Far We Have Seen Don t let the representation choose you CHOOSE THE REPRESENTATION Representation Understand the relationship between different representations of the same information or idea 1 2 3 So Far We Have Seen Induction is how we define and manipulate mathematical ideas 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 k how do we implement b ak with the fewest number of multiplications Powering By Repeated Multiplication Input a n Output A sequence starting with a ending with an and such that each entry other than the first is the product of 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 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 a 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 a 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 Lower Bound M 8 3 Lower Bound 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 3 Lower Bound 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 times 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 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 1s in the binary representation of n Ex B5 2 since 101 is the binary representation of 5 Proposition Bn 6 b log2 n c 1 The length of the binary representation of n is bounded by this quantity 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 log2 n 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 approach to multiplying by the number n The fastest scribes would seek to know M n for commonly arising values of n M n log2 n Bn 1 2 log2 n Abstraction Abstract away the inessential features of a problem or solution We saw that applying ABSTRACTION to the PROBLEM simplifies the issue PROBLEM Raising A Number To A Power Abstraction Abstract away the inessential features of a problem or solution What about ABSTRACTION to the SOLTUTION Let SOLUTION be the Repeated Squaring Algorithm Abstraction Abstraction Abstract away the inessential features of a problem or solution What features did our solution RQA actually make use of Abstraction Abstraction Abstract away the inessential features of a problem or solution For example does the RQA require the underlying objects to be numbers Abstraction Abstraction Abstract away the inessential features of a problem or solution The repeated squaring method works for modular arithmetic and for raising a matrix to a power Abstraction Abstract away the inessential features of a problem or solution The repeated squaring method works for any notion of multiplication that is associative a b c a b c ak is well defined ax ay ax y GENERALIZATION Abstraction Abstraction Abstract away the inessential features of a problem or solution Solution Always yourself what your solution actually requires M 30 6 M n 2b log 2 n c A Lower Bound Idea You can t make any number bigger than 2n in n steps 1 2 4 8 16 32 64 Failure of Imagination Induction Proof Theorem For all n 0 no n stage addition chain will contain a number greater than 2n Let Sk be the statement that no k stage addition chain will contain a number greater than 2k Base case k 0 S0 is …
View Full Document
Unlocking...