Fibonacci sequence using Python

Since I mentioned the Fibonacci sequence in the Python book I was reading, I will summarize it with a light content like a memo while examining it.

Please note that I am a graduate of design, so there may be various points if you are a graduate of a university related to mathematics or computer science.

Environment to use

What is the Fibonacci sequence in the first place?

It is a sequence named after the Italian mathematician Leonardo Fibonacci (Fibonacci sequence in English).

It is a sequence of values such as 0, 1, 1, 2, 3, 5, 8, 13, 21 ....

The first (index of 0) is 0, the next (index of 1) is 1, and after that, the previous and 2 Written in an expression, it looks like the following (assuming the $ n $ th value in the sequence is $ F_n $).

F_0 = 0\\
F_1 = 1\\
F_n = F_{n - 1} + F_{n - 2}

In addition, this sequence is closely related to the so-called design direction, especially the golden ratio (1: 1.618 ...), and it appears in design-related books.

Even in the natural world, there are various things such as sunflower seeds and nautilus, which are close to the values in this sequence, and it is said that people feel natural and beautiful.

In addition, if you divide a rectangle with a golden ratio into a square and a rectangle, the rectangle will become a rectangle that maintains the golden ratio again, and has various other interesting properties (details are omitted in this article). If you look up articles and books related to mathematics and design, you will find various things, so please check if necessary).

Let's write the calculation process of the value of the Fibonacci sequence in Python

First, without thinking about anything, let's write a process to get the value of the position of the index n of the Fibonacci sequence in Python by calling the function recursively.

def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

As in the above formula, when n is 0 and n is 1, 0 and 1 are returned, respectively, and after that, the total value of the Fibonacci sequence at the positions n-1 and n-2 is set. There is.

Let's run it and see the result.

if __name__ == '__main__':
    for n in range(7):
        print(f'n = {n}in the case of:', fib(n=n))
n =If 0: 0
n =In case of 1: 1
n =In case of 2: 1
n =In case of 3: 2
n =In case of 4: 3
n =In case of 5: 5
n =In case of 6: 8

You can see that the expected value is taken.

Problem that calculation takes time when n becomes large

At this rate, if n becomes large, it will take a long time to calculate.

For example, to calculate the value of n = 5, you have to calculate the values of n = 4 and n = 3, and to calculate n = 4, find the values of n = 3 and n = 2. Every time n increases by one, the conditions that need to be calculated increase exponentially like a family tree.

Let's find out how many times the function prepared for trial was executed. I prepared a variable called count as a global variable.

from datetime import datetime

count: int = 0


def fib(n: int) -> int:
    global count
    count += 1

    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

If you try to execute it with n = 34 and n = 35, you can see that the number of function executions has increased significantly just by increasing n by 1.

n=Run sample on 34


if __name__ == '__main__':
    print(datetime.now(), 'started')
    fib(n=34)
    print('Number of times the function was executed:', count)
    print(datetime.now(), 'ended')
2020-08-30 15:45:15.097393 started
Number of times the function was executed: 18454929
2020-08-30 15:45:17.980419 ended

n=Run sample on 35


if __name__ == '__main__':
    print(datetime.now(), 'started')
    fib(n=35)
    print('Number of times the function was executed:', count)
    print(datetime.now(), 'ended')
2020-08-30 15:49:25.628928 started
Number of times the function was executed: 29860703
2020-08-30 15:49:30.307930 ended

To speed up the calculation ...

As mentioned above, there are various methods to speed up the calculation when n becomes large, and one of them is to cache the execution result of the function.

For example, if the value of n is the same, the return value will be the same, and when calculating the value of large n, the smaller value can be calculated over and over again, so a specific n is already specified. If the case of the value of is already aggregated, it can be cached and the calculation can be skipped, so that the processing can be completed in a short time even if n increases.

You can cache it using a dictionary, but in Python you can use the built-in module functools and specify the lru_cache decorator.

It's easy to use, just set the lru_cache function as a decorator to the function you want to cache. lru is an abbreviation of Least Recently Used, and it is a method of caching in the form of leaving a new execution result (in this case, leaving the calculation result of n cached toward the end).

This time, since the old cache is not deleted and all are cached, None is specified for the argument maxsize.

from datetime import datetime
from functools import lru_cache

count: int = 0


@lru_cache(maxsize=None)
def fib(n: int) -> int:
    global count
    count += 1

    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

When you execute it, you can see that the process is completed in an instant and the number of times it has passed inside the function has decreased at once.

if __name__ == '__main__':
    print(datetime.now(), 'started')
    fib(n=35)
    print('Number of times the function was executed:', count)
    print(datetime.now(), 'ended')
2020-08-30 16:39:49.109241 started
Number of times the function was executed: 36
2020-08-30 16:39:49.110240 ended

References / Reference Sites

Recommended Posts

Fibonacci sequence using Python
Faster Fibonacci sequence calculations (Python version)
Start using Python
Scraping using Python
Python fast fibonacci
Algorithm learned with Python 5th: Fibonacci sequence
I tried recursion with Python ② (Fibonacci sequence)
Operate Redmine using Python Redmine
Data analysis using Python 0
Data cleaning using Python
Implementation of Fibonacci sequence
Using Python #external packages
WiringPi-SPI communication using Python
Age calculation using python
Search Twitter using Python
Name identification using python
Notes using Python subprocesses
Try using Tweepy [Python2.7]
Python notes using perl-ternary operator
Flatten using Python yield from
Scraping using Python 3.5 async / await
Save images using python3 requests
[S3] CRUD with S3 using Python [Python]
[Python] Try using Tkinter's canvas
Using Quaternion with Python ~ numpy-quaternion ~
[Python] Use a string sequence
Try using Kubernetes Client -Python-
Python notes using perl-special variables
[Python] Using OpenCV with Python (Basic)
Scraping using Python 3.5 Async syntax
Website change monitoring using python
Post to Twitter using Python
Start to Selenium using python
Search algorithm using word2vec [python]
Change python version using pyenv
python: Basics of using scikit-learn ①
# 1 [python3] Simple calculation using variables
Create JIRA tickets using Python
Instrument control using Python [pyvisa]
Manipulate spreadsheets locally using Python
Python memo using perl --join
Web scraping using Selenium (Python)
Fibonacci and prime implementations (python)
[Python] I tried using OpenPose
[Python] JSON validation using Voluptuous
Broadcast on LINE using python
Data analysis using python pandas
Translate using googletrans in Python
Using Python mode in Processing
Using OpenCV with Python @Mac
[Python] Shooting game using pyxel
Send using Python with Gmail
Memoization recursion and dynamic programming known by Python Fibonacci sequence
Thank you for the Fibonacci sequence.
Complement python with emacs using company-jedi
How to install python using anaconda
Initializing global variables using Python decorators
[Python] Loading csv files using pandas
Retry post request using python requests
Python Note: About comparison using is
[Ubuntu] [Python] Object tracking using dlib