I learned dynamic programming when I was in my second year of undergraduate school. However, if I don't use that knowledge, I will forget more and more. I will write this article to touch on and remember the Fibonacci sequence based on such a basic point.
What is the Fibonacci sequence?
\begin{align}
F_0 = 0 \quad \quad \quad \quad \quad \quad \quad \\
F_1 = 1 \quad \quad \quad \quad \quad \quad \quad \\
F_n = F_{n-1} + F_{n-2} \quad (n > 2)\\
\end{align}
It is a formula represented by.
What should I do especially in programming here?
fib.py
import time
def fib_stupid(n):
if(n == 0):
return 0
elif(n == 1):
return 1
else:
return fib_stupid(n-1) + fib_stupid(n-2)
#fib_stupid()Call twice
start = time.time()
print(fib_stupid(40))
process_time = time.time() - start
print("Time :" + str(process_time))
102334155
Time :75.65844893455505[s]
This is as defined. However, the order quantity for this calculation is very large. This is because when finding fib_stupid (n), it is necessary to find fib_stupid (n-1) and fib_stupid (n-2), which is recursively called twice with one fib_stupid (), so after all, $ You end up calling the function by O (2 ^ {(n-1)} --2) $. Actually, if you want to find $ F_9 $, you need to find $ F_8 $ and $ F_7 $. To find $ F_8 $, you need to find $ F_7 $, and you need to calculate $ F_7 $ twice. It is very inefficient because it comes.
Here, we will consider dynamic programming in order to think efficiently.
Dynamic programming is an algorithm with a recursive structure that finds multiple small problems from a target problem and solves them to solve the original problem.
The following introduces algorithms that can be calculated with $ O (n), O (log (n)) $.
fib.py
import sys
sys.setrecursionlimit(30000)
#Upper limit setting for recursive processing
def make_list_for_topdown(n):
l = [0]
l.append(1)
for i in range(n-1):
l.append(-1)
return l
lst = make_list_for_topdown(30000)
#This time I set the shape of list so that up to 3000 can be requested
def fib_topdown(n):
if(lst[n] != -1):
return lst[n]
else:
lst[n] = fib_topdown(n-1) + fib_topdown(n-2)
return lst[n]
start = time.time()
print(fib_topdown(40))
fib_topdown(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
Time :0.10364508628845215[s]
For this, the value of the Fibonacci sequence is saved by creating an array called lst. This avoids duplicate calculations like the one above. It seems that the number of function calls is the same as that of fib_stupid (), but since the result remains in the array, the amount of calculation is $ O (2 (n-2)) $, which is much higher than before. It's faster.
fib.py
def fib_bottomup(n):
if(n < 2):
return n
else:
num_0 = 0
num_1 = 1
num_2 = -1
for i in range(n-1):
num_2 = num_0 + num_1
num_0 , num_1 = num_1, num_2
return num_2
start = time.time()
print(fib_bottomup(40))
fib_bottomup(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
Time :0.023389101028442383[s]
Here, you only have to memorize the latest two states with num_0 and num_1 and add them together, and it does not have a recursive structure. Therefore, it can be calculated with $ O (n-2) $.
I expected it to be about twice as fast as the bottom-up order, but for some reason the result was about five times faster. It is thought that the result of the process of generating and reading the list is such a result (If you want to verify accurately, you should do several processing times and average and distribute, but talk I will omit it this time because it deviates.)
The general term of the Fibonacci sequence can be expressed as follows by solving the recurrence formula.
F_n = \frac{1}{\sqrt{5}}\Biggl\{\biggl( \frac{1+\sqrt{5}}{2}\biggl)^n- \biggl( \frac{1-\sqrt{5}}{2}\biggl)^n\Biggl\}
Therefore, apply as follows.
fib.py
import math
def fib_general_term(n):
return math.floor((1/math.sqrt(5))*(((1+math.sqrt(5))/2)**n-((1-math.sqrt(5))/2)**n))
start = time.time()
print(fib_general_term(40))
try:
fib_general_term(30000)
except OverflowError:
print("OverflowError")
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
OverflowError
Time :0.00013494491577148438[s]
This time, the decimal point comes out because we used the route operation. Therefore, I adjusted it with the floor function. Also, the upper limit of float is 1.9796931348623157e + 308, and exception handling is applied because $ F_ {30000} $ is larger than that (it was possible to calculate because int has no upper limit). However, it is still possible that it is faster than the above two dynamic programming methods. It is due to the power calculation order being $ O (log (n)) $. By considering even and odd numbers, the process of multiplying n times is shortened. A similar example can be considered in the determinant, so I will explain it in that example (of course, it is not a versatile programming because exception handling is applied).
The recurrence formula of the Fibonacci sequence can also be expressed by the following matrix product.
\begin{pmatrix}
F_{n} \\
F_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n-1} \\
F_{n-2}
\end{pmatrix}
In other words
A
:=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}\\
\begin{align}
\begin{pmatrix}
F_{n} \\
F_{n-1}
\end{pmatrix}
=A
\begin{pmatrix}
F_{n-1} \\
F_{n-2}
\end{pmatrix}
=A^2
\begin{pmatrix}
F_{n-2} \\
F_{n-3}
\end{pmatrix}
=A^{n-1}
\begin{pmatrix}
F_{n-(n-1)} \\
F_{n-1-(n-1)}
\end{pmatrix} \\
=A^{n-1}
\begin{pmatrix}
1 \\
0
\end{pmatrix}
\end{align}
Can be written. (n> 0) If $ A ^ n $ is $ n = 2 ^ k $, it can be obtained by repeating the square k times as shown below. For example, if $ n = 35 $, Because $ n = 2 ^ 5 + 2 ^ 1 + 2 ^ 0 $ $ A ^ {35} = A ^ {2 ^ 5} A ^ {2 ^ 1} A ^ {2 ^ 0} = ((((A ^ 2) ^ 2) ^ 2) ^ 2) ^ 2A ^ 2A Will be $ (Another way of thinking The idea is $ 35 = 2 * 17 + 1 = 2 * (2 * 8 + 1) + 1 = ... $. I personally thought it would be easier to understand). As you can see from the above, this time it ends with 6 times, that is, $ log (35) $ times. In other words, the order of the calculation of the Fibonacci sequence by the power of the matrix in this algorithm is $ log (n) $. The specific code is as follows (in python, of course, the operation of the determinant is in numpy, but since it is the same as the calculation method by the general term above, numpy is not used intentionally).
fib.py
def make_matrix(row_len,column_len):
matrix_c = [[0]*column_len for _ in range(row_len)]
return matrix_c
def matrix_mul(a,b):
c = make_matrix(len(a),len(b[0]))
for i in range(len(a)):
for k in range(len(b)):
for j in range(len(b[0])):
c[i][j] += a[i][k] * b[k][j]
return c
def matrix_pow(a,n):
b = make_matrix(len(a), len(a))
for i in range(len(a)):
b[i][i] = 1
while(n>0):
if(n & 1):
b = matrix_mul(a,b)
else:
pass
a = matrix_mul(a,a)
n >>= 1
return b
def fib_matrix(n):
if n == 0:
return 0
a = make_matrix(2,2)
a[0][0] = 1
a[0][1] = 1
a[1][0] = 1
a[1][1] = 0
a = matrix_pow(a, n)
return a[1][0]
start = time.time()
print(fib_matrix(40))
fib_matrix(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
Time :0.002933025360107422[s]
Here you can see that it is about 10 times faster than the bottom-up method.
By using the dynamic programming method described above, the amount of calculation can be significantly reduced. This is a basic matter, so I would like to summarize various DPs at a later date.
-Dynamic programming speeds up the calculation of Fibonacci sequences. https://yosuke-furukawa.hatenablog.com/entry/20120120/1327056359
Recommended Posts