Discuss the optimal method of summing Fibonacci numbers

This weekend, the #random group, mistaken #hardcore of Ruby Vietnam team, has a very interesting discussion about an uncommon problem, that is: Sum the Fibonacci numbers from 1 to 4 million

Simple solution

To calculate a Fibonacci number, it is extremely simple, just follow the formula:


The code is quite simple by using recursion:

Or use a loop to eliminate recursion:

Back to the problem of summing up Fibonacci numbers, we can implement a simple sum function as follows:

However, with such an algorithm, do we have any problems?

The answer is yes, great problem!

First look at the graph showing the time needed to calculate the Fibonacci below:


Obviously, the larger the number of n, the longer the time to calculate the Fibonacci of that number.

So for the problem here is to sum up the Fibonacci numbers from 1 to 4 million, in terms of time factor, this also becomes an impossible problem. To solve this problem, we need to eliminate the time problem caused by recursive or iterative runs.

Since every problem related to arithmetic is, obviously, possible to represent math, so this is not an exception, let's see what we can borrow from math.

The formula for calculating the number of Fibonacci n numbers

We have the formula to sum n the Fibonacci numbers with all numbers n> = 2 as follows:


If you don't trust the recipe, then you can refer to the proof here

So to sum up the Fibonacci numbers from 1 to 4 million, we can find the 4th Fibonacci number of 1 million and 2 (4,000,002) and subtract this value for 1 . The problem returns to find any Fibonacci number.

However, 4 million odd 2 is still too big a number to be able to calculate normally on a personal computer (with factors such as processing speed, memory limit, limit of data type , …). We need to find a less expensive solution.

The formula finds any Fibonacci number

We have 2 ways to do it, one is to use Binet Formula , the other is to use Matrix

Use Binet formula

We have the Binet formula to find any Fibonacci number as follows:


Applying the above two formulas, we can completely eliminate the use of recursion or loop, and this will improve the computational speed significantly.

The way to implement it is extremely simple:

The only drawback of this way is that the calculation with square root on the computer will lead to a rounding condition and a certain error will occur that makes the value not really accurate.

Use matrix

After writing this article, we can introduce another way, a @kiennt , that is using matrix.

Return to the formula for calculating a Fibonacci number:


Synonymous with:


So we can represent the matrix as follows:


Rewrite to something like this:


If you don't believe it, just try and prove it yourself   Next, we can rewrite the expression on:


And after performing some simple calculations on the matrix we obtain the following result:


With F (1) = 1 and F (0) = 0 . The problem returns to the problem of multiplying 2 × 2 matrixes and multiplying a 2 × 2 matrix with a 2 × 1 matrix.

After calculating the above matrix, it is easy to extract the value of F (n) and apply the formula for calculating the sum mentioned at the beginning.

Below is the implementation in Python of a @kiennt :

Thank you very much, the #hardcore group of Ruby Vietnam community has actively discussed to synthesize this article, especially @ nguyenduyhao1111 , @huydx , @kiennt , @unrealhoang

Hopefully the article partly helps you realize the importance of applying mathematics, especially the use of matrices to solve complex programming problems. After writing this synthesizer, I still sat on my forehead, thinking about it, how good it would be to study my math at that time.

ITZone via Kipalog

Share the news now