Introduction to Algorithms 6 006 Lecture 23 Jelani Nelson Menu Numerics algorithms for operations on large numbers Cryptography simulations etc Operations Addition Multiplication Division Matrix multiplication Introduction to Algorithms 3 14159265358979323846264338327950288419 7169399375105820974944592307816406286208 9986280348253421170679821480865132823066 4709384460955058223172535940812848111745 0284102701938521105559644622948954930381 9644288109756659334461284756482337867831 6527120190914564856692346034861045432664 8213393607260249141273724587006 5 5 11 2 Division a b Inversion Given positive n digit number b radix r Compute 1 b I e for some R rk compute R b Iterative algorithm Start from some x0 Keep computing xi 1 from xi Show this converges to the answer Introduction to Algorithms 5 5 11 3 Newton s method Iterative approach to solving f x 0 In our case f x 1 x b R Iterative step Find a line 0 6 0 5 0 4 f 0 3 0 2 y f xi f xi x xi tangent to f x at xi Set xi 1 to the solution of 0 1 0 0 1 xi xi 1 0 2 f xi f xi x xi 0 I e xi 1 xi f xi f xi Introduction to Algorithms 5 5 11 4 Division algorithm Want to solve f x 1 x b R 0 We have f x 1 x2 Iterative step xi 1 xi f xi f xi yields xi 1 xi xi2 1 xi b R I e xi 1 2xi xi2b R Only O 1 multiplications shifts and subtractions Convergence Introduction to Algorithms 5 5 11 5 Convergence of xi 1 2xi xi2b R Assume xi R b 1 ei ei error Assumptions ei is small Ignore the round off errors caused by the R operation How does each iteration affect ei xi 1 2xi xi2b R 2R b 1 ei R b 1 ei 2 b R R b 2 2ei 1 2ei ei2 R b 1 ei2 R b 1 ei 1 where ei 1 ei2 We have ei 1 ei 2 quadratic convergence Introduction to Algorithms 5 5 11 6 Quadratic convergence ei 1 ei 2 If we start close enough say e0 1 2 then the convergence is very fast e1 e0 2 e2 e0 2 2 ei e0 2 i 1 22 i To make sure we get k digits of precision we need ei 1 rk 1 22 i 1 rk i log2 k log2 r What if e0 1 2 Heuristically can apply the same algorithm Analysis much more complicated Does not always converge Introduction to Algorithms 5 5 11 7 General method E g square roots f x x2 a xi 1 xi xi2 a 2 xi xi a xi 2 Only O 1 multiplications subtractions and divisions Introduction to Algorithms 5 5 11 8 Matrix multiplication Input A aij B bij Output C cij A B i j 1 2 n cij k aik bkj Introduction to Algorithms 5 5 11 9 Standard algorithm for i 1 to n do for j 1 to n do cij 0 for k 1 to n do cij cij aik bkj Running time n3 Introduction to Algorithms 5 5 11 10 Divide and conquer algorithm IDEA n n matrix 2 2 matrix of n 2 n 2 submatrices rs tu r s t u ae bg af bh ce dg cf dh C a b cd A ef gh B 8 mults of n 2 n 2 submatrices 4 adds of n 2 n 2 submatrices Introduction to Algorithms 5 5 11 11 Analysis of D C algorithm T n 8 T n 2 n2 submatrices submatrix size work adding submatrices nlogba nlog28 n3 CASE 1 T n n3 No better than the ordinary algorithm Introduction to Algorithms 5 5 11 12 Strassen s idea 1969 rs tu ab cd ef gh Multiply 2 2 matrices with only 7 recursive mults P1 a f h P2 a b h r P5 P4 P2 P6 P3 c d e s P1 P2 P4 d g e t P3 P4 P5 a d e h u P5 P1 P3 P7 P6 b d g h P7 a c e f Introduction to Algorithms 5 5 11 13 Strassen s idea Multiply 2 2 matrices with only 7 recursive mults P1 a f h P2 a b h P3 c d e P4 d g e P5 a d e h P6 b d g h P7 a c e f r P5 P4 P2 P6 a d e h d g e a b h b d g h ae ah de dh dg de ah bh bg bh dg dh ae bg Introduction to Algorithms 5 5 11 14 Strassen s algorithm 1 Divide Partition A and B into n 2 n 2 submatrices Form terms to be multiplied using and 2 Conquer Perform 7 multiplications of n 2 n 2 submatrices recursively 3 Combine Form C using and on n 2 n 2 submatrices T n 7 T n 2 n2 Introduction to Algorithms 5 5 11 15 Analysis of Strassen T n 7 T n 2 n2 nlogba nlog27 n2 81 CASE 1 T n nlg 7 Best to date of theoretical interest only n2 376 Introduction to Algorithms 5 5 11 16
View Full Document
Unlocking...