CSCI 161: calculation and efficiency

There are four pairs of algorithms listed below.

For each pair, the algorithm on the left is significantly less effective than the algorithm on the right.

Try implementing the algorithms and testing them to see just how big a difference an intelligent algorithm can make!

  1. Computing m-choose-n
    // m choose n version A
    result = 1
    for i = 1 to m
        result = result * i
    for i = 1 to n
        result = result / i
    for i = 1 to m-n
        result = result / i
    return result
    
    // m choose n version B
    a = max(n, m-n)
    b = min(n, m-n)
    result  1
    for i = 1 to b
       result = result * (a + i) / b
    return result
    

    Additional note: the intermediate values computed by the first algorithm can be much larger than those computed by the second, meaning it runs into overflow problems for much smaller values of m and n.

  2. Recursively computing fibonacci numbers
    // fib(n) version A
    if (n < 0) return 0
    if (n < 2) return 1
    return fib(n-1) + fib(n-2)
    
    // fib(n, v=1, p=0) version B
    // (i.e. an initial call to f(n) is mapped to f(n, 1, 0))
    if (n <= 0) return p 
    if (n == 1) return v
    return fib(n-1,v+p,v)
    

  3. Computing greatest common divisors
    // gcd(a, b) version A
    s = min(a, b)
    gcd = 1
    for c = 2 to s
       if (a mod c) and (b mod c) are both 0
          gcd = c
    return c
    
    // gcd(a, b) version B
    L = max(a,b)
    s = min(a, b)
    while (s > 0)
       t = s
       s = L mod s
       L = s
    return L
    

  4. Generating primes
    // genprimes(n, arr[])  (generate all primes <= n, store in arr)
    numprimes = 0
    for c = 2 to n
        isprime = true
        for f = 2 to c
            if (c mod f) is 0
               isprime = false
        if isprime
            arr[numprimes] = c
            numprimes++
    return numprimes
    
    // genprimes(n, arr[])  (generate all primes <= n, store in arr)
    arr[0] = 2
    arr[1] = 3
    numprimes = 2
    c = 5
    while c <= n
       isprime = true
       i = 0
       f = arr[i]
       while (f*f < c) and isprime
          if (c mod f) is 0
             isprime = false
          else
             i++
             f = arr[i]
       if isprime
          arr[numprimes] = c
          numprimes++
       c += 2
    return numprimes