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

Given arbitrary large inputs, simply reading in n takes O(log n), so in that sense no constant time algorithm is possible. So, use the closed form solution, or precompute the values you care about, to get reasonable performance.

Edit: In comments it was pointed out that it is actually worse, because fibonacci is O(phi^n) printing the result of Fibonacci is O(log (phi^n)) which is O(n)!