Great Theoretical Ideas In Computer Science John Lafferty Lecture 18 CS 15 251 October 27 2005 Fall 2005 Carnegie Mellon University Grade School Revisited How To Multiply Two Numbers 2X2 5 The best way is often far from obvious Gauss a bi c di Gauss Complex Puzzle Remember how to multiply two complex numbers a bi and c di a bi c di ac bd ad bc i Input a b c d Output ac bd ad bc If multiplying two real numbers costs 1 and adding them costs a penny what is the cheapest way to obtain the output from the input Can you do better than 4 02 Gauss 3 05 Method Input a b c d Output ac bd ad bc c c c cc a bi c di ac bd ad bc i X1 a b X2 c d X3 X 1 X2 ac ad bc bd X4 ac X5 bd X6 X 4 X 5 ac bd X7 X3 X4 X5 bc ad The Gauss optimization saves one multiplication out of four It requires 25 less work Time complexity of grade school addition T n The amount of time grade school addition uses to add two n bit numbers We saw that T n was linear T n n Time complexity of grade school multiplication X n2 T n The amount of time grade school multiplication uses to add two n bit numbers We saw that T n was quadratic T n n2 Grade School Addition Linear time Grade School Multiplication Quadratic time t i m e of bits in numbers No matter how dramatic the difference in the constants the quadratic curve will eventually dominate the linear curve Grade school addition is linear time Is there a sub linear time method for addition Any addition algorithm takes n time Claim Any algorithm for addition must read all of the input bits Proof Suppose there is a mystery algorithm A that does not examine each bit Give A a pair of numbers There must be some unexamined bit position i in one of the numbers Any addition algorithm takes n time A did not read this bit at position i If A is not correct on the inputs we found a bug If A is correct flip the bit at position i and give A the new pair of numbers A gives the same answer as before which is now wrong So any algorithm for addition must use time at least linear in the size of the numbers Grade school addition can t be improved upon by more than a constant factor Grade School Addition n time Furthermore it is optimal Grade School Multiplication n2 time Is there a clever algorithm to multiply two numbers in linear time Despite years of research no one knows If you resolve this question Carnegie Mellon will give you a PhD Can we even break the quadratic time barrier In other words can we do something very different than grade school multiplication Grade School Multiplication The Kissing Intuition Intuition Let s say that each time an algorithm has to multiply a digit from one number with a digit from the other number we call that a kiss It seems as if any correct algorithm must kiss at least n2 times Divide And Conquer An approach to faster algorithms 1 DIVIDE a problem into smaller subproblems 2 CONQUER them recursively 3 GLUE the answers together so as to obtain the answer to the larger problem Multiplication of 2 n bit numbers n bits X Y a c n 2 bits X Y b d n 2 bits X a 2n 2 b Y c 2n 2 d X Y ac 2n ad bc 2n 2 bd Multiplication of 2 n bit numbers X Y a c b d n 2 bits n 2 bits X Y ac 2n ad bc 2n 2 bd MULT X Y If X Y 1 then return XY break X into a b and Y into c d return MULT a c 2n MULT a d MULT b c 2n 2 MULT b d Same thing for numbers in decimal n digits X Y a c b d n 2 digits n 2 digits X a 10n 2 b Y c 10n 2 d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 4276 5678 2139 5678 4276 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx 1 2 1 1 2 2 2 1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 1234 4276 5678 2139 5678 4276 12 21 12 39 34 21 34 39 xxxxxxxxxxxxxxxxxxxxxxxxx 2 1 4 2 1 2 1 1 2 2 2 1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Hence 2 102 a 1 4 101 b 2 252 X12 21 Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style …
View Full Document
Unlocking...