PCP Teaser

Overview and Learning Objectives

This unit briefly introduces basic Python control structures (including if, for, and while), which are similar to most other programming languages. Then, we look at how to create a function in Python using the keyword def. In particular, we discuss the difference between default and non-default arguments. Also, we give some guidelines on how to document a function using a suitable docstring. Finally, we show how one can measure the runtime for executing a function or small code snippets using the Python module timeit. In the first three exercises of this unit, you will implement some simple functions (which can be done in many ways) to familiarize yourself with the Python syntax. In Exercise 4, we consider the mathematical problem of whether a natural number is a prime number. After implementing a simple Python function that solves this task, you should look for more efficient algorithms for primality testing. Going beyond the task specification, you may implement different algorithms and compare their runtime behavior and execution time for increasing numbers. Finally, in Exercise 5, you find an accurate description of an algorithm for finding a root of a continuous function (i.e., an argument where the function assumes the value zero). While being a good exercise for implementing a mathematical procedure in executable Python code, this exercise also reviews some mathematical terms (e.g., interval, root, prime) that we think you should be familiar with. Furthermore, we want to make you aware that the notion of a function may appear in different contexts, e.g., once referring to a Python function and once to a mathematical function $f$ (which itself may serve as an argument to a Python function).

Basic Control Structures

In Python, there are basic control structures similar to most other programming languages. The most important control structures are:

  • if: conditionally execute statements
  • for: repeat statements a specific number of times
  • while: repeat statements an indefinite number of times
  • break: terminate execution of a while or for loop
  • continue: continue execution of a while or for loop at top

For control structures such as if, for or while, one has to use indentations (as part of the syntax). A typical Python convention is to use four spaces (or a tab indent). In the following, we give examples for each of these control structures. Let us start with an if-statement, which is written as follows:

In [1]:
n = -2
if n < 0:
    print('Negative')
elif n > 0:
    print('Positive')    
else:
    print('Zero')
Negative

The next example shows how to use a for-loop. Note that an iterable may be specified by a range, a list, a tuple, or even other structures.

In [2]:
for i in range(3):
    print(i, end='-')
print()
    
for i in ['a', 2, 'c', 'def']:
    print(i, end='-')
print()

for i in 'example':
    print(i, end='-')
print()
0-1-2-
a-2-c-def-
e-x-a-m-p-l-e-

A while-loop is written as follows:

In [3]:
a = 0
while a < 5:
    print(a, end='-')
    a += 1
0-1-2-3-4-

The break-statement is used to terminate the loop containing it. This is demonstrated by the following example, which consists of two nested loops each containing a break-statement.

In [4]:
for k in 'abcd':
    if k == 'c':
        break
    for i in '12345':
        if i == '4':
            break
        print(k + i, end='-')
a1-a2-a3-b1-b2-b3-

The continue-statement is used to terminate only the current step of the loop. The loop then continues with the next iteration.

In [5]:
for k in 'abcd':
    if k == 'c':
        continue
    for i in '12345':
        if i == '4':
            continue
        print(k + i, end='-')
a1-a2-a3-a5-b1-b2-b3-b5-d1-d2-d3-d5-

Python Functions

One defines functions with the def-keyword. As variable names, function names may contain letters (a, b, ..., Y, Z) and the underscore (_). All but the first character can also be positive integer number. Usually one uses lower case letters and underscores to separate words. The following function is named add. It has three arguments a, b, and c (with b and c having a default value). The return keyword is succeeded by the return value.

In [6]:
def add(a, b=0, c=0):
    """Function to add three numbers

    Notebook: PCP_04_control.ipynb

    Args:
        a: first number
        b: second number (Default value = 0)
        c: third number (Default value = 0)

    Returns:
        Sum of a, b and c
    """
    print('Addition: ', a, ' + ', b, ' + ', c)
    return a + b + c

print(add(5))
print(add(5, 2, 1))
print(add(5, c=4))
Addition:  5  +  0  +  0
5
Addition:  5  +  2  +  1
8
Addition:  5  +  0  +  4
9

