Thursday, October 27, 2011

No. 15 - Fibonacci Sequences


Problem: Please implement a function which returns the nth number in Fibonacci sequences with an input n. Fibonacci sequence is defined as:



Analysis: It is a classic interview questions to get numbers in Fibonacci sequences. We have different solutions for it, and their performance varies a lot.

Solution 1: Inefficient recursive solution

Fibonacci sequences are taken as examples to lecture recursive functions in many C/C++ textbooks, so most of candidates are familiar with the recursive solution. They feel confident and delighted when they meet this problem during interviews, because the can write the following code in short time:

long long Fibonacci(unsigned int n)
{
    if(n <= 0)
        return 0;

    if(n == 1)
        return 1;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Our textbooks take Fibonacci sequences as examples for recursive functions does not necessarily mean that recursion is a good solution for Fibonacci sequences. Interviewers may tell candidates that the performance of this recursive solution is quite bad, and ask them to analyze root causes.

Let us take f(10) as an example to analyze the recursive process. We have to get f(9) and f(8) before we get f(10). Meanwhile, f(8) and f(7) are needed before we get f(9). The dependency can be visualized in a tree as shown in Figure 1:

Figure 1: Recursive process to get the 10th number in Fibonacci sequences

It is not difficult to notice that there are many duplicate nodes in the tree in Figure 1. The number of duplicated nodes increases dramatically when n increases.  Readers may have a try on the 100th number if Fibonacci sequences to have intuitive ideas about how slow this recursive solution is.

Solution 2: Practical Solution with O(n) efficiency

It is easy to optimize performance fortunately if we calculate from bottom. That is to say, we get f(2) based on f(0) and f(1), and get f(3) based on f(1) and f(2). We follow this pattern till we get f(n). It is obvious that its time complexity is O(n). Its corresponding code is shown below:

long long Fibonacci(unsigned n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];

    long long  fibNMinusOne = 1;
    long long  fibNMinusTwo = 0;
    long long  fibN = 0;
    for(unsigned int i = 2; i <= n; ++ i)
    {
        fibN = fibNMinusOne + fibNMinusTwo;

        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }

     return fibN;
}

Solution 3: O(logn) solution

Usually interviewers expect the O(n) solution above. However, there is an O(logn) solution available, which is based on an uncommon equation as shown below:

It is not difficult to prove this equation vithmathematical induction. Interested readers may have try.

Now the only problem is how to calculate power of a matrix. We can calculate power with exponent n in O(logn) time with the following equation:






The source code to get power of a matrix looks complicated, which is listed below:

#include <cassert>

struct Matrix2By2
{
    Matrix2By2
    (
        long long m00 = 0,
        long long m01 = 0,
        long long m10 = 0,
        long long m11 = 0
    )
    :m_00(m00), m_01(m01), m_10(m10), m_11(m11)
    {
    }

    long long m_00;
    long long m_01;
    long long m_10;
    long long m_11;
};

Matrix2By2 MatrixMultiply
(
    const Matrix2By2& matrix1,
    const Matrix2By2& matrix2
)
{
    return Matrix2By2(
        matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
        matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
        matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
        matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}

Matrix2By2 MatrixPower(unsigned int n)
{
    assert(n > 0);

    Matrix2By2 matrix;
    if(n == 1)
    {
        matrix = Matrix2By2(1, 1, 1, 0);
    }
    else if(n % 2 == 0)
    {
        matrix = MatrixPower(n / 2);
        matrix = MatrixMultiply(matrix, matrix);
    }
    else if(n % 2 == 1)
    {
        matrix = MatrixPower((n - 1) / 2);
        matrix = MatrixMultiply(matrix, matrix);
        matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
    }

    return matrix;
}

long long Fibonacci(unsigned int n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];

    Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
    return PowerNMinus2.m_00;
}

Even though it cost only O(logn) time in theory, its hidden constant parameter is quite big, so it is not treated as a practical solution in real software development. Additionally, it is not a recommended solution during interviews since its implementation code is very complex.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog o webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.  

9 comments:

  1. Hey! Thanks for posting all of these cool problems. I wanted to suggest an ever faster solution. It's constant time if you solve out the closed form solution for the nth fibonacci number.

    http://math.stackexchange.com/questions/55922/fibonacci-recurrence-relations

    ReplyDelete
    Replies
    1. Thanks for your reply. The equation listed in the URL you provided is cool, but is not better than the solution in this post: (1) Precision issue. The equation is based on the value of sqrt(5). The calculation on double values is not as accurate as calculation on integer values. (2) The time efficiency is not constant. We can only calculate [(1 + sqrt(5)) / 2]^n and [(1 - sqrt(5)) / 2]^n in O(lgn) time.

      Delete
    2. Hi Harry

      Why to consider Precision Issue iff it is giving accurate answer ?

      Delete
  2. very nice explanation.One of the different fibonacci problem is mentioned in this link
    http://techno-terminal.blogspot.in/2015/09/fibonacci-problem-calculate-sum-fx-fx-1.html

    ReplyDelete
  3. Binet's formula solves this instantaneously.

    ReplyDelete
    Replies
    1. Accuracy is maintained, all the floating values cancel in the numerator and denominator

      Delete
    2. "The calculation on double values not as accurate..." Who would ever ask for the 2.2th fibonacci number? That is meaningless.

      Delete
    3. Accuracy is maintained, all the floating values cancel in the numerator and denominator

      Delete
  4. Binet's formula solves this instantaneously.

    ReplyDelete