Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by cperciva on Tuesday July 07, 2009 @08:25AM
(#691334)
The title is wrong -- it should be "On the Quadratic Time Algorithm...". The fastest algorithm of which I'm aware is O(n log n 2^log*(n)); and I'd be astonished if it were possible to compute the nth fibonacci number in o(n log n) time, although I can't offhand see any way to prove that it is impossible.
[ Parent
| on HN ]
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by vang3lis on Tuesday July 07, 2009 @08:32AM
(#691341)
The title mimicks the common misunderstanding that naive calculation for Fibonacci numbers is done in linear time, which is not true when cost of arithmetic operations is not negligible. The whole point of the article, as I understand it, was to show that not taking such details in account will lead to flawed analysis.
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by pkrumins on Tuesday July 07, 2009 @09:08AM
(#691383)
That's right!
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by dangoldin on Tuesday July 07, 2009 @10:18AM
(#691494)
There's a closed form solution to calculate the Nth Fibonacci number which can be derived from a recurrence relation.
http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_e...
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by cperciva on Tuesday July 07, 2009 @10:27AM
(#691508)
Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by dangoldin on Tuesday July 07, 2009 @10:54AM
(#691565)
Ah my mistake then. I didn't realize the closed form solution takes that long to evaluate.
Couldn't there be a faster way to evaluate it using an algebraic rather than a computational way? I just find the bound you give too high but I may be completely wrong.