Moore's Law and Algorithms  Case of Fibonacci Numbers
The world of computers is moving fast. While going through some materials on algorithms, I have come across an interesting discussion enhancements in hardware (cpu) visavis algorithms.
One side of the coin is the hardware  the speed of computers. The famous Moore’s law states that:
The complexity for minimum component costs has increased at a rate of roughly a factor of two per year. Certainly over the short term this rate can be expected to continue, if not to increase. Over the longer term, the rate of increase is a bit more uncertain, although there is no reason to believe it will not remain nearly constant for at least 10 years.
In simple words, Moore’s law is the observation that, over the history of computing hardware, the number of transistors in a dense integrated circuit has doubled approximately every two years. More precisely, the number of transistors in a dense integrated circuit has increased by a factor of 1.6 every two years. More recently, keeping up with this has been challenging. In the context of this discussion, the inherent assumption is that number of transistors is directly proportional to the speed of computers.
Now, looking at the other side of the coin  speed of algorithms. According to Excerpt from Report to the President and Congress: Designing a Digital Future, December 2010 (page 97):
Everyone knows Moore’s Law – a prediction made in 1965 by Intel cofounder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years…. in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.
The gain in computing speed due to algorithms have been simply phenomenal, unprecedented, to say the least! Being actively involved with realization of Moore’s law, I have been naturally attracted in the study and design of algorithms.
To get a more practical perspective on this, lets look at the problem of finding large Fibonacci numbers. These numbers have been used in wide areas ranging from arts to economics to biology to computer science to the game of poker! The simple definition of these numbers are:
$$ F_{n} = \begin{cases} F_{n2} + F_{n1} & \text{if } n > 1 \cr 1 & \text{if } n = 1 \cr 0 & \text{if } n = 0 \end{cases} $$
So, first few Fibonacci numbers are: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 \ldots $ These numbers grow almost as fast as powers of 2: for example, $F_{30}$ is over a million, and $F_{100}$ is 21 digits long! In general, $F_n \approx 2^{0.694n}$ Clearly, we need a computing device to calculate say $F_{200}$.
Here is a simple plot of first few Fibonacci numbers:
The most basic algorithm, that comes to mind is a recursive scheme that taps directly into the above definition of Fibonacci series.


If you analyze this scheme, this is in fact an exponential algorithm, i.e. fibRecursive( n ) is proportional to $2^{0.694n} \approx (1.6)^n$, so it takes 1.6 times longer to compute $F_{n+1}$ than $F_n$. This is interesting. Recall, under Moore’s law, computers get roughly 1.6 times faster every 2 years. So if we can reasonably compute $F_{100}$ with this year’s technology, then only after 2 years we will manage to get $F_{101}$! Only one more Fibonacci number every 2 years!
Luckily, algorithms have grown at a much faster pace. Let’s consider improvements w.r.t to this current problem of finding $n^{th}$ Fibonacci number, $F_n$.
First problem we should realize in the above recursive scheme is that we are recalculating lower $F_n$ at each recursion level. Lets solve this issue by storing each calculation and avoiding any recalculation!


On first glance this looks like an $\mathcal{O}(n)$ scheme, as we consider each addition as one operation. However, we should realize that as $n$ increases, addition can not be assumed as a single operation, rather every step of addition is an $\mathcal{O}(n)$ operation, recall first grade Math for adding numbers digit by digit!! Hence, this algorithm is an $\mathcal{O}(n^2)$ scheme. Can we do better?
You bet, we can! Lets consider the following scheme:
$$ \begin{pmatrix} 1&1 \cr 1&0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1}&F_n \cr F_n&F_{n1} \end{pmatrix} $$
We can use a recursive scheme to calculate this matrix power using a divide and conquer scheme in $\mathcal{O}(\log{}n)$ time.


Lets think a bit harder about this. Is it really an $\mathcal{O}(\log{}n)$ scheme? It involves multiplication of numbers, the method mul(A, B). What happens when $n$ is very large? Sure, this will blow up, as typical multiplication would be an $\mathcal{O}(n^2)$ operation. So, in fact, our new scheme is $\mathcal{O}(n^2 \log{}n)$!
Luckily, we can solve even large multiplications in $\mathcal{O}(n^{log_2{3}} \approx n^{1.585})$, using Karatsuba multiplication, which is again a divide and conquer scheme.
Here is one simple implementation (Same as the above scheme, but with the following mul(A,B) method):


So, this final scheme is in $\mathcal{O}(n^{1.585}\log{}n)$ time.
Here is one final way of solving this problem in the same $\mathcal{O}(n^{1.585}\log{}n)$ time, but using a somewhat simpler scheme!
If we know $F_K$ and $F_{K+1}$, then we can find,
$$ F_{2K} = F_K \left [ 2F_{K+1}F_K \right ] $$
$$ F_{2K+1} = {F_{K+1}}^2+{F_K}^2 $$
We can implement this using the Karatsuba multiplication as follows:


That’s it for today. We saw how far algorithms can go in speed for such simple problems. Let me know in the comments below, if you have any faster or alternate algorithms in mind. Have fun, May zero be with you!