On the Linear Time Algorithm For Finding Fibonacci Numbers

http://www.catonmat.net/blog/on-the-linear-time-algorithm-for-finding-fibonacci-numbers/

by pkrumins • 17 years ago

41 27 17 years ago

dantheman• 17 years ago

I love Fibonacci as pedagogical exercise, but there is a closed form solution that can find the nth term without the need to calculate all the preceding values (no need for recursion). In computer science we are often obsessed with finding good algorithms for calculating, but are not so good at finding ways to completely jump past the calculation, of course this is very hard, but I don't think it is emphasized enough in the undergraduate computer science curriculum.

Here's a link to the closed form solution: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_ex...

cruise02• 17 years ago

The closed form still depends on the precision of the decimal expansion of the irrational constant phi, the golden ratio. You can't use it to find any arbitrary F(n) without a precise expansion of phi.

vang3lis2• 17 years ago

That and the fact that computing the closed form expression still needs log(n) steps (as exponentiation).

RiderOfGiraffes2• 17 years ago

You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ ) to generate precision as needed. The CF for phi is [1; 1, 1, 1, 1, ...] and basically all you need to do is take the n^th power. You can use that using the log(n) method (http://www.brpreiss.com/books/opus5/html/page54.html (that reference took a surprisingly long time to find - there must be a better one))

I'd be surprised if there isn't a true linear time algorithm for Fibonacci, it's just that it's more subtle than people think.

PS: Finding an optimal sequence of multiples and squares for computing an arbitrary power is still an open question.

dangoldin3• 17 years ago

I think it would be pretty straightforward to implement this in an algebraic way without needing to resort to fractional values since you know beforehand that the solution is an integer.

In that case you can keep the value of sqrt(5) as sqrt(5) knowing it will cancel out at some point.

jcl3• 17 years ago

Note: The closed form solution is given in the article.

cperciva5• 17 years ago

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.

vang3lis2• 17 years ago

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.

pkrumins2• 17 years ago

That's right!

dangoldin3• 17 years ago

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

cperciva5• 17 years ago

Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.

mikhael2• 17 years ago

most people would consider the so-called "linear" algorithm exponential, as the size of the input for the number n is m = Theta(log(n)) bits; the running time is Theta(2^m). the "quadratic" running time is Theta(4^m).

dmg_83• 17 years ago

In complexity theory, n is based on the length of the binary encoding of the input, NOT the decimal value as was used here. Therefore, the x-axis should be based on n = log2(k), for each number k.

Overlooking this would lead one to believe there are known algorithms that solve NP-C problems in polynomial time (e.g., knapsack problem can be solved in polynomial time with respect to the decimal values of its inputs, but exponential with respect to the length of the binary encoding).

sp3322• 17 years ago

(e.g., knapsack problem can be solved in polynomial time with respect to the decimal values of its inputs, but exponential with respect to the length of the binary encoding).

That doesn't make any sense. The number of binary and decimal digits has a linear relation. I think the ratio is log(10) / log(2) or about 3.32 .

mikhael2• 17 years ago

it does make sense; there are two issues here. one is that the author overlooked (or ignored) the fact that "input size" means number of bits. the number N uses ~log2(N) = M bits, so that is the input size, not N, and O(N) is O(2^M).

the other is that addition of two D-digits numbers takes O(D) time (this is what the author means to expose in the article). as you have pointed out, the base (10, or 2, or anything else) does not matter for asymptotic analysis here, because the logarithm functions are all linearly related.

pkrumins2• 17 years ago

Yes, but you can also measure it by input value, like I did. It makes more sense to me to plot n vs. time(Fib(n)), because practically I'd want to know how "how fast" my algo runs if i give it n. What do you think about that?

On the Linear Time Algorithm For Finding Fibonacci Numbers

Related Stories