5

This is one of the best algorithms to calculate the nth Fibonacci sequence. it needs O(log(n)) time to do its job, so it's so efficient. I found it somewhere but don't know how it works! Can anyone tell me how this algorithm works? thanks. Here's the code:

int fib3 (int n) {

    int i = 1, j = 0, k = 0, h = 1, t;
    while (n > 0) {
        if (n % 2) {
            t = j * h;
            j = i * h + j * k + t;
            i = i * k + t;
        }
        t = h * h;
        h = 2 * k * h + t;
        k = k * k + t;
        n /= 2;
    }
    return j;
}
  • Why is this O(n)? It looks O(logn) to me because of the n /= 2. – jliv902 Feb 7 '14 at 21:05
  • @jliv902 yeah you're right. Sorry, I knew that it's O(log(n)) but I don't know why I wrote O(n)! I'm sorry. I just edited it. thanks for mentioning that :) – Rasool Feb 7 '14 at 21:11
  • 2
    See en.wikipedia.org/wiki/Exponentiation_by_squaring, and nayuki.eigenstate.org/page/fast-fibonacci-algorithms under the Matrix exponentiation (medium) heading. – Robert Harvey Feb 7 '14 at 21:23
  • Thanks @RobertHarvey, I saw that link but I didn't understand. Could you please tell me what exactly it does? step-by-step. Thanks a lot :) – Rasool Feb 7 '14 at 21:31
  • Well, the code probably corresponds to the math. You don't understand the math? – Robert Harvey Feb 7 '14 at 21:32
3

It's called the "matrix form" - take a look at Wikipedia

You can compute next Fibonacci number (k+2) by multiplying matrix on a vector of two previous elements (k + 1 and k). Hence, k + 3 can be computed by multiplying matrix on vector of (k + 2 and k + 1). This equals squared matrix multiplied on (k + 1 and k). So on.

Your code simply squares the matrix, taking into account odd powers.

  • Why was this downvoted, I wonder? – neontapir Feb 7 '14 at 21:25
  • I gotta tell you that I didn't down vote you. Anyway, if I get the result form your link, I'll accept this answer. thank you buddy :) – Rasool Feb 7 '14 at 21:25
  • @neontapir: It was downvoted because it doesn't explain anything. Answers posted to Programmers are expected to answer the question in the answer itself, not in a link to some other website. See also meta.stackexchange.com/questions/8231/… – Robert Harvey Feb 7 '14 at 21:33
  • @RobertHarvey I see very little value in copy-pasting the answer contents from another public website. And I'm definitely not going to write complete answer from scratch - I doubt that there's any reason for anybody to do that in this question. – Eugene Feb 7 '14 at 21:36
  • That sounds like a good reason to cast a close vote on the question. If the question is unanswerable here, then there's no need to keep it around. – Robert Harvey Feb 7 '14 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.