3 ms·
Very nice! Had never seen this trick. One non-obvious aspect is that the function relies on using Python's big ints, even for pretty small values of n. You are
by toth 3y ago
Very nice! Had never seen this trick.
One non-obvious aspect is that the function relies on using Python's big ints, even for pretty small values of n. You are calculating `2^(n(n+1))` for the numerator, so if n=8 you already get `2^72`, which you can't fit in a 64-bit int. This is even though the answer itself is very small: `F_8=21`.
This makes sense, because you are essentially packing all the previous Fibonnaci numbers into a bit string, so you need room for all of them without overlapping and that bit-string is going to necessarily be long.
- cbolton 3y agoIndeed! I was trying in Julia and got [0, 1, 1, 2, 3, 5, 8, 0, 0, 0]. Had to use "big integers" to make it work past n=7: function f(n) b = big(2) << n return b^(n+1) ÷ (b^2-b-1) % b end or for code golf: f(n;b=big(2)<<n)=b^(n+1)÷(b^2-b-1)%b With "big" f.(1:10) gives the expected answer.
- andrewla 3y agoAnd since exponentation is logarithmic in the exponent, this algorithm is computing Fib(n) in O(log n) time. So while more compact than the matrix method or the field extension method or the doubling formula method, this reduces to the same complexity. I'd venture to say that it is clear that we can't really do better than O(log n) just because the number of digits in Fib(n) is O(log n).
- marschot 3y agoThe number of bits in Fib(n) is O(n), not O(log n). Put differently, Fib(n) grows exponentially. To be precise, Fib(n) = (phi^n - (-phi)^(-n)) / sqrt(5). So the complexity to compute Fib(n) is O(n) time (or slower). And one algorithm that runs this fast is to compute the n-th power of [[1,1],[1,0]] (using repeated squaring and large integer arithmetic).
- andrewla 3y agoI stand corrected. I made the same mistake that I am attributing to others; to think that n-bit arithmetic operations are O(1) instead of O(n).