Fibonacci Sequence – Part 5

create package fib_pkg
as
    function fib_iteration(n number) return number;
    function fib_recursion(n number) return number;
end fib_pkg;
/

Package created.

create package body fib_pkg
as
    function fib_iteration(n number) return number
    is
        first   number := 0;
        second  number := 1;
        current number;
    begin
        for i in 3 .. n loop
            current := first + second;
            first   := second;
            second  := current;
        end loop;
        return current;
    end fib_iteration;
    function fib_recursion(n number) return number
    is
    begin
         if n = 1 or n = 2 then
            return n - 1;
         end if;
         return fib_pkg.fib_recursion(n - 1) + fib_pkg.fib_recursion(n - 2);
    end fib_recursion;
end fib_pkg;
/

Package body created.

set serveroutput on
var n number
exec :n := fib_pkg.fib_iteration(10);

PL/SQL procedure successfully completed.


print n

         N
----------
        34

exec :n := fib_pkg.fib_recursion(10);

PL/SQL procedure successfully completed.


print n

         N
----------
        34

Now, we are seeing the Oracle PL/SQL version for generating the Fibonacci Sequence.
No need to mention that I used SQL*Plus to create/execute the codes.
We created a package FIB_PKG to hold both iterative and recursive versions.
Note that on Line No. 31 I have qualified the function calls with the package name as well.
Though this is not a mandatory one, it is a good practice.

If we want, we can create them as a stand-alone functions as well, instead of encapsulating in the package.

create     function fib_iteration(n number) return number
           is
               first   number := 0;
               second  number := 1;
               current number;
           begin
               for i in 3 .. n loop
                   current := first + second;
                   first   := second;
                   second  := current;
               end loop;
               return current;
           end fib_iteration;
/

Function created.

create     function fib_recursion(n number) return number
           is
           begin
               if n = 1 or n = 2 then
                    return n - 1;
               end if;
               return fib_recursion(n - 1) + fib_recursion(n - 2);
           end fib_recursion;
/

Function created.

OK. The above functions just return nth term.
What if want n terms?
Arrays in PL/SQL is not as simple as what we saw in JavaScript and/or Perl.
So, it is not posted now.
If possible, let us see it some other day later.

Fibonacci Sequence – Part 4


I used “Google Drive” (earlier “Google Docs”) for this post.
You can generate the Fibonacci sequence so easily with spreadsheets.
Here, A1 = 0; A2 = 1; A3 = A1 + A2;


Similarly, An = A(n-2) + A(n-1);
You can just drag the formulae at A3 to generate formula for other cells.
Its such an easiest thing.
And, do you see an array of temporary variables to hold the previous terms’ calculations? 😉

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.