4 ms·

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

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.

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.