How is exponentiation implemented in Python?
<p>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:</p>

<p>for the non-recursive implementation of fibonnaci:</p>

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

<p>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?</p>
