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}}
}