15 251 Great Theoretical Ideas in Computer Science Ancient Wisdom On Raising A Number To A Power Lecture 13 October 9 2007 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 Doubling Halving Odd Running Total 70 13 70 140 6 280 3 350 560 1 910 Binary for 13 is 1101 23 22 20 70 13 70 23 70 22 70 20 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 184 17 8 17 2 14 184 17 10 with remainder 14 This method is called Egyptian Multiplication Division or Russian Peasant Multiplication Division Standard Binary Multiplication Egyptian Multiplication 1101 00000000 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 b a8 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 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 log2 n 1 It is at most the number of bits in the binary representation of n Binary 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 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 log2 n Bn 1 2 log2 n 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 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 30 6 M n 2 log2 n A Lower Bound Idea You can t make any number bigger than 2n in n steps 1 2 4 8 16 32 64 or is this a failure of imagination Let Sk be the statement that no k stage addition chain contains a number greater than 2k Base case k 0 S0 is true since no chain can exceed 20 after 0 stages k 0 Sk Sk 1 At stage k 1 we add two numbers from the previous stage From Sk we know that they both are bounded by 2k Hence their sum is …
View Full Document
Unlocking...