CSE 101 Class NotesDivide & Conquer: Integer Multiplication, Master TheoremOctober 25, 2006Multiplication: First TryWe want the product of two numbers x =Pn−1i=0xi10i, y =Pjyn−1j=010j. Thegrade-school method is O(n2), but we can do a faster version using divide-and-conquer.As an example, let x = 1234, y = 5678. Then1234 × 5678 = (12 × 100 + 34) × (56 × 100 + 78)= (12 × 56)104+ (56 × 34 + 12 × 78)102+ 34 × 78)= ... = 7066652In general,xy = 10nxhyh+ 10n/2(xhyl+ xlyh) + xlylor in pseudocode:1 mult(x[n-1..0],y[n-1..0])2 if n = 13 return lookup(x,y)4 else5 xh <- x[n-1..n/2]; xl <- x[n/2..0]6 yh <- y[n-1..n/2]; yl <- y[n/2..0]7 a <- xh * yh8 b <- xh * yl9 c <- xl * yh10 d <- xl * yl11 bc <- add(b, c)12 a <- append_zeros(a, 2*floor(n/2))13 bc <- append_zeros(bc, floor(n/2))14 return add(a, bc, d)Lines 5-6 take O(n); lines 7-10 take T (n/2) each; lines 11-13 take O(n); sothe total running time isT (n) = 4T (n/2) + O(n)1Running TimeDepth Subproblems Size Subprobem Time Total time0 1 n cn cn1 4 n/2 cn/2 4cn/2 = 2cn· · · · · · · · · · · · · · ·i 4in/2icn/2i4icn/2i= 2icn· · · · · · · · · · · · · · ·log n 4log n= n21 c cn2TOTALPlog ni=02icn = cnPi2i= cn2log n+1− 1= Θ(n2)So this is no better than grade-school multiplication.Second (Clever) TryAs it turns out, we can do better than this by rearranging the work we do inlines 7-10 to reduce the number of subproblems to solve. We need to computethe following expression:(xlyl)10n+ (xlyh+ xhyl)10n/2+ (xhyh)We can compute the three subterms using only three multiplications by recog-nizing that(xlyh+ xhyl) = (xl+ xh)(yl+ yh) − (xlyl) − (xhyh)We already have to compute the last two terms, so by computing (xl+ xh)(yl+yh), we can find the 10n/2-term in one less (recursive) multiplication, by sub-tracting out the last two. Our table then becomes:Depth Subproblems Size Subprobem Time Total time0 1 n cn cn1 3 n/2 cn/2 4cn/2 = 2cn· · · · · · · · · · · · · · ·i 3in/2icn/2i3icn/2i= 1.5icn· · · · · · · · · · · · · · ·log n 3log n= nlog 31 c cnlog 3TOTALPlog ni=01.5icn = cnPi1.5i= cn1.5log n+1−11.5−1≈ cn3log n2log n= Θ(3log n) = Θ(nlog 3)To get an idea of how much an improvement that is,n2nlog 3= n2−log 3is 2.6for n = 10, 17 for n = 1000, and 309 for n = 106.2Master TheoremSo far, to find the running time of divide-and-conquer algorithms, we have filledin a table like the one above. However, if we could fill in this table once for a“generic” divide-and-conquer algorithm, we could simply read off the answer inthe future. Let’s.Depth Subproblems Size Subprobem Time Total time0 1 n cnkcnk1 a n/b c(n/b)kac(n/b)k· · · · · · · · · · · · · · ·i ain/bic(n/bi)kaic(n/bi)k· · · · · · · · · · · · · · ·logbn alogbn= nlogba1 c cnlogbaThe total time falls into one of three cases:• If the algorithm is top-heavy (i.e. a/bk< 1), then the top line of the tabledominates, and T (n) = O(nk).• If the algorithm is balanced (i.e. a/bk= 1), then the total time is the sumof the times at each level, or T (n) = logbnO(nk) = O(nklogbn)• If the algorithm is bottom-heavy (i.e. a/bk> 1), then the table’s height(hence the number of base cases) dominates and T (n) =
View Full Document
Unlocking...