3 ms·
Closed-form expression [0], good up to n == 71: def fibonacci(n): gr = (1 + (5**0.5)) / 2 return int((gr**int(n) - (-gr)**int(-n)) / 5**0.5
by robomartin 13y ago
Closed-form expression [0], good up to n == 71:
def fibonacci(n):
gr = (1 + (5**0.5)) / 2
return int((gr**int(n) - (-gr)**int(-n)) / 5**0.5)
[0] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
- LinaLauneBaer 13y agoI wanted to mention this as well. There is actually a closed form (as you indicated). Also good to know: This is or was a interview question at Google. You had to know Moivre-Binet's closed formula from the top of your head to pass.
- speeder 13y agoI don't even know what is Moivre-Binet what the fuck.
- robomartin 13y ago> You had to know Moivre-Binet's closed formula from the top of your head to pass. What's unfortunate about what you just said is that this is utterly irrelevant as a test of coding or problem solving ability. See my other comment about MIT 6.00.1x