Introduction to Algorithms 6.006 Lecture 23 Jelani NelsonIntroduction to Algorithms 5/5/11 2 Menu • “Numerics” - algorithms for operations on large numbers – Cryptography, simulations, etc • Operations – Addition – Multiplication – Division – Matrix multiplication 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006…Introduction to Algorithms 5/5/11 3 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 answerIntroduction to Algorithms 5/5/11 4 Newton’s method • Iterative approach to solving f(x)=0 – In our case f(x)=1/x-b/R • Iterative step: – Find a line y= f(xi)+f’(xi)(x- xi) tangent to f(x) at xi – Set xi+1 to the solution of f(xi)+f’(xi)(x- xi) =0 I.e., xi+1=xi-f(xi)/f’(xi) -0.2-0.100.10.20.30.40.50.6xi xi+1 fIntroduction to Algorithms 5/5/11 5 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 6 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” convergenceIntroduction to Algorithms 5/5/11 7 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 convergeIntroduction to Algorithms 5/5/11 8 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 divisionsIntroduction to Algorithms 5/5/11 9 Matrix multiplication Input: A = [aij], B = [bij]. Output: C = [cij] = A⋅ B. i, j = 1, 2,… , n. cij = ∑ k aik bkjIntroduction to Algorithms 5/5/11 10 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 11 Divide-and-conquer algorithm n×n matrix = 2×2 matrix of (n/2)×(n/2) submatrices: IDEA: C = A ⋅ B r = ae + bg s = af + bh t = ce + dg u = cf + dh 8 mults of (n/2)×(n/2) submatrices 4 adds of (n/2)×(n/2) submatrices r s t u a b c d e f g h =Introduction to Algorithms 5/5/11 12 Analysis of D&C algorithm nlogba = nlog28 = n3 ⇒ CASE 1 ⇒ T(n) = Θ(n3). No better than the ordinary algorithm. # submatrices submatrix size work adding submatrices T(n) = 8 T(n/2) + Θ(n2)Introduction to Algorithms 5/5/11 13 Strassen’s idea (1969) • 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 s = P1 + P2 t = P3 + P4 u = P5 + P1 – P3 – P7 r s t u a b c d e f g h =Introduction to Algorithms 5/5/11 14 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 + bgIntroduction to Algorithms 5/5/11 15 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 16 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):
View Full Document
Unlocking...