Calculate Fibonacci Numbers Concurrently in Python

February 11, 2022 Python ProcessPoolExecutor

The ProcessPoolExecutor class in Python can be used to calculate multiple Fibonacci numbers at the same time.

This can dramatically speed-up your program compared to calculating Fibonacci numbers, one-by-one.

In this tutorial, you will discover how to calculate Fibonacci concurrently using a pool of worker processes.

Let's dive in.

How to Calculate Fibonacci Numbers One at a Time (slowly)

Fibonacci numbers are a famous sequence of numbers.

For example, the first handful of numbers in the sequence are as follows:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

The sequence of numbers are related to the golden ratio and are named after the discoverer of the sequence known as Fibonacci.

It is a common mathematical task to calculate the n'th Fibonacci number, that is the Fibonacci number at a specific point in the sequence.

The numbers in the sequence are calculated as the sum of the last two numbers in the sequence where the first two numbers in the sequence are 0 and 1.

For example:

f_n = f_(n-1) + f_(n-2)

If we were to calculate the third number in the sequence (n=3) and we known that f1=1 and f0=0, then it would be calculated as:

f_n = f_(n-1) + f_(n-2)
f3 = 1 + 0
f3 = 1

Given that the n'th Fibonacci is dependent on the previous two numbers in the sequence, the only way to figure out what a given number in the sequence is, is to calculate it.

This makes it a good task to explore concurrency in Python. For example, we might ask for a few different Fibonacci numbers and require our CPUs to grind away and compute them.

Next, let's see how we can calculate Fibonacci numbers in Python.

Calculate Fibonacci Numbers

Calculating Fibonacci numbers is relatively straightforward.

Let's look at the two main approaches, recursive and iterative implementations.

Calculate Fibonacci Numbers Recursively

Perhaps the most common implementation is to calculate the numbers recursively. That is to write a function that calls itself.

Writing recursive functions is a common exercise for new programmers and computer science students, although it is probably poor form in modern software development.

Given that we want to calculate the n'th number in the sequence as the sum of the previous two numbers, we can define a function that calls itself to calculate the n-1 and n-2 numbers in the sequence. The recursive call continues until we reach 0 or 1 in which case we bubble the numbers back up.

For example, the function below will calculate Fibonacci numbers using recursion.

# calculate the nth fibonacci number
def fibonacci(n):
    # check for the start of the sequence
    if n <= 1:
        return n
    return (fibonacci(n-1) + fibonacci(n-2))

Let's desk-check the function.

Consider we want to calculate the 4th number:

fibonacci(4) = fibonacci(3) + fibonacci(2) = 3
    fibonacci(3) = fibonacci(2) + fibonacci(1) = 2
        fibonacci(2) = fibonacci(1) + fibonacci(0) = 1
            fibonacci(1) = 1
            fibonacci(0) = 0
        fibonacci(1) = 1
    fibonacci(2) = fibonacci(1) + fibonacci(0) = 1
        fibonacci(1) = 1
        fibonacci(0) = 0

We can see that f(4) = 3, which is correct.

The example below uses this recursive implementation of calculating Fibonacci numbers to calculate the first 30 numbers in the sequence.

# SuperFastPython.com
# calculate fibonacci numbers using recursion

# calculate the nth fibonacci number
def fibonacci(n):
    # check for the start of the sequence
    if n <= 1:
        return n
    return (fibonacci(n-1) + fibonacci(n-2))

# calculate some fibonacci numbers
for i in range(30):
    print(f'f({i}) = {fibonacci(i)}')

Running the example calculates and reports Fibonacci numbers from 0 to 29.

f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 5
f(6) = 8
f(7) = 13
f(8) = 21
f(9) = 34
f(10) = 55
f(11) = 89
f(12) = 144
f(13) = 233
f(14) = 377
f(15) = 610
f(16) = 987
f(17) = 1597
f(18) = 2584
f(19) = 4181
f(20) = 6765
f(21) = 10946
f(22) = 17711
f(23) = 28657
f(24) = 46368
f(25) = 75025
f(26) = 121393
f(27) = 196418
f(28) = 317811
f(29) = 514229

By the time we start calculating numbers around 30, this recursive approach becomes very slow.

This is not surprising given that there is a lot of redundancy in this recursive implementation. We have to calculate the same sub-sequences many times.

Let's consider an iterative approach.

Calculate Fibonacci Numbers Iteratively

We can develop an iterative algorithm for calculating Fibonacci numbers.

It too is relatively straightforward.

First, we need to define the start of the sequence, that is the 0th and 1st numbers in the sequence as 0 and 1 respectively.

...
# start the sequence
f0, f1 = 0, 1

We then need to build up a sum to the nth number in the sequence.

This can be achieved with just two variables.

