{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "-"
}
},
"source": [
"# MTH5001 Introduction to Computer Programming - Lecture 6b\n",
"Module organisers Dr. Lennart Dabelow and Prof. Thomas Prellberg"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will now use the loops we introduced in the last lecture to work on sequence constructions."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Comparing Sequence Constructions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have now introduced several constructions that allow us to create sequences. Let's first recap three ways we used earlier when we discussed iterables, namely (i) specifying elements directly, (ii) using ranges, and (ii) using list comprehension."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[5, 11, 17, 23, 29, 35]\n",
"[5, 11, 17, 23, 29, 35]\n",
"[5, 11, 17, 23, 29, 35]\n"
]
}
],
"source": [
"print([5,11,17,23,29,35])\n",
"print(list(range(5,36,6)))\n",
"print([5+6*n for n in range (6)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Specifying the elements directly is something we can always do (assuming we know the items explicitly). Ranges are useful for integer data that is evenly spaced, and list comprehension can be used when we know a formula for the $n$-th item. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we saw in the last lecture, instead of a list comprehension we can use a for loop that appends items sequentially. To do so, you need to create an empty list before you start the loop (so you have something to append to), and then in the loop repeatedly compute the next list item and append it to your list."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[5, 11, 17, 23, 29, 35]\n"
]
}
],
"source": [
"my_list=[]\n",
"for n in range(6):\n",
" new_item=5+6*n\n",
" my_list.append(new_item)\n",
"print(my_list)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we also saw in the last lecture, this can be written using a while loop, too."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[5, 11, 17, 23, 29, 35]\n"
]
}
],
"source": [
"my_list=[]\n",
"n=0\n",
"while n<6:\n",
" new_item=5+6*n\n",
" my_list.append(new_item)\n",
" n=n+1\n",
"print(my_list)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that if you can write a sequence using list comprehension instead of using loops, you should choose to do this. It is the most efficient way."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Recursive Sequences"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For loops and while loops are very useful when we don't know an explicit formula but can compute new items in the sequence from the previous one. Such a sequence is called a recursive sequence."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The items $x_n=5+6n$ in the above example also satisfy the recursion $$x_n=x_{n-1}+6\\;.$$ This recursion can be used in a for or while loop to compute the next list item, once we know the initial item."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[5, 11, 17, 23, 29, 35]\n"
]
}
],
"source": [
"my_list=[5]\n",
"for n in range(1,6):\n",
" new_item=my_list[-1]+6\n",
" my_list.append(new_item)\n",
"print(my_list)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that Python makes it very easy to refer to the last entry of our list as `mylist[-1]` using the convention of negative indices. Alternatively, we could have written `mylist[len(mylist)-1]`, or in this case also `mylist[n-1]` as the length of the list in this particular loop is `n`. \n",
"\n",
"(Please remember that using negative indices was covered in Week 2.)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[5, 11, 17, 23, 29, 35]\n"
]
}
],
"source": [
"my_list=[5]\n",
"n=1\n",
"while n<6:\n",
" new_item=5+6*n\n",
" my_list.append(new_item)\n",
" n=n+1\n",
"print(my_list)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us look at a slightly more complicated example: the Fibonacci numbers $1,1,2,3,5,8,13,21,34,55,\\ldots$ are recursively defined by $x_0=1$, $x_1=1$, and\n",
"$$x_n=x_{n-1}+x_{n-2}\\text{ for $n>1$.}$$\n",
"\n",
"While there is an explicit formula for the $n$-th Fibonacci number involving powers of the golden ratio, the recursive description, where the next term depends on the two previous ones, is again easy to code using the `for` loop together with `append`. The structure of the for loop is precisely as above, except that we need two starting values."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]\n"
]
}
],
"source": [
"fibonacci_numbers=[1,1]\n",
"for n in range(2,15):\n",
" next_fibonacci=fibonacci_numbers[-1]+fibonacci_numbers[-2]\n",
" fibonacci_numbers.append(next_fibonacci)\n",
"print(fibonacci_numbers)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If you paid attention last week, you will already have realised that I could also have formulated the Fibonacci number computation as a recursive function:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def fibonacci(n):\n",
" if n<=1:\n",
" f=1\n",
" else:\n",
" f=fibonacci(n-1)+fibonacci(n-2)\n",
" return f\n",
"\n",
"[fibonacci(n) for n in range(15)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Which of the two versions is more efficient?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Computing Sums"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's assume we want to numerically evaluate $$\\frac1e=\\sum\\limits_{n=0}^\\infty\\frac{(-1)^n}{n!}\\;.$$\n",
"\n",
"To start with, we need to a define function compute the factorial of $n$. A few weeks ago, we used for this the black-box function `math.factorial`, and in the last lecture we used a recursive function. Here we implement the recursive description $n!=n\\cdot(n-1)!$ with a for loop."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 24 3628800\n"
]
}
],
"source": [
"def factorial(N):\n",
" '''Compute N! = 1*2*...*(N-1)*N'''\n",
" product=1\n",
" for n in range(1,N+1):\n",
" product=n*product\n",
" return product\n",
"\n",
"print(factorial(1),factorial(4),factorial(10))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(Alternatively, we could also have used `np.prod(range(1,N+1))`. There are usually different ways to write code for the same problem.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we want to compute $1/e$ by approximating the infinite sum by finite partial sums\n",
"$$\\sum_{n=0}^N\\frac{(-1)^n}{n!}\\;.$$\n",
"We can of course do it by summing up a list of coefficients generated by list comprehension via\n",
"```python\n",
"sum([(-1)**n/factorial(n) for n in range(N+1)])\n",
"```\n",
"but we want to practice writing loops, so let's do the summation with a while loop."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.3678794642857144\n"
]
}
],
"source": [
"def euler(N):\n",
" summation=0\n",
" n=0\n",
" while n<=N:\n",
" summation=summation+(-1)**n/factorial(n)\n",
" n=n+1\n",
" return(summation)\n",
"\n",
"print(euler(10))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"But how good is this approximation? How large do we need to choose $N$? Fortunately, for alternating sums we have the [Leibniz criterion](http://en.wikipedia.org/wiki/Alternating_series_test) stating that if the absolute value of the summands strictly decreases to zero then the error is smaller than the absolute value of the first omitted term.\n",
"\n",
"We can therefore conclude that $$\\left|\\sum_{n=0}^N\\frac{(-1)^n}{n!}-\\frac1e\\right|<\\frac1{(N+1)!}\\;.$$ This means that if we want to compute $1/e$ up to some accuracy, we need to keep summing terms *while* these are greater than this accuracy, which is perfect for a using a while loop."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.3678819444444445\n"
]
}
],
"source": [
"def euler2(accuracy):\n",
" summation=0\n",
" n=0\n",
" while 1/factorial(n)>accuracy:\n",
" summation=summation+(-1)**n/factorial(n)\n",
" n=n+1\n",
" return(summation)\n",
"\n",
"print(euler2(1e-5))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You see that the only part of the code that has changed is the logical condition after the `while`. \n",
"\n",
"Does this work as we want? Let's compare the actual error with the given accuracy:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"accuracy: 1e-06\n",
"computed: 0.3678791887125221 error: 2.5245892021352745e-07\n",
"\n",
"accuracy: 1e-09\n",
"computed: 0.3678794413212817 error: 1.498393631393924e-10\n",
"\n",
"accuracy: 1e-12\n",
"computed: 0.36787944117216204 error: 7.197020757132577e-13\n",
"\n",
" 1/e = 0.36787944117144233\n"
]
}
],
"source": [
"import numpy as np\n",
"\n",
"def pretty_print(accuracy, compute, actual):\n",
" print('accuracy:', accuracy)\n",
" print('computed:', compute(accuracy),\\\n",
" 'error:', abs(compute(accuracy)-actual))\n",
" print()\n",
"\n",
"pretty_print(1e-6,euler2,np.exp(-1))\n",
"pretty_print(1e-9,euler2,np.exp(-1))\n",
"pretty_print(1e-12,euler2,np.exp(-1))\n",
"print(' 1/e =',np.exp(-1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that indeed the error is less than the given accuracy."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### The danger of infinite while loops"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When using while loops, it is important to make sure that the logical condition in the while loop will eventially become false, otherwise your loop will run forever. When this happens you will keep seeing an asterisk in `In[*]` and you need to stop Python by interrupting the kernel by hand (as explained last week)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's assume we tried to compute Euler's constant up to machine precision, i.e. as long as the evaluation of 1/n! was indistinguishable from `0.0`:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.36787944117144245\n",
"1/e = 0.36787944117144233\n"
]
}
],
"source": [
"def euler3():\n",
" summation=0\n",
" n=0\n",
" while 1/factorial(n)>0:\n",
" summation=summation+(-1)**n/factorial(n)\n",
" n=n+1\n",
" return(summation)\n",
"\n",
"print(euler3())\n",
"print('1/e =',np.exp(-1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are some expected rounding errors, but this works reasonably well. But now assume we had a minor mistake in the code:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[16], line 9\u001b[0m\n\u001b[1;32m 6\u001b[0m n\u001b[38;5;241m=\u001b[39mn\u001b[38;5;241m+\u001b[39m\u001b[38;5;241m1\u001b[39m\n\u001b[1;32m 7\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m(summation)\n\u001b[0;32m----> 9\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43meuler4\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m)\n\u001b[1;32m 10\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124m'\u001b[39m\u001b[38;5;124m1/e =\u001b[39m\u001b[38;5;124m'\u001b[39m,np\u001b[38;5;241m.\u001b[39mexp(\u001b[38;5;241m-\u001b[39m\u001b[38;5;241m1\u001b[39m))\n",
"Cell \u001b[0;32mIn[16], line 4\u001b[0m, in \u001b[0;36meuler4\u001b[0;34m()\u001b[0m\n\u001b[1;32m 2\u001b[0m summation\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m0\u001b[39m\n\u001b[1;32m 3\u001b[0m n\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m0\u001b[39m\n\u001b[0;32m----> 4\u001b[0m \u001b[38;5;28;01mwhile\u001b[39;00m \u001b[38;5;241m1\u001b[39m\u001b[38;5;241m/\u001b[39m\u001b[43mfactorial\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241m>\u001b[39m\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m0\u001b[39m:\n\u001b[1;32m 5\u001b[0m summation\u001b[38;5;241m=\u001b[39msummation\u001b[38;5;241m+\u001b[39m(\u001b[38;5;241m-\u001b[39m\u001b[38;5;241m1\u001b[39m)\u001b[38;5;241m*\u001b[39m\u001b[38;5;241m*\u001b[39mn\u001b[38;5;241m/\u001b[39mfactorial(n)\n\u001b[1;32m 6\u001b[0m n\u001b[38;5;241m=\u001b[39mn\u001b[38;5;241m+\u001b[39m\u001b[38;5;241m1\u001b[39m\n",
"Cell \u001b[0;32mIn[9], line 5\u001b[0m, in \u001b[0;36mfactorial\u001b[0;34m(N)\u001b[0m\n\u001b[1;32m 3\u001b[0m product\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m1\u001b[39m\n\u001b[1;32m 4\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m n \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m1\u001b[39m,N\u001b[38;5;241m+\u001b[39m\u001b[38;5;241m1\u001b[39m):\n\u001b[0;32m----> 5\u001b[0m product\u001b[38;5;241m=\u001b[39m\u001b[43mn\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mproduct\u001b[49m\n\u001b[1;32m 6\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m product\n",
"\u001b[0;31mKeyboardInterrupt\u001b[0m: "
]
}
],
"source": [
"def euler4():\n",
" summation=0\n",
" n=0\n",
" while 1/factorial(n)>=0:\n",
" summation=summation+(-1)**n/factorial(n)\n",
" n=n+1\n",
" return(summation)\n",
"\n",
"print(euler4())\n",
"print('1/e =',np.exp(-1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Nothing happens, and we have to interrupt by hand. Did you find the mistake? "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Conclusion and Outlook"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this lecture we have introduced loops and used them for the creation of lists and numerical evaluation of sums. After the midterm we shall continue with applications."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.12.0"
}
},
"nbformat": 4,
"nbformat_minor": 4
}