Closed-Form Fibonacci through Linear Algebra

Fibonacci.m

% Octave code showing how to compute Fibonacci sequence numbers through  Linear
% Algebra concepts (*eigen*-stuff) applied in order to reach efficient O(lg(n))
% complexity (supposing exponentiation is O(lg(n))). This method also correctly
% calculates the "negafibonacci" sequence, that is, Fibonacci(n)` when n is negative.
% For big values of n, however, the floating-point operations yield +infinity.

function fn = Fibonacci(n)

	% golden ratio number and its conjugate are eigen-values
	phi = (1 + sqrt(5)) / 2;
	fi = (1 - sqrt(5)) / 2;

	% change of basis from B to C
	Mcb = [1  , 1 ;
	       phi, fi;];

	% change of basis from C to B
	aux = 1 / (fi - phi);
	Mbc = aux * [ fi , -1;
	             -phi,  1;];

  	% fibonacci seed (0,1) in canonical basis C = {(1,0);(0,1)}
	Sc = [0;
	      1;];

	% linear Transformation T(a,b) = (b,a+b) in eigen-basis B = {(1,phi);(1,fi)}
	Tb = [phi, 0 ;
	      0  , fi;];

	% final result vector [F(n);F(n-1)], in normal basis
	Fn = Mcb * (Tb^n) * Mbc * Sc;
	fn = round(Fn(1,1));

end