# Unit 4: Basic Control Structures and Functions¶

- Overview and Learning Objectives
- Basic Control Structures
- Python Functions
- Efficiency and Runtime
- Exercise 1: Function `give_me_a_number`
- Exercise 2: Function for Computing Row Mean
- Exercise 3: Function for Computing Odd-Index Vector
- Exercise 4: Primality Test
- Exercise 5: Function for Root Finding

## 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