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 multiplicatio

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