4 ms·
Then I might have misunderstood what you meant by "integer-arithmetic recurrence"; my understanding of it was that it was the traditional recursive implementati
by valw 7y ago
Then 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.)