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:

Nice :)

Time limit exceeded!

Post a Comment