There are some rules and differences on how to use arguments without and with default values.

  • All non-default arguments must be specified in the function call.
  • The order of default arguments may not be changed in the call.
  • The default arguments are optional in a call. If a value is provided, the default value is overwritten.
  • A function may have any number of default arguments. However, a default argument may not be followed by a non-default argument.

These rules are illustrated by the previous examples. The next example demonstrates that a function may also have multiple return values (which are returned as a tuple):

In [7]:
def add_and_diff(a, b=0):
    """Function to add and subtract two numbers

    Notebook: PCP_04_control.ipynb

    Args:
        a: first number
        b: second number (Default value = 0)

    Returns:
        first: a + b
        second: a - b
    """
    return a + b, a - b

x = add_and_diff(3, 5)
print('result:', x, type(x))
x, y = add_and_diff(3, 5)
print('result:', x, y, type(x), type(y))
x, y = add_and_diff(3.0, 5)
print('result:', x, y, type(x), type(y))
result: (8, -2) <class 'tuple'>
result: 8 -2 <class 'int'> <class 'int'>
result: 8.0 -2.0 <class 'float'> <class 'float'>

It is important to document a function. In particular, one should always describe the purpose of a function as well as its input and output. This is exactly what a docstring is used for. As described in the Python Docstring Conventions, a docstring is a string literal that occurs as the first statement in the function. For consistency, it is advised to use """triple double quotes""" around docstrings. Using the help() function, the content of the docstring is shown. This is a useful feature when building your own libraries with many functions. In the following code cell, we show the docstring of the function add defined above.

In [8]:
help(add)
Help on function add in module __main__:

add(a, b=0, c=0)
    Function to add three numbers
    
    Notebook: PCP_04_control.ipynb
    
    Args:
        a: first number
        b: second number (Default value = 0)
        c: third number (Default value = 0)
    
    Returns:
        Sum of a, b and c

Efficiency and Runtime

In the following example, we consider the task of computing the sum $\sum_{i=1}^n i$ for a given integer $n\in\mathbb{N}$. We first implement a naive function sum_n that uses a simple for-loop. We then execute the function sum_n in a while-loop for increasing $n=1,2,3,...$ and output the result until the sum exceeds $100$.

In [9]:
def sum_n(n):
    """Function that sums up the integers from 1 to n

    Notebook: PCP_04_control.ipynb

    Args:
        n: Integer number

    Returns:
        s: Sum of integers from 1 to n
    """
    s = 0
    for n in range(1, n+1):
        s = s + n
    return s

n = 1
while sum_n(n) <= 100:
    print(f'n= {n}, s={sum_n(n)}')
    n += 1
n= 1, s=1
n= 2, s=3
n= 3, s=6
n= 4, s=10
n= 5, s=15
n= 6, s=21
n= 7, s=28
n= 8, s=36
n= 9, s=45
n= 10, s=55
n= 11, s=66
n= 12, s=78
n= 13, s=91

Rather than using a for-loop, one may think more efficient functions to compute this sum. In the following code cell, we consider the function sum_n_numpy that is based on the efficient NumPy-function np.sum. Furthermore, we consider the function sum_n_math which uses a closed mathematical formula for calculating the sum. We then measure and compare the execution time for the three different implementations. To this end, we use the Python module timeit, which provides a simple way to measure the execution time of small bits of Python code. As an alternative, one may also use the function time.time() of the module time.

In [10]:
import numpy as np

def sum_n_numpy(n):
    """Function that sums up the integers from 1 to n  using numpy

    Notebook: PCP_04_control.ipynb

    Args:
        n: Integer number

    Returns:
        s: Sum of integers from 1 to n
    """
    s = np.sum(np.arange(1, n+1))
    return s    

def sum_n_math(n):
    """Function that sums up the integers from 1 to n using the idea by Gauss

    Notebook: PCP_04_control.ipynb

    Args:
        n: Integer number

    Returns:
        s: Sum of integers from 1 to n
    """
    s = n * (n + 1) // 2
    return s   

