Can a Fibonacci function be written to execute in O(1) time?

Question

So, we see a lot of fibonacci questions. I, personally, hate them. A lot. More than a lot. I thought it'd be neat if maybe we could make it impossible for anyone to ever use it as an interview question again. Let's see how close to O(1) we can get fibonacci.

Here's my kick off, pretty much crib'd from Wikipedia, with of course plenty of headroom. Importantly, this solution will detonate for any particularly large fib, and it contains a relatively naive use of the power function, which places it at O(log(n)) at worst, if your libraries aren't good. I suspect we can get rid of the power function, or at least specialize it. Anyone up for helping? Is there a true O(1) solution, other than the finite* solution of using a look-up table?

http://ideone.com/FDt3P

#include <iostream> #include <math.h> using namespace std; // would never normally do this.  int main() { int target = 10; cin >> target; // should be close enough for anything that won't make us explode anyway. float mangle = 2.23607610;   float manglemore = mangle; ++manglemore; manglemore = manglemore / 2; manglemore = pow(manglemore, target); manglemore = manglemore/mangle; manglemore += .5; cout << floor(manglemore);  } 

*I know, I know, it's enough for any of the zero practical uses fibonacci has.

Answer 1

Here is a near O(1) solution for a Fibonacci sequence term. Admittedly, O(log n) depending on the system Math.pow() implementation, but it is Fibonacci w/o a visible loop, if your interviewer is looking for that. The ceil() was due to rounding precision on larger values returning .9 repeating.

Example in JS:

function fib (n) {   var A=(1+Math.sqrt(5))/2,       B=(1-Math.sqrt(5))/2,       fib = (Math.pow(A,n) - Math.pow(B,n)) / Math.sqrt(5);       return Math.ceil(fib); }