Algorithms With Numbers

The first of a possible series related to the book Algorithms by Dasgupta, Papadimitriou, and Vazirani. As the preface states, this book is evolved from lecture notes rather than a very formal book. I like the style so far, its less intimidating than purely academic textbooks, but then again, its early days. The first example of an algorithm is for finding a Fibonacci number. As a reminder, the Fibonacci sequence is defined as 0, 1, then (n-1) + (n-2) where n is an index greater than 1. This is a recurrence relation: an equation that recursively defines a sequence once one or more initial terms are given; each further term is defined as a function of the preceding terms. For example, 0 1 1 2 3 5 8 13 21 34. It is the most studied number sequence in existence, according to the book. Its stated that Fibonacci sequence grows almost as fast as 2^n. However, the coefficient for n is 0.694 so that seems somewhat less than close. Graphing these on the same plot, the coefficient is not as impactful as I first thought since the exponential growth relative to n is so extreme.

The general approach given to evaluating algorithms is more brief and understandable but essentially the same as stated in the Art of Programming book: is it correct, how long does it take relative to input size, and can we make it any better? Computing Fibonacci numbers requires many repeated calls to the same function with the same input. With the most basic Fibonacci computing implementation, this fact isn’t taken into account. So yes, it may be correct, but it is slow and we can definitely do better. One way to improve in this case is to store values that we’ve already computed; that is, stop doing the same work over and over again. A solution could be to store these computed values into an array and perform the array lookup instead of the calculation. Implementing this and watching the runtimes, its clear that this new approach is much faster.

#include 
#include 

int fib_1(int input)
{
        int result = 0;
        printf("fib_1(%d)\n", input);
        if (input == 0)
                return 0;
        else if (input == 1)
                return 1;
        else
                return fib_1(input-1) + fib_1(input-2);
}

int fib_2(int input)
{
        int result = 0;
        int fib_numbers[1024];
        fib_numbers[0] = 0;
        fib_numbers[1] = 1;
        for (int i = 2; i <= input; i++) {
                fib_numbers[i] = fib_numbers[i-1] + fib_numbers[i-2];
        }
        return fib_numbers[input];
}

int main()
{
        clock_t start, end;
        double cpu_time_used;

        /*
        start = clock();
        printf("%d\n", fib_1(30));
        end = clock();
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
        printf("runtime: %f\n", cpu_time_used);
        */

        /*
        start = clock();
        printf("%d\n", fib_2(30));
        end = clock();
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
        printf("runtime: %f\n", cpu_time_used);
        */

        return 0;
}

Both functions calculate the 30th Fibonacci number:

fib_1:
832040
runtime: 3.283374

fib_2:
832040
runtime: 0.000071

Leave a Reply