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!

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.

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)

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

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