7 ms·

On the Linear Time Algorithm For Finding Fibonacci Numbers

41 points by pkrumins 17y ago

dantheman 17y 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_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_ex...
- cruise02 17y 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.
  - vang3lis 17y ago
    That and the fact that computing the closed form expression still needs log(n) steps (as exponentiation).
  - RiderOfGiraffes 17y ago
    You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ 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 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.
    - cperciva 17y ago
      You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ 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. I'm trying to figure out if you're intentionally making a sophisticated math joke or not -- and failing. Are you? The precision to which you need to compute phi in order to compute the Nth Fibonacci number by exponentiation is the precision you'd obtain by computing the ratio of the Nth and (N-1)th Fibonacci numbers -- which is exactly how you evaluate the continued fraction for phi. So your suggestion amounts to "compute the Nth Fibonacci number... then do a lot of work to use that value to compute the Nth Fibonacci number". :-)
      - eru 17y ago
        > So your suggestion amounts to "compute the Nth Fibonacci number... then do a lot of work to use that value to compute the Nth Fibonacci number". :-) That might just work in a lazy language.
        cperciva 17y ago
        It works in non-lazy languages, too... it just happens to be a waste of cycles. :-)
        jcl 17y ago
        How? Giving f(N) in terms of f(N) hardly seems useful, in any language. (It's hard to tell if you're joking without a smiley.)
        eru 17y ago
        I am too dumb / lazy to think of an example for the fibonaccy numbers at the top of my head. But suppose your problem was giving a list of natural numbers, then giving a circular definition like > naturals = 0 : (map (+1) naturals) actually works in Haskell. (In Haskell a:b means the same as (cons a b) in Lisp. I also added parens to make the definition more readable for non-Haskellers.)
  - dangoldin 17y 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.
- jcl 17y ago
  Note: The closed form solution is given in the article.
cperciva 17y 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.
- vang3lis 17y 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.
  - pkrumins 17y ago
    That's right!
- dangoldin 17y 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_expression http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_e...
  - cperciva 17y ago
    Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.
    - dangoldin 17y ago
      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.
- deleted 17y ago
mikhael 17y 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 17y 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).
- sp332 17y 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 .
  - mikhael 17y 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.
    - sp332 17y ago
      Ah, sorry I misread the contrasted "value vs. length". That does make sense.
  - deleted 17y ago
    [deleted]
- pkrumins 17y 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?

41 points by pkrumins 17y 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_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_ex...

cruise02 17y 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.
- vang3lis 17y ago
  That and the fact that computing the closed form expression still needs log(n) steps (as exponentiation).
- RiderOfGiraffes 17y ago
  You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ 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 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.
  - cperciva 17y ago
    You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ 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. I'm trying to figure out if you're intentionally making a sophisticated math joke or not -- and failing. Are you? The precision to which you need to compute phi in order to compute the Nth Fibonacci number by exponentiation is the precision you'd obtain by computing the ratio of the Nth and (N-1)th Fibonacci numbers -- which is exactly how you evaluate the continued fraction for phi. So your suggestion amounts to "compute the Nth Fibonacci number... then do a lot of work to use that value to compute the Nth Fibonacci number". :-)
    - eru 17y ago
      > So your suggestion amounts to "compute the Nth Fibonacci number... then do a lot of work to use that value to compute the Nth Fibonacci number". :-) That might just work in a lazy language.
      - cperciva 17y ago
        It works in non-lazy languages, too... it just happens to be a waste of cycles. :-)
      - jcl 17y ago
        How? Giving f(N) in terms of f(N) hardly seems useful, in any language. (It's hard to tell if you're joking without a smiley.)
        eru 17y ago
        I am too dumb / lazy to think of an example for the fibonaccy numbers at the top of my head. But suppose your problem was giving a list of natural numbers, then giving a circular definition like > naturals = 0 : (map (+1) naturals) actually works in Haskell. (In Haskell a:b means the same as (cons a b) in Lisp. I also added parens to make the definition more readable for non-Haskellers.)
- dangoldin 17y 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.
jcl 17y ago
Note: The closed form solution is given in the article.

cperciva 17y 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.

vang3lis 17y 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.
- pkrumins 17y ago
  That's right!
dangoldin 17y 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_expression http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_e...
- cperciva 17y ago
  Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.
  - dangoldin 17y ago
    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.
deleted 17y ago

mikhael 17y 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 17y 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).

sp332 17y 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 .
- mikhael 17y 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.
  - sp332 17y ago
    Ah, sorry I misread the contrasted "value vs. length". That does make sense.
- deleted 17y ago
  [deleted]
pkrumins 17y 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?