[stephencanon]

While I agree with the gist of your comment, it's important to note that none of these give an O(lg(n)) algorithm for computing fibonacci numbers (except on a hypothetical computer that can do arbitrary size integer operations in O(1) time).

The nth fibonacci number has O(n) digits, so you can't even write it out in time less than O(n). The repeated-squaring approach will involve multiplying numbers with O(n/2) = O(n) digits in its final step, so a very coarse analysis says the complexity is at least O(n lg n).

[blackhole]

This is completely missing the point of Big-Oh notation. If you start trying to analyze how long integer operations take, ALL your computational complexity analysis falls apart for any sufficiently large integer arithmetic for any algorithm. This is precisely why such operations are ignored, because it becomes completely impossible to do any meaningful platform-independent analysis if you try to take that into account.

That's not to say you shouldn't take it into account, but the algorithm he described is, in fact, O(log(n)) time. It just is. That's how the math works. Now, you should note that the O(log(n)) time constraint does not take into account arbitrary integer size which will cause progressively larger constant factors to influence the efficiency of the algorithm... but it is still a O(log(n)) algorithm.

[stephencanon]

My analysis holds for any implementation for which you can perform O(1) addition and multiplication of integers of some fixed-size. That's just about as platform-independent as you can get, but it still captures the real complexity of the operation in a way that handwavy "pretend you can do arbitrary arithmetic in O(1)" analyses do not.

This isn't simply my viewpoint on the subject; even the very theoretical textbook by Papadimitriou and Vazirani takes this approach to the question (see exercise 0.4 and note that everything is carried out in terms of the complexity of arbitrary-size integer multiplication M(n)).

[wging]

>progressively larger constant factors

If they are getting progressively larger with larger inputs, then they are not in fact constant factors.

[iansimon]

The algorithm is also relevant if you want to compute the nth Fibonacci number mod k.

[rcfox]

You're conflating the magnitudes. You can't directly compare the number of multiplications with the number of transistor switches or CPU cycles required for a single multiplication.

Also, the number n has O(log(n)) digits.

[stephencanon]

The number n has O(log(n)) digits, but that has nothing to do with the subject at hand. The nth fibonacci number has O(n) digits.

And nothing in my comment relates to "number of transistor switches or CPU cycles required for a single multiplication".