n = 1000
print(f'Computation with sum_n:       n={n}, s={sum_n(n)}')
print(f'Computation with sum_n_numpy: n={n}, s={sum_n_numpy(n)}')
print(f'Computation with sum_n_math:  n={n}, s={sum_n_math(n)}')

# Measuring runtime of different implementations 
import timeit
executions = 100
n = 10000
runtime_av = timeit.timeit(lambda: sum_n(n), number=executions) / executions
print(f'Runtime for sum_n: {runtime_av * 1000:.6f} ms')

runtime_av = timeit.timeit(lambda: sum_n_numpy(n), number=executions) / executions
print(f'Runtime for sum_n_numpy: {runtime_av * 1000:.6f} ms')

runtime_av = timeit.timeit(lambda: sum_n_math(n), number=executions) / executions
print(f'Runtime for sum_n_math: {runtime_av * 1000:.6f} ms')
Computation with sum_n:       n=1000, s=500500
Computation with sum_n_numpy: n=1000, s=500500
Computation with sum_n_math:  n=1000, s=500500
Runtime for sum_n: 0.385383 ms
Runtime for sum_n_numpy: 0.008619 ms
Runtime for sum_n_math: 0.000155 ms
Note: In Python programming, one can use the concept of lambda expressions when an anonymous one-line function is needed temporarily in a specific setting. Such a function takes the form lambda args: expression, where the expression is executed and the result is returned. For more details we refer to the Python Documentation.

Exercises and Results

In [11]:
import libpcp.control
show_result = True

Exercise 1: Function give_me_a_number
Write a function give_me_a_number that has a string variable s as input argument. When s is the string 'large', the function should return the value $2^{100}$. If s is 'small', it should return $2^{-100}$. If s is 'random', it should return a random number in the range $[0,1)$ (using np.random.rand). In all other cases, the function should return np.nan. As default, set the input argument to the string 'nan'.
In [12]:
#<solution>
# Your Solution
#</solution>
In [13]:
libpcp.control.exercise_give_number(show_result=show_result)
default:    nan
s='large':  1267650600228229401496703205376
s='small':  7.888609052210118e-31
s='random': 0.42955001078442256
s='test':   nan

Exercise 2: Function for Computing Row Mean
Write a function row_mean that inputs a matrix and outputs a vector containing the row-wise means (averages) of the input matrix. Apply the function to the matrix matrix $\mathbf{A} = \begin{bmatrix}1 & 2 & 6 \\5 & 5 & 2\\\end{bmatrix}$.
In [14]:
#<solution>
# Your Solution
#</solution>
In [15]:
libpcp.control.exercise_row_mean(show_result=show_result)
Input matrix:
[[1 2 6]
 [5 5 2]]
Vector containing the row means:  [3. 4.]

Exercise 3: Function for Computing Odd-Index Vector
Given a vector x (in form of a one-dimensional NumPy array), write a function vector_odd_index that outputs a vector y consisting only of the elements of x at an odd index position. If the input NumPy array x is not a vector, the function vector_odd_index should output y=None.
Note: Recall that Python indexing starts with index 0 (which is an even index).
In [16]:
#<solution>
# Your Solution
#</solution>
In [17]:
libpcp.control.exercise_odd(show_result=show_result)
x = [0 1 2 3 4 5 6 7 8 9]
y = [1 3 5 7 9]
x = [[0 1 2 3 4 5 6 7 8 9]]
y = None
x =
[[1 2 3]
 [4 5 6]]
y = None

Exercise 4: Primality Test
An integer $n\in\mathbb{N}$ is called a prime number if $n>1$ and if $n$ is divisible only by $1$ and itself. Write a function isprime that inputs an integer n and outputs the boolean value True if n is a prime number and False otherwise.
  • Test your function for $n=1$, $n=17$, $n=1221$, and $n=1223$.
  • Use this function to output the first $20$ prime numbers.
  • Discuss efficiency issues. Is there a more efficient way to compute the first $20$ prime numbers?
  • Have a look at the algorithm Sieve of Eratosthenes, which is an ancient algorithm for finding all prime numbers up to any given limit.
