Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 5 CS 15 251 Sept 12 2006 Fall 2006 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 a x b By Repeated Doubling b has 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 b ab b020 b121 b222 bn 12n 1 b020a b121a b222a bn 12n 1a 2ka is in the sum if and only if bk 1 Wait How did the Egyptians do the part where they converted b to binary They used repeated halving to do base conversion 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 Egyptians combined the base conversion by halving and multiplication by doubling into a single algorithm 70 x 13 Rhind Papyrus 1650 BC Binary for 13 is 1101 23 22 20 70 13 70 23 70 22 70 20 Doubling Halving Odd Running Total 70 13 70 140 6 280 3 350 560 1 910 30 x 5 Doubling Halving Odd Running Total 5 30 10 15 10 20 7 30 40 3 70 80 1 150 184 17 Rhind Papyrus 1650 BC Doubling 17 Powers of 2 1 Check 34 2 68 4 136 8 136 x 2 184 184 136 48 so check highest multiple of 17 less than 48 184 17 Rhind Papyrus 1650 BC Doubling 17 Powers of 2 1 Check 34 2 68 4 136 8 136 x 2 184 48 34 14 so don t check anything 184 17 Rhind Papyrus 1650 BC Doubling 17 Powers of 2 1 Check 34 2 68 4 136 8 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 1101 Our story so far We can view numbers in many different but corresponding ways Representation Representation Understand the the relationship relationship between between Understand different representations representations of of the the same same different information or or idea idea information 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 New One Abstraction Abstraction Abstract away away the inessential Abstract inessential featuresof of aa problem problem or features or solution solution And it s twin Abstraction Generalization Abstract away the inessential Realize the inherent general power of features of a problem or solution problem or solution Marcel Duchamp s L H O O Q b a 8 b a a b b a b b a b b a b b a b b a b b a 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 Powering By Repeated Multiplication Input a n Output 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 a 5 a a2 a3 a4 a5 or Output a a2 a3 a5 or Output a a2 a4 a5 Given a constant n how do we implement b an with the fewest number of multiplications Definition of M n M n 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 Very Small Examples What is M 1 M 1 0 a M n Minimum number of multiplications required to produce an from a by repeated multiplication What is M 0 Not clear how to define M 0 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 3 Upper Bound M 8 3 3 M 8 by exhaustive search There are only two sequences with 2 multiplications Neither of them make 8 a a2 a3 and a a2 a4 3 M 8 3 Lower Bound Upper Bound M 8 3 What is the more essential representation of M n Abstraction Abstraction Abstract away the inessential featuresofofaaproblem problem or features orsolution solution Representation Representation Understand the relationship between different represeninformation or ideaidea tations of the same 1 2 3 The a is a red herring a a is a x y x 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 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 Abstraction Abstract away the inessential featuresofofaaproblem problem or features orsolution solution Representation Representation Understand the relationship between different represeninformation or ideaidea tations of the same 1 2 3 15 15 a M 30 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 E g B5 2 since 5 101 2 Proposition Bn b log2 n c 1 Proof It is at most the number of bits in the binary representation of n Binary Method Repeated Doubling Method Phase I Repeated Doubling For b log2 n c 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 Phase I 1 2 4 8 16 Cost 4 additions Phase II 30 11110 2 2 4 6 6 8 14 14 16 30 Cost 3 additions M n b log2 nc Bn 1 2b log2 nc Rhind Papyrus 1650 BC What is 30 x 5 Addition chain for 30 1 2 4 8 16 24 28 30 5 10 20 40 80 120 140 150 Start at 5 and perform same additions as chain for 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 The Egyptian Connection A shortest …
View Full Document
Unlocking...