[Gondolin]

The Fibonacci example is interesting. If you want arbitrary precision, then the naive recursive method is exponential in $n$ to compute $F_n$. The loop method (recursive method with cache) is in $O(n^2)$. Indeed you only have $n$ steps in the loop, but at step $k$ you add $F_k$ and $F_{k+1}$ which have $O(k)$ bits so the total costs is $O(n^2)$. Finally the matrix/formal \sqrt{5} algorithm costs $O(n log n)$.

Indeed, using fast exponentiations, you only need $O(log n) matrix multiplications. But the dominant cost is actually at the last step, where you multiply two numbers of size $O(n)$ bits for a total cost of $O(n log n)$.

Speaking of mathematics in programming: I find it remarkable that the recent convergence of async programming into the use of promises and async/await (in python, js, rust...) is a weak form of the continuation monad. And the continuation monad is a form of the 'not not' Lawrere topology!