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.  

19 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
  5. Solution one is not only inefficient it is also incorrect.

    ReplyDelete
  6. The The fibonacci-calculator is a tool that traders use to help identify strategic places for transactions, stop losses or target prices to help them get in at a good price. is a tool that traders use to help identify strategic places for transactions, stop losses or target prices to help them get in at a good price.

    ReplyDelete
  7. Hello There,


    So bloody thorough! Ah! So happy and blessed out! I feel redeemed by reading out Infinite
    CoderCareer: Discussing Coding Interview Questions Keep up the good work!

    I am a C beginner and I tried to write a program to convert numbers from decimal base to octal. The program is not working for higher numbers and for those between 192 and 2890(both included). For the numbers in that range, it displays octal value one less than the correct one and for higher numbers, it displays octal value one greater.

    Awesome! Thanks for putting this all in one place. Very useful!


    Grazie,
    Renina

    ReplyDelete
  8. 4. Howdy Mate,


    #Topic being contrived to exist for many projects simply so it can be run will be the first to hit the wall, but those projects where the functions to make existing transactions cheaper in real world applications will find the elusive real world demand.

    I recently attended the AWS Summit London 2018. During the afternoon session about "Open Source at AWS" there were some resources mentioned for persuading your company that open source can be a great benefit to them.
    Unfortunately this wasn't one of the slide sets which has been made available after the event.




    Follow my new blog if you interested in just tag along me in any social media platforms!


    Cheers,

    ReplyDelete
  9. Hello Buddie,


    Thanks for highlighting this and indicating about No. 15 - Fibonacci Sequences where more study and thought is necessary.

    I would like to post an announcement for anyone who needs server resources at AWS. Basically, I have 600$ worth of AWS Credit and I am looking for people who would like to use these credits since I don't need them. The only issue here is that they expire at April 30th. I am ready to negotiate and maybe exchange for 150$ amazon gift card or something more tangible for me. Also, I am open to any kind of negotiation. AWS Training USA






    Awesome! Thanks for putting this all in one place. Very useful!


    Obrigado,
    Ajeeth

    ReplyDelete
  10. Howdy Mate,


    This is indeed great! But I think perhaps you are generally referring No. 15 - Fibonacci Sequences which is getting unsustainable.


    I have a problem with cost allocation tags. I added a number of custom tags to my AWS resources. Activated the tags using activation GUI. I can see the tag keys as dimensions for Cost Explorer filters but no tag values are shown for filtering (only record "No TagKey"). More than a week passed since I added and activated the tags but nothing changes. Please advise. AWS Tutorial





    Once again thanks for your tutorial.


    Merci Beaucoup,
    Ajeeth

    ReplyDelete
  11. SainBainuu,

    Thanks for highlighting this and indicating about No. 15 - Fibonacci Sequences where more study and thought is necessary. AWS Training USA

    If I buy a Route 53 domain name, can I create an email address and use it with gmail? If so, how?
    I do not want to use Workmail, or SES or an EC2 instance.
    All I want is a username, password, and SMTP and whatever else is needed to link my route 53 email to gmail.

    Very useful article, if I run into challenges along the way, I will share them here.

    Cheers,
    Radhey

    ReplyDelete
  12. Thank you for sharing with us! Good luck!
    vivi winkler

    ReplyDelete