Saturday, July 14, 2007

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.

2 comments:

Chandra sekar said...

Nice :)

Anonymous said...

Time limit exceeded!