[vog]

I think the biggest issue in this code in the naive implementation of "powers". It runs in O(b) while it should take at most O(log(b)).

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.)

[ephemient]

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.