Nevermind 1.618... What a silly number. All that was special about it was that its square was one plus itself. Well, so what? That's also true of f: f^2 = 1 + f

Nevermind 1.618... What a silly number. All that was special about it was that its square was one plus itself. Well, so what? That's also true of f: f^2 = 1 + f. And continuing in this way, we find that f^3 = f^2 * f = (1 + f) * f = f + f^2 = 1 + 2f. And f^4 = 2 + 3f, and f^5 = 3 + 5f, and so on, in the same way. Clearly, calculating Fibonacci numbers is as good as calculating the "coefficients" of powers of f. We don't need to bother exponentiating 1.618...; let's just exponentiate f. But how do we efficiently raise f to high powers? Well, the same way we efficiently raise anyone to high powers: by repeated squaring (or addition chains more generally). If you want to compute f^(2n), you can just compute f^n and square it [and to get f^(2n + 1), multiply that by f]. So we can compute f^n with on the order of log(n) multiplications [though, it should be noted, the actual quantities being multiplied will grow in size as we go on]. But what IS f if it's not 1.618...? Well, it's a Fibonaccex number: numbers of the form a + bf, which add and multiply in just the way you'd expect subject to the rule that f^2 = 1 + f. [So, in particular, (a + bf)^2 = a^2 + 2abf + b^2(1 + f) = (a^2 + b^2) + (2ab + b^2)f, which we can use for our repeated squaring]. Introducing the Fibonaccex numbers with f^2 = 1 + f is no different from introducing the complex numbers with i^2 = -1. And working with these directly gives us just as efficient a method for computing Fibonacci numbers as Binet's formula, without all the worries about floating-point precision. Indeed, as far as I'm aware, it gives us the most efficient method anyone knows (supposing you use efficient integer multiplication).