News for hackers. Stuff that matters.
Re:A program to compute the nth Fibonacci number by huggah on Saturday April 28, 2012 @02:59PM (#3903725)
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!

Re:A program to compute the nth Fibonacci number by sp332 on Saturday April 28, 2012 @03:30PM (#3903826)
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).
Re:A program to compute the nth Fibonacci number by ranit8 on Saturday April 28, 2012 @04:29PM (#3903997)
> 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.

Re:A program to compute the nth Fibonacci number by sp332 on Sunday April 29, 2012 @07:41AM (#3905749)
If you want to find an arbitrarily high F(n), you will need an arbitrarily high precision of sqrt(5).
Re:A program to compute the nth Fibonacci number by drostie on Saturday April 28, 2012 @04:47PM (#3904058)
(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).

Re:A program to compute the nth Fibonacci number by huggah on Saturday April 28, 2012 @05:57PM (#3904245)
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.