4 ms·
> If you want precise results for large sizes, then the integer-arithmetic recurrence is faster than computing the square root of 5 to very high precision and r
by valw 7y ago
> If you want precise results for large sizes, then the integer-arithmetic recurrence is faster than computing the square root of 5 to very high precision and raising it to the nth power.
Know what's even faster? Exponentiating a 2x2 matrix of integer coefficients. And again, that's what a bit of math tells you, so I think the point of the author holds.
- jacobolus 7y agoThose are two ways of saying the same thing. If you want to use a fancier algorithm, then fine.
- valw 7y agoThen I might have misunderstood what you meant by "integer-arithmetic recurrence"; my understanding of it was that it was the traditional recursive implementation of Fibonacci, which has much worse complexity than matrix exponentiation, and is not the same algorithm at all.
- jacobolus 7y agoThere are several ways we might try to optimize this calculation. Really depends on the context/constraints. Since the recurrence is always the same we can e.g. use the identities F_{m+n-1} = F_mF_n + F_{m-1}F_{n-1} and F_{m+n} = F_mF_n + F_mF_{n-1} + F_{m-1}F_n to precompute and cache all of the terms for 2^{n-1} and 2^{n}, and then multiply the appropriate ones together to find whatever value we need based on a binary expansion of the index we want to find a fibonacci number for. This is the same idea as fast matrix exponentiation but saves low-level arithmetic and half of the space, because two of the terms in the matrix are basically redundant.
- irchans 7y agoI am wondering if all three methods (sqrt(5) method, 2x2 matrix exponentiation, and jacobolus's power of two method) take approximately the same amount of time --- slightly less than O( log(F_n)*log(F_n)^2) (using Fürer's algorithm for integer multiplication.)