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));
            Console.ReadKey();
        }
        /// <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;
        }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s