3 ms·
There is a log time way to do this, use Binet's formula (https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.m.wikipedia.org/wiki
by adilparvez 10y ago
There is a log time way to do this, use Binet's formula (https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form...), but do the arithmetic in the field Q[√5].
Edit: Someone's implementation: http://ideone.com/NWQe38 http://ideone.com/NWQe38
Edit: constant time -> log time
- yaks_hairbrush 10y agoThat's log(n) time due to the exponentiation.
- adilparvez 10y agoOops, yes log(n), I'll correct the comment, thanks.
- stephencanon 10y agoIt's log(n) multiplications, each of which requires something like O(n log n log log n) time [1]; so the actual complexity is O(n (log n)^2 log log n) ish. [1] Schönhage-Strassen multiplication, one of many bignum multiplication algorithms with sub-quadratic complexity. Other algorithms in common use have worse asymptotic performance.
- yaks_hairbrush 10y agoDon't know why you were downvoted, you're absolutely correct. At first glance your n and my n are different, with mine (n1) being the input to the function and yours representing the number of digits in a multiplicand (n2). n1 and n2 are linearly related, though, since the exponentiation process increases the number of digits in a linear fashion. It's also worth noting that since the Fibonacci sequence grows exponentially, the number of digits is the result will be linear in n. Therefore, the memory requirement is actually O(n), and writing the result to the screen will be O(n).
- stephencanon 10y ago> At first glance your n and my n are different Right; as you sketch out, there's some constants that disappear into the O() notation.