[edflsafoiewq]

You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out.

Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?

[toolslive]

true: adding 2 64 bit numbers is constant time for me, but adding 2 4096 bit numbers is not. Eventually, even the simplest operation becomes O(ln n)