Intellectual Property and Open Source

Chapter 3. The Patent System

One of the first assignments frequently given to new programming students is the Fibonacci function: given a number n, return the nth number in the Fibonacci sequence. A typical response to this assignment might be coded as follows:

def fib(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: fib(n−1) + fib(n−2)

Unfortunately, this code has a trick: trying to compute fib(n) any numbers larger than 40 or so results in incredibly long running times. In algorithmic terms, this code has complexity O(2ⁿ). In other words, the running time increases exponentially as the number requested goes up. Before n gets very large, the running time is too long to be feasible.

The reason why the fib function is so expensive is because it redoes the work each time. If you ask for fib(5), the function also works out fib(4) and fib(3). The calculation of fib(4) in turn works out fib(3) and fib(2). The calculation of fib(3) works out fib(2) and fib(1), etc. There is a lot of duplicated effort, and that duplicated effort takes work and time.

One technique for speeding up this function is memoization. Memoization works by caching the results of each call in a lookup table. The first time a function is called with certain arguments, the memoized function computes the result and associates the function arguments with the result value. When the function is called later with the same arguments, the memoized function returns the cached value rather than spending time and processing power ...