Fibonacci Sequence – Part 3

In Fibonacci Sequence – Part 1, we saw the recursive versions of JavaScript and Perl to calculate the Fibonacci sequences.
The main drawback of them is performance. (To test, try calculating fib(5) and fib(50).)

The formula is fib(n) = fib(n - 1) + fib(n - 2)
Which means that while calculating fib(n - 1), we already calculate fib(n - 2)
But, as it is not stored anywhere, we are again calculating fib(n - 2)
(You might think of some temporary variable to store this value. But, hold on.)
To calculate fib(n - 2), we require fib(n - 3) and fib(n - 4).
We already calculated these values but didn’t store anywhere.
This goes on until fib(3) (We know what fib(2) and fib(1) are, right?).
Hence what we need is a list of temporary variables or just an array.

function fib(n) {
	var t;                       // variable to hold the temporary array
	if(n == 1)      t = [0];     // we know the first two terms
	else if(n == 2) t = [0, 1];  // i.e. for n = 1 or n = 2
	else if(n >= 3) {
		t = fib (n - 1);         // get the previous terms (array and recursion)
        // now calculate the nth term
		t[t.length] = t[t.length - 2] + t[t.length - 1];
	}
	return t;
}
alert(fib(10));

The above JavaScript function gives the list of fibonacci numbers until the nth term.
Now, let us see the beautiful Perl version

use 5.10.0;          # required for the use of given/when construct

sub fib {
	my @t;
	given (pop) {                         # Get the argument and inspect it
		when (1) { @t = (0)    }          # If the arg is 1 then
		when (2) { @t = (0, 1) }          # arg 2
		when ($_ >= 3) {                  # The default variable
			@t     = fib ($_ - 1);        # get the previous terms
			$t[@t] = $t[@t - 2] + $t[@t - 1];   # nth term
		}
	}
	return @t;
}
my @fib = fib($ARGV[0]);
print "@fib\n";

That’s the thing.
Here, we use an array of temporary variables to optimize.
They help us to hold the results of previous calculations.
They help us in reducing the consumptions of CPU cycles.
Please check out the Memoize module on CPAN.

It is not about how fast the hardware do the computations.
It is still in the hands of the programmers to deliver the quality software.

Food for thought: What if we are trying to memorize everything and every other thing?

I have some more things to talk about Fibonnacci Sequence.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s