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

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.

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

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

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

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

    fib :: Integer -> Integer
    fib 0 = 0
    fib 1 = 1
    fib 2 = 1
    fib n = case n `quotRem` 2 of
        -- if n = 2*m
        (m,0) -> (fib (m+1))^2 - (fib (m-1))^2

        -- if n = 2*m + 1
        (m,1) -> (fib (m+1))^2 + (fib (m  ))^2

Real answer: because I didn't realize that it's equivalent to O(n).

Define: Im5(a+b * sqrt(5)) =b

Fib(n)= Im5 ((1+1* sqrt(5))^n) / 2^(n-1)

The analytic solution really should win for very large terms though, but I'm not sure how to implement it properly. Can someone outline how you would decide what precision is needed to compute the Nth Fibonacci number?

Lets say that A` and B` are approximations of A and B, that are within E of the actual answer, that is to say |A`-A|<E and |B`-B|<E.

The total error can be found by:

|(A^n-B^n)/sqrt(5) - (A`^n-B`^n)/sqrt(5)|

If we can make this error be less than 1/2, we can simply round to the nearest integer and have the correct answer.

|(A^n-B^n)/sqrt(5) - (A`^n-B`^n)/sqrt(5)| < 1/2

|(A^n - A`^n + B`^n - B^n)| < sqrt(5)/2

Notice that: |(A^n - A`^n + B`^n - B^n)| <= |(A^n - A`^n| + |B`^n - B^n)|

If both of those absolute values are less than sqrt(5)/4, than their sum would be less than sqrt(5)/2, satisfying the inequality. Because 1<sqrt(5/4), I will make them be less than 1. Without loss of generality, I will consider only one of the absolute values.

|A`^n - A^n| < 1

Assuming the maximum error:

|(A+E)^n - A^n| < 1

Notice that the first term when you expand the binomial is A^n, so the n-1 remaining terms are our error. Every coefficient is less than 2^n. The greatest that A factor can be is A^(n-1)<A^n. And the greatest that the E factor can be is E^1. Therefore all (n-1) factors are less than (2^n)(A^n)E.

The sum of these error term is therefore less than (n-1)(2^n)(A^n)E. So:

(n-1)(2^n)(A^n)E < 1

Because A<2, A^n<2^n we can say: (n-1)2(2^n)E < 1

E < 1/(2(n-1)(2^n))

If our value for A is accurate for d+1 (binary) digits passed the decimal point, E<=2^(-d).

2^(-d) < 1/(2(n-1)(2^n))

2^d > 2(n-1)(2^n)

d>lg(2)+lg(n-1)+lg(2^n)

d>1+lg(n-1)+n

d>2n

I made a lot of simplifications in this analysis, so you can probably get away with fewer terms. It is interesting to note that Fibonacci numbers grow exponentially, so the number of digits needed simply to right the answer grows linearly, so the extra digits do not decrease the algorithmic efficiency.

[1]http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...