Each iteration we can shift up the sequence by one element, where f0 is the current number in the sequence and f1 is the next number in the sequence.

We continue to inch up the sequence until we reach the desired nth number.

...
# compute the nth number
for _ in range(0, n):
    f0, f1 = f1, (f1 + f0)

The function below implements this algorithm, common to many programming textbooks.

# calculate the nth fibonacci number
def fibonacci(n):
    # start the sequence
    f0, f1 = 0, 1
    # compute the nth number
    for _ in range(0, n):
        f0, f1 = f1, (f1 + f0)
    return f0

Let's desk-check it with n=4.

Definition (n=0)
    f0 = 0
    f1 = 1
    f(0) = 0
Iteration 0:
    f0 = f1 = 1
    f1 = f1 + f0 = 1 + 0 = 1
    f(1) = f0 = 1
Iteration 1:
    f0 = f1 = 1
    f1 = f1 + f0 = 1 + 1 = 2
    f(2) = f0 = 1
Iteration 2: (n=3)
    f0 = f1 = 2
    f1 = f1 + f0 = 1 + 2 = 3
    f(3) = f0 = 2
Iteration 3:
    f0 = f1 = 3
    f1 = f1 + f0 = 2 + 3 = 5
    f(3) = 3

Looks good.

The complete example of calculating the first 30 Fibonacci numbers is listed below.

# SuperFastPython.com
# calculate fibonacci numbers using iteration

# calculate the nth fibonacci number
def fibonacci(n):
    # start the sequence
    f0, f1 = 0, 1
    # compute the nth number
    for _ in range(0, n):
        f0, f1 = f1, (f1 + f0)
    return f0

# calculate some fibonacci numbers
for i in range(30):
    print(f'f({i}) = {fibonacci(i)}')

Running the example, we can see that we get the same sequence of numbers as the recursive case.

It is also a lot faster as it does not have to recalculate each sub-sequence while calculating each Fibonacci number, as we did with the recursive case.

f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 5
f(6) = 8
f(7) = 13
f(8) = 21
f(9) = 34
f(10) = 55
f(11) = 89
f(12) = 144
f(13) = 233
f(14) = 377
f(15) = 610
f(16) = 987
f(17) = 1597
f(18) = 2584
f(19) = 4181
f(20) = 6765
f(21) = 10946
f(22) = 17711
f(23) = 28657
f(24) = 46368
f(25) = 75025
f(26) = 121393
f(27) = 196418
f(28) = 317811
f(29) = 514229

Now that we know how to calculate Fibonacci numbers, let's look at calculating lots of numbers.

Calculate Many Fibonacci Numbers

We can use our iterative implementation for calculating Fibonacci numbers to calculate many numbers in the sequence.

For example, we can calculate the first 10,000 numbers.

First, we can define an iterable with the numbers we want to calculate, in this case a range.

...
# fibonacci numbers to calculate
numbers = range(10000)

We can then iterate over the numbers, calculate the Fibonacci number for each then store them in a dictionary that maps the number in the sequence (input) to the Fibonacci number (output).

...
# calculate each in turn
results = {}
for i in numbers:
    results = fibonacci(i)

This is Python, so we can do better than this.

Let's use the map() built-in function to apply the fibonacci() function to each value in the iterable to give an iterable of results.

...
# calculate fibonacci numbers
fibs = map(fibonacci, numbers)

We can then create a dictionary directly from the iterable of numbers and the iterable of results by using the zip() built-in function.

...
# store results
results = dict(zip(numbers, fibs))

You can do this on one line if you like, but I try to avoid large compound statements.

...
# calculate fibonacci numbers
results = dict(zip(numbers, map(fibonacci, numbers)))

Tying this together, the complete example of calculating the first 10,000 Fibonacci numbers is as follows:

# SuperFastPython.com
# calculate some large fibonacci numbers

# calculate the nth fibonacci number
def fibonacci(n):
    # start the sequence
    f0, f1 = 0, 1
    # compute the nth number
    for _ in range(0, n):
        f0, f1 = f1, (f1 + f0)
    return f0

# entry point
if __name__ == '__main__':
    # fibonacci numbers to calculate
    numbers = range(10000)
    # calculate fibonacci numbers
    fibs = map(fibonacci, numbers)
    # store results
    results = dict(zip(numbers, fibs))
    print('Done')

Running the example will take a moment.

On my system it takes about 6.5 seconds.

How long does it take to run on your system?
Let me know in the comments below.

Next, let's look at how we can adapt our program for calculating Fibonacci numbers to make use of the ProcessPoolExecutor.

Calculate Fibonacci Numbers Concurrently

We can update the example of calculating Fibonacci numbers to use the ProcessPoolExecutor.

Given that we are already using the built-in map() function, we can update the example to use the ProcessPoolExecutor map() function directly.

First, we can create the process pool with the default number of processes that matches the number of logical cores in our system.

