Why Study Algorithms?*Important for all branches of computer science *Plays a key role in modern technological innovation *Provides novel ‘lens’ outside of computer science and technology -quantum mechanics, economic markets, evolution *Challenging (i.e., good for the brain!) *Fun Integer MultiplicationInput: two n-digit numbers x and y Output: the product x.y “Primitive Operation”: add or multiply 2 single-digit numbers The Grade-School AlgorithmUpshot: #operations overall <= constant * n**2 The Algorithm Designer’s Mantra “Perhaps the most important principle for the good algorithm designers is to refuse to be content.” Can we do better? Karatsuba MultiplicationExample: X = 5678 Y = 1234 56 = a 78 = b 12 = c 34 = d Step 1: Compute a * c = 672 Step 2: Compute b * d = 2652 Step 3: Compute (a+b)*(c+d) = 134*46 = 6164 Step 4: Compute (3) – (2) – (1) = 2840 Step 5: Pad (1) with 4 zeroes at the end * (2) * pad (3) with 2 zeroes 6720000 * 2652 * 284000 = 7006652 A Recursive AlgorithmWrite x = 10(n/2)a + b and y = 10(n/2)c + d Where a, b, c, d are n/2 – digit numbers [example a =56, b =78, c=12, d=34] x*y = (10(n/2)a+b) (10(n/2)c+d) = 10(n)ac + 10(n/2)(ad+bc) + bd (*simple base case omitted)Idea: recursively compute ac, ad, bc, bd, then compute (*) in the straightforward way Karatsuba Multiplication:x * y = 10(n)ac + 10(n/2)(ad+bc) + bdStep 1: Recursively compute ac Step 2: Recursively compute bd Step 3: Recursively compute (a+b) (cd) = ac + ad + bc + bd Step 4: (3) – (1) – (2) = ad + bc Upshot: Only need 3 recursive multiplications! (and some additions)
0 Comments
## Leave a Reply. |
## AuthorVitali Kremez ## Archives
November 2015
## Categories |