Transcript ALG1.0
Introduction: Efficient Algorithms for the Problem of Computing Fibonocci Numbers Analysis of Algorithms Prepared by John Reif, Ph.D. Readings • Main Reading Selection: – CLR, Chapter 1 Goal • Devise Algorithms to solve problems on a TI calculator • assume each step (a multiplication, addition, or control branch) takes 1 m sec = 10-6 sec on 16 bit words Time Efficiency Fibonocci Sequence • 0, 1, 1, 2, 3, 5, 8, 13… • Recursive Definition • Fn = if n < 1 then n else Fn-1 + Fn-2 • Problem • Compute Fn for n=109 fast. Fibonacci Growth • Can show as n ∞ ( ) n Fn ~ n 5 • Golden ratio 1 5 1.62... 2 • So Fn ~ .45 ∙ 2 .7n is .7n bit number grows exponentially! Obvious Method • Fn = n if n < 1 Fn-1 + Fn-2 if n > 1 costs at least n adds of 2 .7n .35n bit numbers 2 n .35n bits Total Cost adds 2 16 bits > .01 n2 steps > 1016 m sec for n = 109 = 1010 sec ~ 317 years! Wanted! • An efficient algorithm for Fn • Weapons: • Special properties of computational problems = combinatorics (in this case) Theorem: 11 10 n Fn Fn 1 F F n 1 n • Proof by Induction – Basis Step • Holds by definition for n=1 – Inductive Step • Assume holds for some n>0 Inductive Step n 1 11 1 1 Fn 1 Fn 10 1 0 Fn Fn 1 Fn 1 Fn Fn Fn 1 Fn Fn 1 Fn 2 Fn 1 Fn 1 Fn Powering Trick • Fix M = 1 1 1 0 • To compute Mn when n is a power of 2 For i=1 to log n do M M M 2i 2i-1 2i-1 2 22 gives M, M , M , ... M 2 logn General Case of Powering • Decompose n = 2 j1 + 2 as sum of powers of 2 • Example • Compute j2 + ... + 2 23 2 4 2 2 21 20 16 4 2 1 10111 2 M = n ÕM i=1,...,k 2 ji jk Algorithm 1 1 M 10 2 (1) compute M, M , ..., M 2 logn by power method (2) if n = 2 + 2 +... + 2 then M = j1 j2 jk n ÕM i=1,...,k (3) output Fn = upper right of M n 2 ji Bounding Mults • = 2 log n matrix products on symmetric matrices of size 2 x 2 • Each matrix product costs 6 integer mults • Total Cost = 12 (log n) integer mults > 360 for n = 109 integer mults Time Analysis • Fn ~ .45 2 .7n • So Fn is m = .7n bit integer • New method to compute Fn requires multiplying m bit number • BUT • Grammar School Method for Mult takes m2 bool ops = m2/16 steps ~ 1016 steps for n = 109 ~ 1016 msec ~ 1010 seconds ~ 317 years! Fast Multiplication of m bit integers a,b by • “Divide and Conquer” a a L 2k a R b bL 2 bR k aL bL aR bR m where k 2 a b a L b L 2 2k (a L b R a R b L )2 k a R b R • seems to take 4 multiplications, but… 3 Mult Trick: Karatsubu Algorithm (1) x a L b L (2) y a R b R (3) z (a L a R ) (b L b R ) (x y) a LbR a R bL Requires only 3 mults m on - bit integers and 6 adds on m - bits 2 a b a L b L 2 2k (a L b R a R b L )2 k a R b R x 2 z2 y 2k k Recursive Mult Algorithm • Cost C m bit ops C1 1 C m 3C m 6m for m 1 2 i 3 6m i 0 2 log m 3 2 log m 6m 6m log2 3 ~ 6m1.4 bit ops ~ 1013 bit ops if m .7 109 13 10 ~ steps 16 ~.05 years Schonhage-Strassen Integer Multiplication Algorithm 10m log m log log m bit ops ~ .7 1012 bit ops for m .7 109 ~ 4.3 1010 steps ~4.3 104 sec. ~3 days • This is feasible to compute! Improved Algorithm • Computed Fn for n = 109 using 360 = 12 log n integer mults each taking ~ 3 days • Total time to compute Fn • ~ 3 years with 1 msec/step How Did We Get Even More Speed-Up? 1) New trick • a 2 log n mult algorithm (rather than n adds) 2) Old Trick • use known efficient algorithms for integer multiplication (rather than Grammar School mult) 3) Also used careful analysis of efficiency of algorithms to compare methods Problem (to be pondered later…) • How fast can 109 integers be sorted? • What algorithms would be used? Introduction: Efficient Algorithms for the Problem of Computing Fibonocci Numbers Analysis of Algorithms Prepared by John Reif, Ph.D.