Question: Print Fibonacci series in order of log(n).

Solution: Here's a mathematical trick with matrices:

[ 1 1 ] n [ F(n+1) F(n) ]
[ 1 0 ] = [ F(n) F(n-1) ]

(You don't have to remember much linear algebra to understand this -- just the formula for multiplying two symmetric 2x2 matrices:

[ a b ] [ d e ] [ ad + be bd + ce ]
[ b c ] [ e f ] = [ bd + ce be + cf ]

You can then prove the result above by induction: Let

[ 1 1 ]
A = [ 1 0 ]

assume by induction that the equation above is is true for some n, multiply both sides by another power of A using the formula for matrix multiplication, and verify that the terms you get are the same as the formula defining the Fibonacci numbers.)

int M[2][2] = {{1,0}{0,1}}

int fib(int n)
{
matpow(n-1);
return M[0][0];
}

void matpow(int n)
{
if (n > 1) {
matpow(n/2);
M = M*M;
}
if (n is odd) M = M*{{1,1}{1,0}}
}