4 ms·
The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link
by cousin_it 9y ago
The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.
- engnr567 9y agoThe matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.
- cousin_it 9y agoThe article I linked has code examples in four languages, all use bigints, not longs.