Fast nth Fibonacci number calculation

I am now preparing myself for Dynamic Programming quiz this Wednesday. One classic example of DP is the calculation of nth Fibonacci.

The straight-forward way is to convert the recurrence relation, Fn = Fn-1 + Fn-2, F0=0, F1=1, to a recursive function. However, the problem overlapping makes this solution poor in performance. A betterway is to calculate value of Fk from 2 to n in a bottom-up style. The asymptotic running time of this DP method is O(n).

   private static int FibN(int n)
   {
       if (n <= 1)
           return n;

       int a = 0, b = 1, c = 1;
       for(int i = 2 ; i <= n ; i++)
       {
           c = a + b;
           a = b;
           b = c;
       }

       return c;
   }

My instructor, Aj.Somchai, wrote in one of his book, "การออกแบบและวิเคราะห์อัลกอริทึม (Design & Analysis of Algorithms)", the challenge of finding a method that calculate Fn in less than O(n) time. After thinking for a while, I fired up my browser and search :)

This page described a method of calculating Fn in O(log n) time using a property of special case of matrix multiplication. The following is my implementation of this O(log n) method and O(n) method in C#.

using System;
using System.Collections.Generic;
using System.Text;

namespace FastFibo
{
   class Program
   {
       private static int[] G = new int[] { 1, 1, 1, 0 };

       /// <summary>
       /// Get [[1,1][1,0]]^n matrix.
       /// </summary>
       /// <param name="n">n</param>
       /// <returns>[[1,1][1,0]]^n</returns>
       private static int[] GetFiboMatrix(int n)
       {
           if (n == 1)
               return G;
           int[] c = GetFiboMatrix(n / 2);
           c = MatrixMul(c,c);
           if (n % 2 == 1)
               c = MatrixMul(c, G);
           return c;
       }

       private static int[] MatrixMul(int[] a, int[] b)
       {
           if (a.Length != 4 || b.Length != 4)
               throw new Exception("Invalid matrix size");

           int[] res = new int[4];
           res[0] = a[0] * b[0] + a[1] * b[2];
           res[1] = a[0] * b[1] + a[1] * b[3];
           res[2] = a[2] * b[0] + a[3] * b[2];
           res[3] = a[2] * b[1] + a[3] * b[3];
           return res;
       }

       private static int FibLogN(int n)
       {
           if (n <= 1)
               return n;

           return GetFiboMatrix(n)[1];
       }

       private static int FibN(int n)
       {
           if (n <= 1)
               return n;

           int a = 0, b = 1, c = 1;
           for(int i = 2 ; i <= n ; i++)
           {
               c = a + b;
               a = b;
               b = c;
           }

           return c;
       }


       static void Main(string[] args)
       {
           for (int i = 1; i <= 46; i++)
               Console.WriteLine("{0,4} FibN = {1,10} FibLogN = {2,10}",
                   i, FibN(i), FibLogN(i));
       }
   }
}

The normal 4-byte integer can only contain values in range [-2^31,2^31-1] and we can only get actual nth Fibonacci number up to n = 46. The difference of running time between O(n) and O(log n) for n under 47 can hardly be noticed.

This, however, can be apply to some Computer Olympiad problems such as "Find the last digit of nth Fibonacci number" :) You can also make this faster by convert it to non-recursion version.