robomartin on Common Species Of Code

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_ex...

LinaLauneBaer 12y

I 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 12y

I don't even know what is Moivre-Binet what the fuck.

robomartin 12y

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

Comments