Ancient Wisdom: On Raising A Number To A PowerSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Study BeeSlide 67Slide 68Slide 69Slide 70Ancient Wisdom:On Raising A Number To A PowerGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2006Lecture 5 Sept 12, 2006 Carnegie Mellon University1515aaThe Egyptians used decimal numbers but multiplied and divided in binaryEgyptian Multiplicationa x b By Repeated Doublingb has n-bit representation: bn-1bn-2…b1b0Starting with a, repeatedly double largest number so far to obtain: a, 2a, 4a, …., 2n-1aSum together all the 2ka where bk = 1ab = b020a + b121a + b222a + … + bn-12n-1a2ka is in the sum if and only if bk = 1 b = b020 + b121 + b222 + … + bn-12n-1Wait! How did the Egyptians do the part where they converted b to binary?They used repeated halving to do base conversion!Egyptian Base ConversionOutput stream will print right to leftInput 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 algorithmBinary for 13 is 1101 = 23 + 22 + 2070*13 = 70*23 + 70*22 + 70*20 70 x 13Rhind Papyrus [1650 BC]7014028056013631* 70350910Doubling Halving Odd? Running Total**30 x 55102040301573*3070Doubling Halving Odd? Running Total**80 1 150*10184 / 17Rhind Papyrus [1650 BC]Doubling Powers of 2 Check1734681361248136 x 2 > 184184 – 136 = 48 so check highest multiple of 17 less than 48**184 / 17Rhind Papyrus [1650 BC]Doubling Powers of 2 Check1734681361248136 x 2 > 18448 – 34 = 14 so don’t check anything**184 / 17Rhind Papyrus [1650 BC]Doubling Powers of 2 Check1734681361248 **184 = 17*8 + 17*2 + 14184/17 = 10 with remainder 14This method is called “Egyptian Multiplication / Division” or “Russian Peasant Multiplication / Division”Wow! Those Russian peasants were pretty smart×1101 * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * *Standard Binary Multiplication= Egyptian MultiplicationWe can view numbers in many different, but corresponding waysRepresentation:Representation:Understand the relationship betweenUnderstand the relationship betweendifferent representations of the samedifferent representations of the sameinformation or ideainformation or idea123Our story so far…Induction is how we define and manipulate mathematical ideasInductionhas many guisesMaster their interrelationship•Formal Arguments•Loop Invariants•Recursion•Algorithm Design•Recurrences Our story so far…AbstractionAbstraction: : Abstract away the inessential Abstract away the inessential features of a problem or solutionfeatures of a problem or solution=Let’s Articulate New One:AbstractionGeneralization: : Abstract away the inessential Realize the inherent general power of features of a problem or solutionproblem or solution=And it’s “twin”Marcel Duchamp’s L.H.O.O.Qb:=a8b:=a*ab:=b*ab:=b*ab:=b*ab:=b*ab:=b*ab:=b*ab:=a*ab:=b*bb:=b*bThis method costs only 3 multiplications. The savings are significant if b:=a8 is executed oftenPowering By Repeated MultiplicationSequence starting with a, ending with an, such that each entry other than the first is the product of two previous entriesInput:Output:a,nExampleInput: a,5Output: a, a2, a3, a4, a5orOutput: a, a2, a3, a5Output: a, a2, a4, a5orGiven a constant n, how do we implement b:=an with the fewest number of multiplications?Definition of M(n)M(n) = Minimum number ofmultiplications required to produce an from a by repeated multiplicationExemplification:Try out a problem or solution on small examplesWhat is M(n)? Can we calculate it exactly? Can we approximate it?Very Small ExamplesWhat 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(n) = Minimum number ofmultiplications required to produce an from a by repeated multiplicationM(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) ≤ 3Upper Bound? ≤ M(8) ≤ 33 ≤ M(8) by exhaustive searchThere are only two sequences with 2 multiplications. Neither of them make 8: a, a2, a3 and a, a2, a4M(8) = 33 ≤ M(8) ≤ 3Lower BoundUpper Bound((( )))AbstractionAbstractionAbstract away the inessential features of a problem or solutionfeatures of a problem or solution=Representation:Representation:Understand the relationshipbetween different represen-information or ideatations of the same idea123What is the more essential representation of M(n)?Everything besides the exponent is inessential. This should be viewed as a problem of repeated addition, rather than repeated multiplicationThe “a” is aaxay is ax+yred herringAddition ChainsNumber of stages required to make n, where we start at 1 and in each stage we add two previously constructed numbersM(n) =ExamplesAddition Chain for 8: 1 2 3 5 8Minimal Addition Chain for 8:1 2 4 8AbstractionAbstractionAbstract away the inessential features of a problem or solutionfeatures of a problem or solution=Representation:Representation:Understand the relationshipbetween different represen-information or ideatations of the same idea123Addition Chains Are a Simpler Way To Represent The Original ProblemM(30) = ?1515aAddition Chains For 301 2 4 8 16 24 28 301 2 4 5 10 20 301 2 3 5 10 15 301 2 4 8 10 20 30? ≤ M(30) ≤ 6? ≤ M(n) ≤ ?Binary RepresentationLet Bn be the number of 1s in the binary representation of nE.g.: B5 = 2 since 5 = (101)2Proposition: Bn ≤ b log2 (n) c + 1 Proof: It is at most the number of bits in the binary representation of nTotal cost: b log2 nc + Bn -1Binary Method(Repeated Doubling Method)For b log2 (n) c stages:Add largest so far to itself(1, 2, 4, 8, 16, . . . )Phase I (Repeated Doubling)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 IBinary MethodApplied To 30Phase I1, 2, 4, 8, 16Phase II30 =
View Full Document