# Calculating Fibonacci Numbers

/// <summary>
/// O(Log2N) time algorithm for calculation of N Fibonacci’s number
/// F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = 1.
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
Console.WriteLine(GetN(10));
}
/// <summary>
/// A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is
/// |Fk+2|   |1 1|  |Fk+1|
/// |       | = |    |x|       |
/// |Fk+1|   |1 0|  |Fk    |
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
private static int GetN(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
number -= 2;
int[,] result = new int[2, 2] { { 1, 1 }, { 1, 0 } };
int[,] even = new int[2, 2] { { 1, 1 }, { 1, 0 } };
while (number != 0)
{
if ((number % 2) == 0)
{
even = Multiply(even, even);
number /= 2;
}
else
{
result = Multiply(result, even);
number–;
}
}
return result[0, 0];
}

/// <summary>
///           n
/// Ci,j =  Σ Ai,r * Br,j = Ai,1 * B1,j + Ai,2 * B2,j + … + Ai,n * Bn,j;
///          r=1
/// </summary>
/// <param name="first"></param>
/// <param name="second"></param>
/// <returns></returns>
private static int[,] Multiply(int[,] first, int[,] second)
{
int[,] result = new int[2, 2];
result[0, 0] = first[0, 0] * second[0, 0] + first[0, 1] * second[1, 0];
result[0, 1] = first[0, 0] * second[0, 1] + first[0, 1] * second[1, 1];
result[1, 0] = first[1, 0] * second[0, 0] + first[1, 1] * second[1, 0];
result[1, 1] = first[1, 0] * second[0, 1] + first[1, 1] * second[1, 1];
return result;
}