Calculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the rat

Calculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the ratios between the Fibonacci numbers. At that point, it's totally redundant to use Binet's formula on the approximation, since you have the values already! If you want to beat the O(n^2) runtime of the trivial iteration, you pretty much have to use Newton's method for φ, exponentiation by squaring on the matrix form, or another method with faster-than-linear convergence.