There, that runtime is roughly O(n^2) when dealing with bignums, since addition scales linearly with bit length of the operands, and bit length increases linearly with the number of iterations (~0.7 bits per iteration).

Which is still not fast -- on my laptop, Python takes about 9s for fib(1000000). But compared to an exponentially-growing function, that's a blink of an eye.