In [18]:
#<solution>
# Your Solution
#</solution>
In [19]:
libpcp.control.exercise_isprime(show_result=show_result)
n = 1, isprime = False
n = 17, isprime = True
n = 1221, isprime = False
n = 1223, isprime = True
List of first 20 prime numbers:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 

Exercise 5: Function for Root Finding
Let $f:\mathbb{R}\to\mathbb{R}$ be a continuous function and let $a,b\in\mathbb{R}$ be two numbers such that $aroot in the interval $[a,b]$. In other words, there is a number $r\in[a,b]$ such that $f(r)=0$. To find such a root, one can proceed as follows:
  • Let $c = (a+b)/2$ be the center. If $f(a)=0$, $f(b)=0$, or $f(c)=0$, then we have found a root and we can stop.
  • Otherwise, either $f(a)$ and $f(c)$, or $f(c)$ and $f(b)$ have opposite signs. In the first case, continue with the interval $[a,c]$, otherwise with the interval $[c,b]$.
  • Iterate this interval-halving procedure until the interval size is below a given threshold parameter (e.g., $10^{-5}$) and a sufficient approximation for the root is obtained.

Write a function search_root that implements this procedure (also known as bisection method). The input arguments should be f, a, b, and thresh. Here, f is a Python function realizing a continuous function $f:\mathbb{R}\to\mathbb{R}$. The parameter thresh is the threshold parameter, which should be set to the value $10^{-5}$ by default. The function search_root should check if a < b and if the opposite sign condition for f(a) and f(b) is fulfilled (if not it should return the value np.nan).

  • Evaluate search_root for f given by $f(x) = x^2-2$, a=0, and b=2.
    (Note: You may define a separate Python function f that implements $f(x) = x^2-2$. This function can then be used as one of the input argument to the Python function search_root.)
  • Test search_root for the same function when using a=2 and b=4.
  • Test search_root for the same function when using a=4 and b=2.
  • Evaluate search_root for f being np.sin using a=3 and b=4.
