I have not profiled the code, but I expect that the Newtonian approximation of sqrt is the slowest part.
It would surprise me if "powers" was a big problem relative to the rest. And no shortcuts: each of [1, b b², b³, b⁴, b⁵, …] (up to n) is used in the binomial expansion.
Also, the multiplication might be a bottleneck, there has been a lot of research in this area. (the original article mentions some)
It might be a good idea to use an arbitrary precision library like GMP, which provides super-fast multiplication and thus power() algorithms.
(It also has an implementation of Fib() which outperforms both approaches here, but that's not my point.)