Why are you assuming exponentiation is constant time? For machine integers it near-enough is, but there are fewer than 100 Fibonacci numbers that fit in a 64-bit integer so you may as well use a lookup table. For arbitrary precision integers it definitely isn't.