With a dumb bignum library addition will be O(d) and multiplication will be O(d^2), d being the number of digits; d increases linearly with index, so to compute

With a dumb bignum library addition will be O(d) and multiplication will be O(d^2), d being the number of digits; d increases linearly with index, so to compute the n'th Fibonacci number by naive iteration will be O(d^2), whereas doing it by repeated squaring will involve (ignoring lots of constant factors) one size-n multiply, one size-n/2 multiply, one size-n/4 multiply, etc., so also O(d^2). So, same order of magnitude, but it seems quite possible that the constant factor will be worse. And yes, the naive recursive approach is a total disaster. Pretty code, though, and if you have language or library support for memoization you can just write the naive recursive function and demand that it be memoized.