...
A naive program for computing fib (lifted directly from the definition) runs in exponential time, i.e. the running time for (fib n) is proportional to K*b**n for some constants K and b). It is easy to write a program that computes (fib n) in time proportional to n. Your challenge is to write a program that computes (fib n) in log time assuming that all multiplications and additions take constant time, which is unrealistic for large n. More precisely, your program should compute (fib n) using only O(log n) addition and multiplication operations (less than K * log n operations for some constant K).
Hints: assume n = 2**m. Derive a recurrence for fib 2**(m+1) in terms of fib 2**m and fib 2**(m-1). Initially write a program that works when n is a power of 2. Then refine it to a program that works for all n.
Note: in some definitions of fib, fib(0) = 0 which slightly changes the recurrence equations but does not affect asymptotic complexity.