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:
1 2 3 4 5 6 7 8 9 10
|
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:
1 2 3 4 5 6 7 8 9 10 11
|
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.