15 251 Great Theoretical Ideas in Computer Science Grade School Revisited How To Multiply Two Numbers Lecture 23 November 13 2007 Gauss a bi 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 X1 a b c X2 c d X3 X1 X2 ac ad bc bd X4 ac X5 bd c X6 X4 X5 ac bd ccX7 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 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 quadratic2 T n n Grade School Addition Linear time Grade School Multiplication Quadratic time t i m e of bits in the numbers No matter how dramatic the difference in the constants the quadratic curve will eventually dominate the linear curve 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 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 Divide And Conquer An approach to faster algorithms DIVIDE a problem into smaller subproblems CONQUER them recursively 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 Y c 2n 2 d b n X Y ac 2 ad bc 2n 2 bd Multiplication of 2 n bit numbers X Y a c n 2 bits b d n 2 bits X Y ac 2n ad bc 2n 2 bd MULT X Y If X Y 1 then return XY else 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 1234 2139 1234 4276 5678 21395678 4276 12 21 12 39 34 21 34 39 1 2 1 1 2 2 2 1 2 1 4 2 Hence 12 21 2 102 1 4 101 2 252 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 252 12 39 468 34 21 714 1326 34 39 104 102 102 1 2639526 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 1234 2139 2639526 1234 4276 5276584 12145242 5678 2139 24279128 5678 4276 108 104 104 264126842539128 X a b Y c d X Y ac 10n ad bc 10n 2 bd Multiplying Divide Conquer style 12345678 21394276 264126842539128 X a b Y c d X Y ac 10n ad bc 10n 2 bd Divide Conquer and Glue MULT X Y Divide Conquer and Glue MULT X Y if X Y 1 then return XY else Divide Conquer and Glue MULT X Y X a b Y c d Mult a c Mult a d Mult b c Mult b d Divide Conquer and Glue MULT X Y X a b Y c d Mult a d Mult a c Mult b c Mult b d Divide Conquer and Glue MULT X Y X a b Y c d ac Mult a d Mult b c Mult b d Divide Conquer and Glue MULT X Y X a b Y c d ac Mult b c Mult a d Mult b d Divide Conquer and Glue MULT X Y X a b Y c d ac ad Mult b c Mult b d Divide Conquer and Glue MULT X Y X a b Y c d ac Mult b d ad Mult b c Divide Conquer and Glue MULT X Y X a b Y c d ac ad bc Mult b d Divide Conquer and Glue MULT X Y X a b Y c d ac ad bc Mult b d Divide Conquer and Glue MULT X Y X a b Y c d ac ad bc XY ac2n ad bc 2n 2 bd bd Time required by MULT T n time taken by MULT on two nbit numbers What is T n What is its growth rate Big Question Is it n2 T n 4 T n 2 k n k conquering time divide and glue Recurrence Relation T 1 k for some constant k T n 4 T n 2 k n k for constants k and k Simplified Recurrence Relation T 1 1 T n 4 T n 2 n conquering time divide and glue T n T n 2 n T n 2 T n 2 T n 2 T n n n 2 T T T T n 4 n 4 n 4 n 4 T n 2 T n 2 T n 2 T n n 2 T T T T n 4 n 4 n 4 n 4 n n 2 T T T T n 4 n 4 n 4 n 4 T n 2 T n 2 0 1 n n 2 n 2 n 2 n 2 2 i Level i is the sum of 4i copies of n 2i log2 n 1 1 1 1 1 …
View Full Document
Unlocking...