5 ms·

This is neat, and a solution that I hadn't seen before. But the author doesn't seem to be aware that finding the nth Fibonacci number is an O(1) problem: http:/

by huggah 14y ago

This is neat, and a solution that I hadn't seen before. But the author doesn't seem to be aware that finding the nth Fibonacci number is an O(1) problem: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex... Even the page the author links to is doing a great deal too much work!

deleted 14y ago
[deleted]
sp332 14y ago
That's probably faster, but it's not O(1). Calculating sqrt(5) to the needed precision, and raising phi to the n power, are not O(1).
- deleted 14y ago
  [deleted]
- ranit8 14y ago
  > Calculating sqrt(5) to the needed precision... I think this one could be optimized by precomputing and storing (1 + sqrt(5)) at the highest precision available.
  - sp332 14y ago
    If you want to find an arbitrarily high F(n), you will need an arbitrarily high precision of sqrt(5).
drostie 14y ago
(1) The whole point of that "O(1) algorithm" is that the n'th Fibonacci number has asymptotic size: F[n] ~= phi ** n / sqrt(5) But this means that it requires O(n) memory to store, which means that it is impossible to get an algorithm which scales better than O(n), asymptotically. You might be able to get better than O(n²); I don't know much about arbtitrary-precision exponentiation algorithms. (2) This is one of those nasty cases where CS folks are loose with the meaning of big-O, anyway. Strictly speaking the input size for the Turing machine scales like O(log n), and so the Fibonacci algorithms should probably be said to have exponential complexity, even though it's a linear recurrence relation. It depends how loose you are with what the 'n' means in O(n).
- huggah 14y ago
  My apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O. I still might be confused, but AFAICT, the OP's solution and computation by rounding both require O( (log n) * M(log n) ) time, where M(n) is the time it takes to multiply an n-bit number.

by huggah 14y ago

deleted 14y ago

[deleted]

sp332 14y ago

That's probably faster, but it's not O(1). Calculating sqrt(5) to the needed precision, and raising phi to the n power, are not O(1).

deleted 14y ago
[deleted]
ranit8 14y ago
> Calculating sqrt(5) to the needed precision... I think this one could be optimized by precomputing and storing (1 + sqrt(5)) at the highest precision available.
- sp332 14y ago
  If you want to find an arbitrarily high F(n), you will need an arbitrarily high precision of sqrt(5).

drostie 14y ago

(1) The whole point of that "O(1) algorithm" is that the n'th Fibonacci number has asymptotic size: F[n] ~= phi ** n / sqrt(5) But this means that it requires O(n) memory to store, which means that it is impossible to get an algorithm which scales better than O(n), asymptotically. You might be able to get better than O(n²); I don't know much about arbtitrary-precision exponentiation algorithms. (2) This is one of those nasty cases where CS folks are loose with the meaning of big-O, anyway. Strictly speaking the input size for the Turing machine scales like O(log n), and so the Fibonacci algorithms should probably be said to have exponential complexity, even though it's a linear recurrence relation. It depends how loose you are with what the 'n' means in O(n).

huggah 14y ago
My apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O. I still might be confused, but AFAICT, the OP's solution and computation by rounding both require O( (log n) * M(log n) ) time, where M(n) is the time it takes to multiply an n-bit number.