The only logarithmic algorithm here is fib_closed_form because floating-point multiplication is a fixed-cost operation (and yields a progressively imprecise res

The only logarithmic algorithm here is fib_closed_form because floating-point multiplication is a fixed-cost operation (and yields a progressively imprecise result, as other commenters have pointed out). The other approaches use arbitrary precision integers, as you've noted, so additions and multiplications are not actually fixed-cost, but scale with the number of digits you're operating on (addition scales linearly; multiplication in Python uses Karatsuba for sufficiently large N, so it scales like n^1.58). In fact, you can't get a sublinear result with a lossless approach, since the number of digits in Fib(n) scales linearly with n, and so you need O(n) operations to just write out the digits. This is pretty straightforward to explain with the closed-form solution: Fib(n) is roughly 1.618^n / 2.236; by taking the binary logarithm, you can see this requires about 0.7n bits to represent. (Equivalently, 0.2n decimal digits.)