Hacker News Reader

Comment by huggah | Hacker News Reader

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

Even the page the author links to is doing a great deal too much work!

View on HN

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

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

If you want to find an arbitrarily high F(n), you will need an arbitrarily high precision of sqrt(5).

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

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.

Reply on news.ycombinator.com