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:
1 2 3 4 5 6 | Fibonacci func (n: Int) -> Int { if n <= 2 { return 1 } return Fibonacci (n - 1) + Fibonacci (n - 2) } |
Or use a loop to eliminate recursion:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Fibonacci func (n: Int) -> Int { var a = 0 var b = 1 var next = 0 for i prints 0 .. <n { if i <= 1 { next = i } else { next = a + b a = b b = next } } return next } |
Back to the problem of summing up Fibonacci numbers, we can implement a simple sum function as follows:
1 2 3 4 5 6 7 | func Sum (n: Int) -> Int { var sum = 0 for i prints 0 .. <n { sum + = Fibonacci (n) } return sum } |
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:
1 2 3 4 5 6 7 8 9 | import Foundation Fibonacci func (n: Double) -> Double { return (pow ((1.0 + sqrt (5.0)), n) - pow ((1.0 - sqrt (5.0)), n)) / (pow (2.0, n) * sqrt (5.0)) } func Sum (n: Double) -> Double { return Fibonacci (n: n + 2.0) - 1.0 } |
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 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | def mul_metrix_1 (m1, m2): return ( m1 [0] [0] * m2 [0] + m1 [0] [1] * m2 [1], m1 [1] [0] * m2 [0] + m1 [1] [1] * m2 [1] ) def mul_matrix (m1, m2): "" " matrix m1, m2 is 2x2 matrix which is respresend like ((r00, r01), (r10, r11)) "" " return ( (m1 [0] [0] * m2 [0] [0] + m1 [0] [1] * m2 [1] [0], m1 [0] [0] * m2 [0] [1] + m1 [0] [1] * m2 [1] [1]), (m1 [1] [0] * m2 [0] [0] + m1 [1] [1] * m2 [1] [0], m1 [1] [0] * m2 [0] [1] + m1 [1] [1] * m2 [1] [1]) ) def pow_matrix (m, n): "" "m is 2x2 matrix" "" if n == 1: return m elif n% 2 == 0: a = pow_matrix (m, n / 2) return mul_matrix (a, a) else: return mul_matrix (pow_matrix (m, n - 1), m) def fibo (n): if n == 0: return 1 if n == 1: return 1 a = ((1, 1), (1, 0)) an = pow_matrix (a, n) pair_0 = (1, 1) pair_n = mul_metrix_1 (an, pair_0) return pair_n [1] for i in xrange (2, 10): print fibo (i) |
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.