5 ms·

I always thought the fastest was the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibo

by MrRage 12y ago

I always thought the fastest was the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex... Unless looping and counting is that much faster than doing some floating point math?

aarongolliver 12y ago
Only "faster" because you precompute digits of the golden ratio, and will quickly become inaccurate unless you compute more of them
Bognar 12y ago
The closed form will become inaccurate at some point. However, there is a way to calculate Fibonacci accurately with O(log(n)) time (ignoring the time to multiply - otherwise O(M(n) log(n)) where M(n) is the time to multiply two numbers of n digits).