3 minute read

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) vis-a-vis algorithms.

One side of the coin is the hardware - the speed of computers. The famous Moore's law states that:

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 :

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:

Fn={Fn2+Fn1if n>11if n=10if n=0F_{n} = \begin{cases} F_{n-2} + F_{n-1} & \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,1440, 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, F30F_{30} is over a million, and F100F_{100} is 21 digits long! In general, Fn20.694nF_n \approx 2^{0.694n} Clearly, we need a computing device to calculate say F200F_{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 20.694n(1.6)n2^{0.694n} \approx (1.6)^n, so it takes 1.6 times longer to compute Fn+1F_{n+1} than FnF_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 F100F_{100} with this year's technology, then only after 2 years we will manage to get F101F_{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 nthn^{th} Fibonacci number, FnF_n.

First problem we should realize in the above recursive scheme is that we are recalculating lower FnF_n at each recursion level. Lets solve this issue by storing each calculation and avoiding any re-calculation!

On first glance this looks like an O(n)\mathcal{O}(n) scheme, as we consider each addition as one operation. However, we should realize that as nn increases, addition can not be assumed as a single operation, rather every step of addition is an O(n)\mathcal{O}(n) operation, recall first grade Math for adding numbers digit by digit!! Hence, this algorithm is an O(n2)\mathcal{O}(n^2) scheme. Can we do better?

You bet, we can! Lets consider the following scheme:

(1110)n=(Fn+1FnFnFn1)\begin{pmatrix} 1&1 \cr 1&0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1}&F_n \cr F_n&F_{n-1} \end{pmatrix}

We can use a recursive scheme to calculate this matrix power using a divide and conquer scheme in O(logn)\mathcal{O}(\log{}n) time.

Lets think a bit harder about this. Is it really an O(logn)\mathcal{O}(\log{}n) scheme? It involves multiplication of numbers, the method mul(A, B). What happens when nn is very large? Sure, this will blow up, as typical multiplication would be an O(n2)\mathcal{O}(n^2) operation. So, in fact, our new scheme is O(n2logn)\mathcal{O}(n^2 \log{}n)!

Luckily, we can solve even large multiplications in O(nlog23n1.585)\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 O(n1.585logn)\mathcal{O}(n^{1.585}\log{}n) time.

Here is one final way of solving this problem in the same O(n1.585logn)\mathcal{O}(n^{1.585}\log{}n) time, but using a somewhat simpler scheme!

If we know FKF_K and FK+1F_{K+1}, then we can find,

F2K=FK[2FK+1FK]F_{2K} = F_K \left [ 2F_{K+1}-F_K \right ]
F2K+1=FK+12+FK2F_{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!



Get in touch 👋

Feel free to email me about anything. Want some advice? Give some feedback?

You can also reach me around the web: GitHub, Twitter, LinkedIn