Posts tagged optimization

Another simple-but-yet-interesting problem that I found challenging solving is the to Write a Fibonacci’s numbers calculator. It’s a REALLY SIMPLE problem, but still can demonstrate how superficial thinking in programming can lead to dramatically bad solutions.

What’s a Fibonacci’s number

A Fibonacci’s number is an integer number generated using the following function:

Assumed that:
f(0) = 0
f(1) = 1

for a generic “n” Integer:
f(n) = f(n-1) + f(n-2)

For example, the first 20 Fibonacci’s number are:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

The young-and-entusiast approach

Recursion! We all love the elegance of it. When we manage to write something that uses Recursions, everything seems easier and simpler to our eyes for a while. BUT, in this particular case, using recursion for implementing such simple task is really bad.

Why? Because at every call to this function, it will generate 2n recursive function calls. A bit of a nightmare for the process call stack if the whole purpose of this thing is calculating a “stupid” integer number.

Functions call tree using a recursive algorithm

Plus, given the nature of the function itself, it will recalculate the same f(x) over and over again, because f(x) is going to be a subproblem shared between a certain y and z, where both y > x and z > x.

Result? An awful implementation. With a quick Big-Oh analysis I would say that the Time Complexity of this “monster” will be O(2ⁿ).
Don’t believe it? Check out the implementation here:

#include <stdio .h>

unsigned long fibonacci_slow(unsigned short i)
{
    if ( i == 0 )
        return (0);

    if ( i == 1 )
        return (1);

    return ( fibonacci_slow(i-1) + fibonacci_slow(i-2) );
}

int main(int argc, char** argv)
{
    unsigned short i, input;
    unsigned long curr = 0, prevprev = 0, prev = 1;

    // Check the Input
	if ( argc == 2 ) input = atoi(argv[1]); else return (1);

	printf("RESULT: fibonacci(%d) = %lu\n\n", input, fibonacci_slow(input));
	return (0);
}

Running it on my Code 2 Duo laptop with n > 40 takes around 10 seconds. For n = 50 I got bored to wait after 1 minute passed by.

If you check out this book, it is going to tell you that such solution is going to take 13 days to come out with a solution, for an average machine (i.e. a machine where O(1) = 0.001 µs).

BUT, of course, I have an alternative solution. Actually, more then one. And the best runs in O(log(n))
More >