...
# create the process pool
with ProcessPoolExecutor() as executor:
    # ...

We can then update the call to map() to use the executor, for example:

...
# calculate concurrently
fibs = executor.map(fibonacci, numbers)

And that's it.

The complete example of calculating Fibonacci numbers concurrently using multiple CPU cores is listed below.

# SuperFastPython.com
# calculate some large fibonacci numbers concurrently
from concurrent.futures import ProcessPoolExecutor

# calculate the nth fibonacci number
def fibonacci(n):
    # start the sequence
    f0, f1 = 0, 1
    # compute the nth number
    for _ in range(0, n):
        f0, f1 = f1, (f1 + f0)
    return f0

# entry point
if __name__ == '__main__':
    # create the process pool
    with ProcessPoolExecutor() as executor:
        # fibonacci numbers to calculate
        numbers = range(10000)
        # calculate concurrently
        fibs = executor.map(fibonacci, numbers)
        # store results
        results = dict(zip(numbers, fibs))
    print('Done')

Running the example is dramatically faster compared to the sequential case.

On my system, it executes in about 2.7 seconds, compared to the 6.5 seconds for the serial version. That is about a 2.4x speedup.

How much speed-up did you see on your system?
Let me know in the comments below.

Speed-up Calculating Fibonacci Numbers with Chunksize

We can further speed-up the concurrent calculation of Fibonacci numbers.

The map() function on the ProcessPoolExeuctor takes a "chunksize" argument.

This argument is responsible for mapping tasks submitted to the process pool to internal tasks that are sent to worker processes in the pool for execution.

If the tasks are short duration and we have a lot of tasks to execute, then configuring the chunksize argument is a good idea. This matches our specific use case, we have a large number of short duration tasks.

By default the chunksize argument is set to 1, meaning each task submitted to the process pool is mapped to one internal task and sent to a worker process. Each task has some computational and memory overhead as it must be serialized (pickled) and transmitted to a separate process using inter-process communication. Fewer internal tasks means less overhead and a faster overall process.

...
# calculate concurrently
fibs = executor.map(fibonacci, numbers, chunksize=1)

A good starting point for setting the chunksize is to divide the number of tasks by the number of logical CPUs.

...
# mapping of external tasks to internal tasks
size = 10000 / 8
# calculate concurrently
fibs = executor.map(fibonacci, numbers, chunksize=size)

This is good if all tasks have about the same execution duration, but that is not the case here as calculating the n=10 Fibonacci number is a lot faster than calculating the f=1000 number.

As such, it is a good idea to try different chunksize values and see what works best.

After some experimentation, I found that a value of 50 works well for this problem on my system.

...
# mapping of external tasks to internal tasks
size = 50
# calculate concurrently
fibs = executor.map(fibonacci, numbers, chunksize=size)

Experiment with different chunksizes in order to discover what works best on your system. Let me know in the comments below, I'd love to see what you discover.

The complete example of calculating Fibonacci numbers concurrently with an optimized chunksize is listed below.

# SuperFastPython.com
# calculate some large fibonacci numbers concurrently
from concurrent.futures import ProcessPoolExecutor

# calculate the nth fibonacci number
def fibonacci(n):
    # start the sequence
    f0, f1 = 0, 1
    # compute the nth number
    for _ in range(0, n):
        f0, f1 = f1, (f1 + f0)
    return f0

# entry point
if __name__ == '__main__':
    # create the process pool
    with ProcessPoolExecutor() as executor:
        # fibonacci numbers to calculate
        numbers = range(10000)
        # mapping of external tasks to internal tasks
        size = 50
        # calculate concurrently
        fibs = executor.map(fibonacci, numbers, chunksize=size)
        # store results
        results = dict(zip(numbers, fibs))
    print('Done')

Running the example calculates the first 10,000 Fibonacci numbers as before, but is faster again than the concurrent version above.

On my system the example completes in about 1.6 seconds, compared to 2.7 seconds when chunksize=1 in the previous section.

How much further speed-up did you see on your system?
Let me know in the comments below.

Extensions

This section lists ideas for extending the tutorial.

Memorize Calculated Numbers. Update the example so that the fibonacci() function memorizes and reuses previously calculated numbers in the sequence.
Parallelize Calculation of One Number. Explore how you might parallelize the calculation of a single number in the sequence using the process pool.
Tune Chunksize. Tune the chunksize argument on your system and compare a range of values in order to discover what value is optimal.

Share your extensions in the comments below, it would be great to see what you come up with.

Takeaways

In this tutorial you discovered how to calculate Fibonacci concurrently using a pool of worker processes.

If you enjoyed this tutorial, you will love my book: Python ProcessPoolExecutor Jump-Start. It covers everything you need to master the topic with hands-on examples and clear explanations.