On the Linear Time Algorithm For Finding Fibonacci Numbers(catonmat.net)
catonmat.net
On the Linear Time Algorithm For Finding Fibonacci Numbers
http://www.catonmat.net/blog/on-the-linear-time-algorithm-for-finding-fibonacci-numbers/
29 comments
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.
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.
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.
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.
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". :-)
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". :-)
I think you've misunderstood me. You don't evaluate the CF for Phi, you compute with it directly.
Gosper showed that it's possible to compute the CF of Phi^2 (say) directly, without evaluating the CF of Phi. Lather, rinse, repeat. The numbers involved are all similar in size to F(n) and so the complexity is linear. The number of multiplications and squarings is log(n), so I think the whole thing is sub-quadratic. Possibly it's n log(n) rather than linear.
The point is that there are fast ways of doing these sorts of things, but they tend to be little-known and subtle. I've not gone into the details, there may be something I've missed.
Gosper showed that it's possible to compute the CF of Phi^2 (say) directly, without evaluating the CF of Phi. Lather, rinse, repeat. The numbers involved are all similar in size to F(n) and so the complexity is linear. The number of multiplications and squarings is log(n), so I think the whole thing is sub-quadratic. Possibly it's n log(n) rather than linear.
The point is that there are fast ways of doing these sorts of things, but they tend to be little-known and subtle. I've not gone into the details, there may be something I've missed.
> 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
This seems true empirically, but when I do the math, it looks like you only need to calculate F_n up to about N/2 to make the ratio precise enough. (Since:
This seems true empirically, but when I do the math, it looks like you only need to calculate F_n up to about N/2 to make the ratio precise enough. (Since:
|phi - (F_(n+1)/F_n)| < (F_n)^(-2) = phi^(-2n)/sqrt(5) (approximately)
|(a+b)^n - a^n| = n a^(n-1) b (approximately)
This seems true empirically, but when I do the math, it looks like you only need to calculate F_n up to about N/2 to make the ratio precise enough.
True -- I oversimplified. But computing both F_n and F_{n+1} (as you need in order to compute the ratio) takes effectively the same amount of time as computing F_{2n}, so it still doesn't win you anything.
True -- I oversimplified. But computing both F_n and F_{n+1} (as you need in order to compute the ratio) takes effectively the same amount of time as computing F_{2n}, so it still doesn't win you anything.
> 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.
That might just work in a lazy language.
It works in non-lazy languages, too... it just happens to be a waste of cycles. :-)
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.)
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.)
> 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.)
So, that actually works by establishing a base value and a derivation step... i.e., it defines N(0), then it expresses N(n) in terms of N(n - 1).
If you try to do the same thing for Fibonacci numbers, you would need to express F(n) in terms of earlier values, not in terms of F(n). What cperciva is jokingly proposing is the equivalent of:
If you try to do the same thing for Fibonacci numbers, you would need to express F(n) in terms of earlier values, not in terms of F(n). What cperciva is jokingly proposing is the equivalent of:
naturals = naturals
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.
In that case you can keep the value of sqrt(5) as sqrt(5) knowing it will cancel out at some point.
That and the fact that computing the closed form expression still needs log(n) steps (as exponentiation).
Note: The closed form solution is given in the article.
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).
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).
(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 .
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 .
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.
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.
Ah, sorry I misread the contrasted "value vs. length". That does make sense.
[deleted]
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?
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.
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.
That's right!
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...
http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_e...
Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.
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.
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]
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).
Here's a link to the closed form solution: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_ex...