4 ms·
It would be interesting to see what the asymtotic complexity would be in terms of number of (fixed-size) operations as opposed to number of bigint operations re
by TheLoneWolfling 12y ago
It would be interesting to see what the asymtotic complexity would be in terms of number of (fixed-size) operations as opposed to number of bigint operations required.
I mean, the nth Fibonacci number requires O(n) bits to store.
- fdej 12y agoIt's O(M(n)) where M(n) is the complexity of the algorithm used for multiplying n-bit integers. To see why, note that each step of the matrix powering or fast doubling algorithm 1) costs a constant C number of multiplications, and 2) roughly doubles the number of bits. F(n) has b = O(n) bits, so the cost is essentially C M(b) + C M(b/2) + C M(b/4) + ... <= 2 C M(b) = O(M(n)), using the natural assumption that M(2x) >= 2M(x).
- TheLoneWolfling 12y agoSo then: is there any better solution? Or is that the optimal?
- fdej 12y agoIt's almost certainly optimal, but proving that is likely an open problem.