How is exponentiation implemented in Python?

Question

I am able to compute any normally computable fibonnaci number (unless the result becomes to large) in a constant time using Binet's formula ie closed solution formula to compute fibonnaci numbers. Here is my code:

for the non-recursive implementation of fibonnaci:

gr = (1 + 5**0.5) / 2
def gfib(n):
    return int(((gr**n - (1-gr)**n) / 5**0.5))

I understand a^n indicates exponential run time complexity, however this is not the case when the code is run in python, as this computes the nth fibonnaci number instantly. I've done some research on how exponents are implemented in python (maybe exponentiation by squaring?) to give the constant time solution that I get, but haven't found a definitive answer. Any ideas?

Answer 1

The float.__pow__() method uses C's libm which takes full advantage of hardware support for binary floating point arithmetic. The latter represents numbers using logarithms. The logarithmic representation makes it possible to implement exponentation will just a single multiplication.

Executive summary: Float exponentation is implemented in hardware and runs at nearly constant speed due to the magic of logarithms.