n-th Fibonacci number in O(logn)

[rajenipcv]

This is recursive function to compute nth Fibonacci number and is of O(n) time:

int Fibonacci(int n)
{
   if (n == 0 || n == 1)
       return n;
   else
       return Fibonacci(n - 1) + Fibonacci(n - 2);
}

How can we compute nth Fibonacci number in O(logn) time?

[helios]

That function takes O(n^2) for n>1.

http://www.google.com.ar/search?q=fibonacci+in+logarithmic+time

[tition]

Actually helios, as he wrote it, it takes
[Edit: previous expression was incorrect]
O((1/2(1+sqrt(5)))^n)
The reason is simple: the function Fibonacci(1) will execute as many times as is the size of the Fibonacci number. Now, the n-th Fibonacci number is asymptotically
(1/2 (1+sqrt(5)))^n = approx 1.6^n

[tition]

What you are perhaps expected to do is to express Fibonacci numbers with matrices. This can be done with a two by two matrix in the following way. Let F be the matrix

1 1
1 0

Then F^n (2x2 matrix multiplication) equals

F(n+1) F(n)
F(n)   F(n-1)

,
because:

(F(n+1) F(n)  ) (1 1) = ( F(n+1)+F(n)   F(n+1))
(F(n)   F(n-1)) (1 0) = ( F(n)+F(n-1)   F(n)  )

Now to complete your assignment, you must raise the two by two matrix F to the n-th power in time O(log(n)). That is of course a cheating on your instructor's side, since the size of the Fibonacci numbers will quickly exceed the size of int64, and you will have to use mathematical operations that do not take constant processor time.

To raise a 2x2 matrix to the 2^k-th power, you can proceed quickly by computing F^{2^k}= (F^{2^{k-1}})^2.

[helios]

Arg. I often confuse the exponential and polynomial functions. I visualize one function and write down another.
Yeah, I meant to say O(k^n) (the value of k isn't really relevant).

[jsmith]

Is not the simplest solution simply to store all intermediary results in a lookup table?

[tition]

Umm, that actually can be implemented together with *any* of the described algorithms (even that worst one with the recursion). To me, the simplest solution is:

int Fibonacci(int n)
{ int result=0;
  int oldResult=1; 
  for (int i=0;i<n;i++)
  { int temp= result; 
    result+=result+oldResult;
    oldResult= temp;
  }
  return result;
}

Of course, this is of complexity O(n) (assuming addition is of constant complexity). That of course is not true for large enough integers. This algorithm is also very easy to realize with large numbers. For example, if I used my math library to write the above:

void Fibonacci(int n, LargeInt& output)
{ LargeInt oldOutput, temp;
  output.MakeZero();
  oldOutput.MakeOne();
  for (int i=0;i<n;i++)
  { temp.Assign(output); 
    output.Add(output);
    output.Add(oldOutput);
    oldOutput.Assign(temp);    
  }
}

The "advantage" of the matrix multiplication algorithm is that "theoretically" it is O(log n), since you gain operations when raising matrices to powers, since computing F^{2^k} requires only k multiplications.

However, this is not at all the core of the problem, since a multiplication operation is slower than an addition operation (the matrix approach = save on addition operations by using multiplication operations).

Now, if you try to compute, say, the 10 thousandth Fibonacci number (which should be no problem, say, with the second piece of code, although I do not use any fancy addition algorithms), I am sure you will not get it much better with some elaborate-if-we-assume-multiplication-takes-constant-time algorithm.

[jsmith]

I agree that a lookup table can be used with any solution.

I just suggested it because it could be incorporated into the recursive solution
in about 3 lines of code whereas the matrix solution was overly complex and
slower (though I agree that your non-recursive implementation would
be even faster and definitely more scalable than the recursive one).