{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Unit 4: Basic Control Structures and Functions\n",
"\n",
"\n",
" - Overview and Learning Objectives
\n",
" - Basic Control Structures
\n",
" - Python Functions
\n",
" - Efficiency and Runtime
\n",
" - Exercise 1: Function
give_me_a_number
\n",
" - Exercise 2: Function for Computing Row Mean
\n",
" - Exercise 3: Function for Computing Odd-Index Vector
\n",
" - Exercise 4: Primality Test
\n",
" - Exercise 5: Function for Root Finding
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" \n",
"\n",
"
Overview and Learning Objectives
\n",
"\n",
"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).\n",
" \n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Basic Control Structures\n",
"\n",
"In Python, there are basic control structures similar to most other programming languages. The most important control structures are:\n",
"\n",
"-
if
: conditionally execute statements\n",
" -
for
: repeat statements a specific number of times\n",
" -
while
: repeat statements an indefinite number of times\n",
" -
break
: terminate execution of a while
or for
loop\n",
" -
continue
: continue execution of a while
or for
loop at top\n",
"
\n",
"\n",
"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:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = -2\n",
"if n < 0:\n",
" print('Negative')\n",
"elif n > 0:\n",
" print('Positive') \n",
"else:\n",
" print('Zero')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(3):\n",
" print(i, end='-')\n",
"print()\n",
" \n",
"for i in ['a', 2, 'c', 'def']:\n",
" print(i, end='-')\n",
"print()\n",
"\n",
"for i in 'example':\n",
" print(i, end='-')\n",
"print()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A `while`-loop is written as follows:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 0\n",
"while a < 5:\n",
" print(a, end='-')\n",
" a += 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for k in 'abcd':\n",
" if k == 'c':\n",
" break\n",
" for i in '12345':\n",
" if i == '4':\n",
" break\n",
" print(k + i, end='-')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `continue`-statement is used to terminate only the current step of the loop. The loop then continues with the next iteration."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for k in 'abcd':\n",
" if k == 'c':\n",
" continue\n",
" for i in '12345':\n",
" if i == '4':\n",
" continue\n",
" print(k + i, end='-')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Python Functions\n",
"\n",
"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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def add(a, b=0, c=0):\n",
" \"\"\"Function to add three numbers\n",
"\n",
" Notebook: PCP_04_control.ipynb\n",
"\n",
" Args:\n",
" a: first number\n",
" b: second number (Default value = 0)\n",
" c: third number (Default value = 0)\n",
"\n",
" Returns:\n",
" Sum of a, b and c\n",
" \"\"\"\n",
" print('Addition: ', a, ' + ', b, ' + ', c)\n",
" return a + b + c\n",
"\n",
"print(add(5))\n",
"print(add(5, 2, 1))\n",
"print(add(5, c=4))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are some rules and differences on how to use arguments without and with default values. \n",
"\n",
"* All non-default arguments must be specified in the function call.\n",
"* The order of default arguments may not be changed in the call.\n",
"* The default arguments are optional in a call. If a value is provided, the default value is overwritten.\n",
"* A function may have any number of default arguments. However, a default argument may not be followed by a non-default argument. \n",
"\n",
"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):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def add_and_diff(a, b=0):\n",
" \"\"\"Function to add and subtract two numbers\n",
"\n",
" Notebook: PCP_04_control.ipynb\n",
"\n",
" Args:\n",
" a: first number\n",
" b: second number (Default value = 0)\n",
"\n",
" Returns:\n",
" first: a + b\n",
" second: a - b\n",
" \"\"\"\n",
" return a + b, a - b\n",
"\n",
"x = add_and_diff(3, 5)\n",
"print('result:', x, type(x))\n",
"x, y = add_and_diff(3, 5)\n",
"print('result:', x, y, type(x), type(y))\n",
"x, y = add_and_diff(3.0, 5)\n",
"print('result:', x, y, type(x), type(y))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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](https://www.python.org/dev/peps/pep-0257/), 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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"help(add)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" \n",
"## Efficiency and Runtime\n",
"\n",
"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$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def sum_n(n):\n",
" \"\"\"Function that sums up the integers from 1 to n\n",
"\n",
" Notebook: PCP_04_control.ipynb\n",
"\n",
" Args:\n",
" n: Integer number\n",
"\n",
" Returns:\n",
" s: Sum of integers from 1 to n\n",
" \"\"\"\n",
" s = 0\n",
" for n in range(1, n+1):\n",
" s = s + n\n",
" return s\n",
"\n",
"n = 1\n",
"while sum_n(n) <= 100:\n",
" print(f'n= {n}, s={sum_n(n)}')\n",
" n += 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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
](https://docs.python.org/2/library/timeit.html), 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
](https://docs.python.org/3/library/time.html).\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"def sum_n_numpy(n):\n",
" \"\"\"Function that sums up the integers from 1 to n using numpy\n",
"\n",
" Notebook: PCP_04_control.ipynb\n",
"\n",
" Args:\n",
" n: Integer number\n",
"\n",
" Returns:\n",
" s: Sum of integers from 1 to n\n",
" \"\"\"\n",
" s = np.sum(np.arange(1, n+1))\n",
" return s \n",
"\n",
"def sum_n_math(n):\n",
" \"\"\"Function that sums up the integers from 1 to n using the idea by Gauss\n",
"\n",
" Notebook: PCP_04_control.ipynb\n",
"\n",
" Args:\n",
" n: Integer number\n",
"\n",
" Returns:\n",
" s: Sum of integers from 1 to n\n",
" \"\"\"\n",
" s = n * (n + 1) // 2\n",
" return s \n",
"\n",
"n = 1000\n",
"print(f'Computation with sum_n: n={n}, s={sum_n(n)}')\n",
"print(f'Computation with sum_n_numpy: n={n}, s={sum_n_numpy(n)}')\n",
"print(f'Computation with sum_n_math: n={n}, s={sum_n_math(n)}')\n",
"\n",
"# Measuring runtime of different implementations \n",
"import timeit\n",
"executions = 100\n",
"n = 10000\n",
"runtime_av = timeit.timeit(lambda: sum_n(n), number=executions) / executions\n",
"print(f'Runtime for sum_n: {runtime_av * 1000:.6f} ms')\n",
"\n",
"runtime_av = timeit.timeit(lambda: sum_n_numpy(n), number=executions) / executions\n",
"print(f'Runtime for sum_n_numpy: {runtime_av * 1000:.6f} ms')\n",
"\n",
"runtime_av = timeit.timeit(lambda: sum_n_math(n), number=executions) / executions\n",
"print(f'Runtime for sum_n_math: {runtime_av * 1000:.6f} ms')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
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.\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercises and Results"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import libpcp.control\n",
"show_result = True"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"Exercise 1: Function give_me_a_number
\n",
"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'
.\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#\n",
"# Your Solution\n",
"#"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"libpcp.control.exercise_give_number(show_result=show_result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"Exercise 2: Function for Computing Row Mean
\n",
"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}$.\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#\n",
"# Your Solution\n",
"#"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"libpcp.control.exercise_row_mean(show_result=show_result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"Exercise 3: Function for Computing Odd-Index Vector
\n",
"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
.
\n",
"Note: Recall that Python indexing starts with index 0
(which is an even index).\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#\n",
"# Your Solution\n",
"#"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"libpcp.control.exercise_odd(show_result=show_result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Exercise 4: Primality Test\n",
"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. \n",
"
\n",
"- Test your function for $n=1$, $n=17$, $n=1221$, and $n=1223$.
\n",
"- Use this function to output the first $20$ prime numbers.
\n",
"- Discuss efficiency issues. Is there a more efficient way to compute the first $20$ prime numbers?
\n",
"- Have a look at the algorithm Sieve of Eratosthenes, which is an ancient algorithm for finding all prime numbers up to any given limit.
\n",
"
\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#\n",
"# Your Solution\n",
"#"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"libpcp.control.exercise_isprime(show_result=show_result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"
Exercise 5: Function for Root Finding\n",
"Let $f:\\mathbb{R}\\to\\mathbb{R}$ be a continuous function and let $a,b\\in\\mathbb{R}$ be two numbers such that $a
root 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: \n",
"\n",
"- 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.
\n",
"- 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]$.
\n",
"- 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.
\n",
"
\n",
" \n",
"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
). \n",
"\n",
"\n",
"- 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
.) \n",
"- Test
search_root
for the same function when using a=2
and b=4
. \n",
"- Test
search_root
for the same function when using a=4
and b=2
. \n",
"- Evaluate
search_root
for f
being np.sin
using a=3
and b=4
. \n",
"
\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
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. \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#\n",
"# Your Solution\n",
"#"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"libpcp.control.exercise_root(show_result=show_result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
\n",
"
"
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.17"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 1
}