Note: In this exercise, we draw attention to the fact that the argument of a Python function (e.g., search_root) can be a function itself (e.g., f). In Python, a function is simply an object that can be referred to in the same way one refers to a number, a string, or a list. For further explanations, we refer to the article on Passing a function as an argument to another function in Python.
In [20]:
#<solution>
# Your Solution
#</solution>
In [21]:
libpcp.control.exercise_root(show_result=show_result)
=== Function f(x) = x**2-2 ===
a = 0.000000, b = 2.000000, c = 1.000000, f(a) = -2.000000, f(b) = 2.000000, f(c) = -1.000000
a = 1.000000, b = 2.000000, c = 1.500000, f(a) = -1.000000, f(b) = 2.000000, f(c) = 0.250000
a = 1.000000, b = 1.500000, c = 1.250000, f(a) = -1.000000, f(b) = 0.250000, f(c) = -0.437500
a = 1.250000, b = 1.500000, c = 1.375000, f(a) = -0.437500, f(b) = 0.250000, f(c) = -0.109375
a = 1.375000, b = 1.500000, c = 1.437500, f(a) = -0.109375, f(b) = 0.250000, f(c) = 0.066406
a = 1.375000, b = 1.437500, c = 1.406250, f(a) = -0.109375, f(b) = 0.066406, f(c) = -0.022461
a = 1.406250, b = 1.437500, c = 1.421875, f(a) = -0.022461, f(b) = 0.066406, f(c) = 0.021729
a = 1.406250, b = 1.421875, c = 1.414062, f(a) = -0.022461, f(b) = 0.021729, f(c) = -0.000427
a = 1.414062, b = 1.421875, c = 1.417969, f(a) = -0.000427, f(b) = 0.021729, f(c) = 0.010635
a = 1.414062, b = 1.417969, c = 1.416016, f(a) = -0.000427, f(b) = 0.010635, f(c) = 0.005100
a = 1.414062, b = 1.416016, c = 1.415039, f(a) = -0.000427, f(b) = 0.005100, f(c) = 0.002336
a = 1.414062, b = 1.415039, c = 1.414551, f(a) = -0.000427, f(b) = 0.002336, f(c) = 0.000954
a = 1.414062, b = 1.414551, c = 1.414307, f(a) = -0.000427, f(b) = 0.000954, f(c) = 0.000263
a = 1.414062, b = 1.414307, c = 1.414185, f(a) = -0.000427, f(b) = 0.000263, f(c) = -0.000082
a = 1.414185, b = 1.414307, c = 1.414246, f(a) = -0.000082, f(b) = 0.000263, f(c) = 0.000091
a = 1.414185, b = 1.414246, c = 1.414215, f(a) = -0.000082, f(b) = 0.000091, f(c) = 0.000004
a = 1.414185, b = 1.414215, c = 1.414200, f(a) = -0.000082, f(b) = 0.000004, f(c) = -0.000039
a = 1.414200, b = 1.414215, c = 1.414207, f(a) = -0.000039, f(b) = 0.000004, f(c) = -0.000017
Root r = 1.414207, f(r) = -0.000017
=== Function f(x) = x**2-2 ===
a = 2.000000, b = 4.000000, f(a) = 2.000000, f(b) = 14.000000
Sign condition not fulfilled
Root r = nan, f(r) = nan
=== Function f(x) = x**2-2 ===
a = 4.000000, b = 2.000000
Interval not valid.
Root r = nan, f(r) = nan
=== Function f(x) = sin(x) ===
a = 3.000000, b = 4.000000, c = 3.500000, f(a) = 0.141120, f(b) = -0.756802, f(c) = -0.350783
a = 3.000000, b = 3.500000, c = 3.250000, f(a) = 0.141120, f(b) = -0.350783, f(c) = -0.108195
a = 3.000000, b = 3.250000, c = 3.125000, f(a) = 0.141120, f(b) = -0.108195, f(c) = 0.016592
a = 3.125000, b = 3.250000, c = 3.187500, f(a) = 0.016592, f(b) = -0.108195, f(c) = -0.045891
a = 3.125000, b = 3.187500, c = 3.156250, f(a) = 0.016592, f(b) = -0.045891, f(c) = -0.014657
a = 3.125000, b = 3.156250, c = 3.140625, f(a) = 0.016592, f(b) = -0.014657, f(c) = 0.000968
a = 3.140625, b = 3.156250, c = 3.148438, f(a) = 0.000968, f(b) = -0.014657, f(c) = -0.006845
a = 3.140625, b = 3.148438, c = 3.144531, f(a) = 0.000968, f(b) = -0.006845, f(c) = -0.002939
a = 3.140625, b = 3.144531, c = 3.142578, f(a) = 0.000968, f(b) = -0.002939, f(c) = -0.000985
a = 3.140625, b = 3.142578, c = 3.141602, f(a) = 0.000968, f(b) = -0.000985, f(c) = -0.000009
a = 3.140625, b = 3.141602, c = 3.141113, f(a) = 0.000968, f(b) = -0.000009, f(c) = 0.000479
a = 3.141113, b = 3.141602, c = 3.141357, f(a) = 0.000479, f(b) = -0.000009, f(c) = 0.000235
a = 3.141357, b = 3.141602, c = 3.141479, f(a) = 0.000235, f(b) = -0.000009, f(c) = 0.000113
a = 3.141479, b = 3.141602, c = 3.141541, f(a) = 0.000113, f(b) = -0.000009, f(c) = 0.000052
a = 3.141541, b = 3.141602, c = 3.141571, f(a) = 0.000052, f(b) = -0.000009, f(c) = 0.000022
a = 3.141571, b = 3.141602, c = 3.141586, f(a) = 0.000022, f(b) = -0.000009, f(c) = 0.000006
a = 3.141586, b = 3.141602, c = 3.141594, f(a) = 0.000006, f(b) = -0.000009, f(c) = -0.000001
Root r = 3.141594, sin(r) = -0.000001
PCP License