alexander/intro-to-python
1
1
Fork 0
Code Issues Pull requests Releases Activity
intro-to-python/04_iteration/00_content.ipynb

4919 lines
122 KiB
Text
Raw Permalink Blame History

{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"**Note**: Click on \"*Kernel*\" > \"*Restart Kernel and Clear All Outputs*\" in [JupyterLab](https://jupyterlab.readthedocs.io/en/stable/) *before* reading this notebook to reset its output. If you cannot run this file on your machine, you may want to open it [in the cloud <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_mb.png\">](https://mybinder.org/v2/gh/webartifex/intro-to-python/develop?urlpath=lab/tree/04_iteration/00_content.ipynb)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Chapter 4: Recursion & Looping"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"While controlling the flow of execution with an `if` statement is a must-have building block in any programming language, it alone does not allow us to run a block of code repetitively, and we need to be able to do precisely that to write useful software.\n",
"\n",
"The `for` statement shown in some examples before might be the missing piece in the puzzle. However, we can live without it and postpone its official introduction until the second half of this chapter.\n",
"\n",
"Instead, we dive into the big idea of **iteration** by studying the concept of **recursion** first. This order is opposite to many other introductory books that only treat the latter as a nice-to-have artifact, if at all. Yet, understanding recursion sharpens one's mind and contributes to seeing problems from a different angle."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Recursion"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A popular joke among programmers by an unknown author goes like this (cf., [discussion](https://www.quora.com/What-does-the-phrase-in-order-to-understand-recursion-you-must-first-understand-recursion-mean-to-you)):"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"> \"In order to understand **recursion**, you must first understand **recursion**.\""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A function that calls itself is **recursive**, and the process of executing such a function is called **recursion**.\n",
"\n",
"Recursive functions contain some form of a conditional check (e.g., `if` statement) to identify a **base case** that ends the recursion *when* reached. Otherwise, the function would keep calling itself forever.\n",
"\n",
"The meaning of the word *recursive* is similar to *circular*. However, a truly circular definition is not very helpful, and we think of a recursive function as kind of a \"circular function with a way out at the end.\""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### Trivial Example: Countdown"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A rather trivial toy example illustrates the important aspects concretely: If called with any positive integer as its `n` argument, `countdown()` just prints that number and calls itself with the *new* `n` being the *old* `n` minus `1`. This continues until `countdown()` is called with `n=0`. Then, the flow of execution hits the base case, and the function calls stop."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"code_folding": [],
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def countdown(n):\n",
" \"\"\"Print a countdown until the party starts.\n",
"\n",
" Args:\n",
" n (int): seconds until the party begins\n",
" \"\"\"\n",
" if n == 0:\n",
" print(\"Happy New Year!\")\n",
" else:\n",
" print(n)\n",
" countdown(n - 1)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3\n",
"2\n",
"1\n",
"Happy New Year!\n"
]
}
],
"source": [
"countdown(3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"As trivial as this seems, a lot of complexity is hidden in this implementation. In particular, the order in which objects are created and de-referenced in memory might not be apparent right away as [PythonTutor <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](http://pythontutor.com/visualize.html#code=def%20countdown%28n%29%3A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20print%28%22Happy%20new%20Year!%22%29%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20print%28n%29%0A%20%20%20%20%20%20%20%20countdown%28n%20-%201%29%0A%0Acountdown%283%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false) shows: Each time `countdown()` is called, Python creates a *new* frame in the part of the memory where it manages all the names. This way, Python *isolates* all the different `n` variables from each other. As new frames are created until we reach the base case, after which the frames are destroyed in the *reversed* order, this is called a **[stack <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Stack_(abstract_data_type))** of frames in computer science terminology. In simple words, a stack is a last-in-first-out (LIFO) task queue. Each frame has a single parent frame, namely the one whose recursive function call created it."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Recursion in Mathematics"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Recursion plays a vital role in mathematics as well, and we likely know about it from some introductory course, for example, in [combinatorics <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Combinatorics)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### Easy Example: [Factorial <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Factorial)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The factorial function, denoted with the $!$ symbol, is defined as follows for all non-negative integers:"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"$$0! = 1$$\n",
"$$n! = n*(n-1)!$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Whenever we find a recursive way of formulating an idea, we can immediately translate it into Python in a *naive* way (i.e., we create a *correct* program that may *not* be an *efficient* implementation yet).\n",
"\n",
"Below is a first version of `factorial()`: The `return` statement does not have to be a function's last code line, and we may indeed have several `return` statements as well."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"code_folding": [],
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def factorial(n):\n",
" \"\"\"Calculate the factorial of a number.\n",
"\n",
" Args:\n",
" n (int): number to calculate the factorial for\n",
"\n",
" Returns:\n",
" factorial (int)\n",
" \"\"\"\n",
" if n == 0:\n",
" return 1\n",
" else:\n",
" recurse = factorial(n - 1)\n",
" result = n * recurse\n",
" return result"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"When we read such code, it is often easier not to follow every function call (i.e., `factorial(n - 1)` here) in one's mind but assume we receive a return value as specified in the documentation. Some call this approach a **[leap of faith](http://greenteapress.com/thinkpython2/html/thinkpython2007.html#sec75)**. We practice this already whenever we call built-in functions (e.g., [print() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#print) or [len() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#len)) where we would have to read C code in many cases.\n",
"\n",
"To visualize *all* the computational steps of the exemplary `factorial(3)`, we use [PythonTutor <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](http://pythontutor.com/visualize.html#code=def%20factorial%28n%29%3A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20recurse%20%3D%20factorial%28n%20-%201%29%0A%20%20%20%20%20%20%20%20result%20%3D%20n%20*%20recurse%0A%20%20%20%20%20%20%20%20return%20result%0A%0Asolution%20%3D%20factorial%283%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false): The recursion again creates a stack of frames in memory. In contrast to the previous trivial example, each frame leaves a return value in memory after it is destroyed. This return value is then assigned to the `recurse` variable within the parent frame and used to compute `result`."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3628800"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(10)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A Pythonista would formulate `factorial()` in a more concise way using the so-called **early exit** pattern: No `else`-clause is needed as reaching a `return` statement ends a function call *immediately*. Furthermore, we do not need the temporary variables `recurse` and `result`.\n",
"\n",
"As [PythonTutor <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](http://pythontutor.com/visualize.html#code=def%20factorial%28n%29%3A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20return%20n%20*%20factorial%28n%20-%201%29%0A%0Asolution%20%3D%20factorial%283%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false) shows, this implementation is more efficient as it only requires 18 computational steps instead of 24 to calculate `factorial(3)`, an improvement of 25 percent! "
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def factorial(n):\n",
" \"\"\"Calculate the factorial of a number.\n",
"\n",
" Args:\n",
" n (int): number to calculate the factorial for\n",
"\n",
" Returns:\n",
" factorial (int)\n",
" \"\"\"\n",
" if n == 0:\n",
" return 1\n",
" return n * factorial(n - 1)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3628800"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(10)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Note that the [math <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/math.html) module in the [standard library <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/index.html) provides a [factorial() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/math.html#math.factorial) function as well, and we should, therefore, *never* implement it ourselves in a real codebase."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import math"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on built-in function factorial in module math:\n",
"\n",
"factorial(x, /)\n",
" Find x!.\n",
" \n",
" Raise a ValueError if x is negative or non-integral.\n",
"\n"
]
}
],
"source": [
"help(math.factorial)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.factorial(3)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3628800"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.factorial(10)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### \"Involved\" Example: [Euclid's Algorithm <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Euclidean_algorithm)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"As famous philosopher Euclid already shows in his \"Elements\" (ca. 300 BC), the greatest common divisor of two integers, i.e., the largest number that divides both integers without a remainder, can be efficiently computed with the following code. This example illustrates that a recursive solution to a problem is not always easy to understand."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def gcd(a, b):\n",
" \"\"\"Calculate the greatest common divisor of two numbers.\n",
"\n",
" Args:\n",
" a (int): first number\n",
" b (int): second number\n",
"\n",
" Returns:\n",
" gcd (int)\n",
" \"\"\"\n",
" if b == 0:\n",
" return a \n",
" return gcd(b, a % b)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gcd(12, 4)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Euclid's algorithm is stunningly fast, even for large numbers. Its speed comes from the use of the modulo operator `%`. However, this is *not* true for recursion in general, which may result in slow programs if not applied correctly."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gcd(112233445566778899, 987654321)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"As expected, for two [prime numbers <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/List_of_prime_numbers) the greatest common divisor is of course $1$."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gcd(7, 7919)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The [math <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/math.html) module in the [standard library <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/index.html) provides a [gcd() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/math.html#math.gcd) function as well, and, therefore, we should again *never* implement it on our own."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on built-in function gcd in module math:\n",
"\n",
"gcd(x, y, /)\n",
" greatest common divisor of x and y\n",
"\n"
]
}
],
"source": [
"help(math.gcd)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.gcd(12, 4)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.gcd(112233445566778899, 987654321)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.gcd(7, 7919)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### \"Easy at first Glance\" Example: [Fibonacci Numbers <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Fibonacci_number)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The Fibonacci numbers are an infinite sequence of non-negative integers that are calculated such that every number is the sum of its two predecessors where the first two numbers of the sequence are defined to be $0$ and $1$. For example, the first 13 numbers are:"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Let's write a function `fibonacci()` that calculates the $i$th Fibonacci number where $0$ is the $0$th number. Looking at the numbers in a **backward** fashion (i.e., from right to left), we realize that the return value for `fibonacci(i)` can be reduced to the sum of the return values for `fibonacci(i - 1)` and `fibonacci(i - 2)` disregarding the *two* base cases."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def fibonacci(i):\n",
" \"\"\"Calculate the ith Fibonacci number.\n",
"\n",
" Args:\n",
" i (int): index of the Fibonacci number to calculate\n",
"\n",
" Returns:\n",
" ith_fibonacci (int)\n",
" \"\"\"\n",
" if i == 0:\n",
" return 0\n",
" elif i == 1:\n",
" return 1\n",
" return fibonacci(i - 1) + fibonacci(i - 2)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"144"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fibonacci(12) # = 13th number"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"#### Efficiency of Algorithms"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"This implementation is *highly* **inefficient** as small Fibonacci numbers already take a very long time to compute. The reason for this is **exponential growth** in the number of function calls. As [PythonTutor <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](http://pythontutor.com/visualize.html#code=def%20fibonacci%28i%29%3A%0A%20%20%20%20if%20i%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%200%0A%20%20%20%20elif%20i%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20return%20fibonacci%28i%20-%201%29%20%2B%20fibonacci%28i%20-%202%29%0A%0Arv%20%3D%20fibonacci%285%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false) shows, `fibonacci()` is called again and again with the same `i` arguments.\n",
"\n",
"To understand this in detail, we have to study algorithms and data structures (e.g., with [this book](https://www.amazon.de/Introduction-Algorithms-Press-Thomas-Cormen/dp/0262033844/ref=sr_1_1?__mk_de_DE=%C3%85M%C3%85%C5%BD%C3%95%C3%91&crid=1JNE8U0VZGU0O&qid=1569837169&s=gateway&sprefix=algorithms+an%2Caps%2C180&sr=8-1)), a discipline within computer science, and dive into the analysis of **[time complexity of algorithms <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Time_complexity)**.\n",
"\n",
"Luckily, in the Fibonacci case, the inefficiency can be resolved with a **caching** (i.e., \"reuse\") strategy from the field of **[dynamic programming <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Dynamic_programming)**, namely **[memoization <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Memoization)**. We do so in [Chapter 9 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/develop/09_mappings/02_content.ipynb#Memoization), after introducing the `dict` data type.\n",
"\n",
"Let's measure the average run times for `fibonacci()` and varying `i` arguments with the `%%timeit` [cell magic](https://ipython.readthedocs.io/en/stable/interactive/magics.html#magic-timeit) that comes with Jupyter."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"38.9 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit -n 100\n",
"fibonacci(12)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"12.2 ms ± 77.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit -n 100\n",
"fibonacci(24)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.89 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
]
}
],
"source": [
"%%timeit -n 1 -r 1\n",
"fibonacci(36)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"6.28 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
]
}
],
"source": [
"%%timeit -n 1 -r 1\n",
"fibonacci(37)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Infinite Recursion"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"If a recursion does not reach its base case, it theoretically runs forever. Luckily, Python detects that and saves the computer from crashing by raising a `RecursionError`.\n",
"\n",
"The simplest possible infinite recursion is generated like so."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def run_forever():\n",
" \"\"\"Also a pointless function should have a docstring.\"\"\"\n",
" run_forever()"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"ename": "RecursionError",
"evalue": "maximum recursion depth exceeded",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-28-62f686a9f8a1>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mrun_forever\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-27-80575699c62c>\u001b[0m in \u001b[0;36mrun_forever\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mrun_forever\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"\"\"Also a pointless function should have a docstring.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mrun_forever\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"... last 1 frames repeated, from the frame below ...\n",
"\u001b[0;32m<ipython-input-27-80575699c62c>\u001b[0m in \u001b[0;36mrun_forever\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mrun_forever\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\"\"\"Also a pointless function should have a docstring.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mrun_forever\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
]
}
],
"source": [
"run_forever()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"However, even the trivial `countdown()` function from above is not immune to infinite recursion. Let's call it with `3.1` instead of `3`. What goes wrong here?"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.1\n",
"2.1\n",
"1.1\n",
"0.10000000000000009\n",
"-0.8999999999999999\n",
"-1.9\n",
"-2.9\n",
"-3.9\n",
"-4.9\n",
"-5.9\n",
"-6.9\n",
"-7.9\n",
"-8.9\n",
"-9.9\n",
"-10.9\n",
"-11.9\n",
"-12.9\n",
"-13.9\n",
"-14.9\n",
"-15.9\n",
"-16.9\n",
"-17.9\n",
"-18.9\n",
"-19.9\n",
"-20.9\n",
"-21.9\n",
"-22.9\n",
"-23.9\n",
"-24.9\n",
"-25.9\n",
"-26.9\n",
"-27.9\n",
"-28.9\n",
"-29.9\n",
"-30.9\n",
"-31.9\n",
"-32.9\n",
"-33.9\n",
"-34.9\n",
"-35.9\n",
"-36.9\n",
"-37.9\n",
"-38.9\n",
"-39.9\n",
"-40.9\n",
"-41.9\n",
"-42.9\n",
"-43.9\n",
"-44.9\n",
"-45.9\n",
"-46.9\n",
"-47.9\n",
"-48.9\n",
"-49.9\n",
"-50.9\n",
"-51.9\n",
"-52.9\n",
"-53.9\n",
"-54.9\n",
"-55.9\n",
"-56.9\n",
"-57.9\n",
"-58.9\n",
"-59.9\n",
"-60.9\n",
"-61.9\n",
"-62.9\n",
"-63.9\n",
"-64.9\n",
"-65.9\n",
"-66.9\n",
"-67.9\n",
"-68.9\n",
"-69.9\n",
"-70.9\n",
"-71.9\n",
"-72.9\n",
"-73.9\n",
"-74.9\n",
"-75.9\n",
"-76.9\n",
"-77.9\n",
"-78.9\n",
"-79.9\n",
"-80.9\n",
"-81.9\n",
"-82.9\n",
"-83.9\n",
"-84.9\n",
"-85.9\n",
"-86.9\n",
"-87.9\n",
"-88.9\n",
"-89.9\n",
"-90.9\n",
"-91.9\n",
"-92.9\n",
"-93.9\n",
"-94.9\n",
"-95.9\n",
"-96.9\n",
"-97.9\n",
"-98.9\n",
"-99.9\n",
"-100.9\n",
"-101.9\n",
"-102.9\n",
"-103.9\n",
"-104.9\n",
"-105.9\n",
"-106.9\n",
"-107.9\n",
"-108.9\n",
"-109.9\n",
"-110.9\n",
"-111.9\n",
"-112.9\n",
"-113.9\n",
"-114.9\n",
"-115.9\n",
"-116.9\n",
"-117.9\n",
"-118.9\n",
"-119.9\n",
"-120.9\n",
"-121.9\n",
"-122.9\n",
"-123.9\n",
"-124.9\n",
"-125.9\n",
"-126.9\n",
"-127.9\n",
"-128.9\n",
"-129.9\n",
"-130.9\n",
"-131.9\n",
"-132.9\n",
"-133.9\n",
"-134.9\n",
"-135.9\n",
"-136.9\n",
"-137.9\n",
"-138.9\n",
"-139.9\n",
"-140.9\n",
"-141.9\n",
"-142.9\n",
"-143.9\n",
"-144.9\n",
"-145.9\n",
"-146.9\n",
"-147.9\n",
"-148.9\n",
"-149.9\n",
"-150.9\n",
"-151.9\n",
"-152.9\n",
"-153.9\n",
"-154.9\n",
"-155.9\n",
"-156.9\n",
"-157.9\n",
"-158.9\n",
"-159.9\n",
"-160.9\n",
"-161.9\n",
"-162.9\n",
"-163.9\n",
"-164.9\n",
"-165.9\n",
"-166.9\n",
"-167.9\n",
"-168.9\n",
"-169.9\n",
"-170.9\n",
"-171.9\n",
"-172.9\n",
"-173.9\n",
"-174.9\n",
"-175.9\n",
"-176.9\n",
"-177.9\n",
"-178.9\n",
"-179.9\n",
"-180.9\n",
"-181.9\n",
"-182.9\n",
"-183.9\n",
"-184.9\n",
"-185.9\n",
"-186.9\n",
"-187.9\n",
"-188.9\n",
"-189.9\n",
"-190.9\n",
"-191.9\n",
"-192.9\n",
"-193.9\n",
"-194.9\n",
"-195.9\n",
"-196.9\n",
"-197.9\n",
"-198.9\n",
"-199.9\n",
"-200.9\n",
"-201.9\n",
"-202.9\n",
"-203.9\n",
"-204.9\n",
"-205.9\n",
"-206.9\n",
"-207.9\n",
"-208.9\n",
"-209.9\n",
"-210.9\n",
"-211.9\n",
"-212.9\n",
"-213.9\n",
"-214.9\n",
"-215.9\n",
"-216.9\n",
"-217.9\n",
"-218.9\n",
"-219.9\n",
"-220.9\n",
"-221.9\n",
"-222.9\n",
"-223.9\n",
"-224.9\n",
"-225.9\n",
"-226.9\n",
"-227.9\n",
"-228.9\n",
"-229.9\n",
"-230.9\n",
"-231.9\n",
"-232.9\n",
"-233.9\n",
"-234.9\n",
"-235.9\n",
"-236.9\n",
"-237.9\n",
"-238.9\n",
"-239.9\n",
"-240.9\n",
"-241.9\n",
"-242.9\n",
"-243.9\n",
"-244.9\n",
"-245.9\n",
"-246.9\n",
"-247.9\n",
"-248.9\n",
"-249.9\n",
"-250.9\n",
"-251.9\n",
"-252.9\n",
"-253.9\n",
"-254.9\n",
"-255.9\n",
"-256.9\n",
"-257.9\n",
"-258.9\n",
"-259.9\n",
"-260.9\n",
"-261.9\n",
"-262.9\n",
"-263.9\n",
"-264.9\n",
"-265.9\n",
"-266.9\n",
"-267.9\n",
"-268.9\n",
"-269.9\n",
"-270.9\n",
"-271.9\n",
"-272.9\n",
"-273.9\n",
"-274.9\n",
"-275.9\n",
"-276.9\n",
"-277.9\n",
"-278.9\n",
"-279.9\n",
"-280.9\n",
"-281.9\n",
"-282.9\n",
"-283.9\n",
"-284.9\n",
"-285.9\n",
"-286.9\n",
"-287.9\n",
"-288.9\n",
"-289.9\n",
"-290.9\n",
"-291.9\n",
"-292.9\n",
"-293.9\n",
"-294.9\n",
"-295.9\n",
"-296.9\n",
"-297.9\n",
"-298.9\n",
"-299.9\n",
"-300.9\n",
"-301.9\n",
"-302.9\n",
"-303.9\n",
"-304.9\n",
"-305.9\n",
"-306.9\n",
"-307.9\n",
"-308.9\n",
"-309.9\n",
"-310.9\n",
"-311.9\n",
"-312.9\n",
"-313.9\n",
"-314.9\n",
"-315.9\n",
"-316.9\n",
"-317.9\n",
"-318.9\n",
"-319.9\n",
"-320.9\n",
"-321.9\n",
"-322.9\n",
"-323.9\n",
"-324.9\n",
"-325.9\n",
"-326.9\n",
"-327.9\n",
"-328.9\n",
"-329.9\n",
"-330.9\n",
"-331.9\n",
"-332.9\n",
"-333.9\n",
"-334.9\n",
"-335.9\n",
"-336.9\n",
"-337.9\n",
"-338.9\n",
"-339.9\n",
"-340.9\n",
"-341.9\n",
"-342.9\n",
"-343.9\n",
"-344.9\n",
"-345.9\n",
"-346.9\n",
"-347.9\n",
"-348.9\n",
"-349.9\n",
"-350.9\n",
"-351.9\n",
"-352.9\n",
"-353.9\n",
"-354.9\n",
"-355.9\n",
"-356.9\n",
"-357.9\n",
"-358.9\n",
"-359.9\n",
"-360.9\n",
"-361.9\n",
"-362.9\n",
"-363.9\n",
"-364.9\n",
"-365.9\n",
"-366.9\n",
"-367.9\n",
"-368.9\n",
"-369.9\n",
"-370.9\n",
"-371.9\n",
"-372.9\n",
"-373.9\n",
"-374.9\n",
"-375.9\n",
"-376.9\n",
"-377.9\n",
"-378.9\n",
"-379.9\n",
"-380.9\n",
"-381.9\n",
"-382.9\n",
"-383.9\n",
"-384.9\n",
"-385.9\n",
"-386.9\n",
"-387.9\n",
"-388.9\n",
"-389.9\n",
"-390.9\n",
"-391.9\n",
"-392.9\n",
"-393.9\n",
"-394.9\n",
"-395.9\n",
"-396.9\n",
"-397.9\n",
"-398.9\n",
"-399.9\n",
"-400.9\n",
"-401.9\n",
"-402.9\n",
"-403.9\n",
"-404.9\n",
"-405.9\n",
"-406.9\n",
"-407.9\n",
"-408.9\n",
"-409.9\n",
"-410.9\n",
"-411.9\n",
"-412.9\n",
"-413.9\n",
"-414.9\n",
"-415.9\n",
"-416.9\n",
"-417.9\n",
"-418.9\n",
"-419.9\n",
"-420.9\n",
"-421.9\n",
"-422.9\n",
"-423.9\n",
"-424.9\n",
"-425.9\n",
"-426.9\n",
"-427.9\n",
"-428.9\n",
"-429.9\n",
"-430.9\n",
"-431.9\n",
"-432.9\n",
"-433.9\n",
"-434.9\n",
"-435.9\n",
"-436.9\n",
"-437.9\n",
"-438.9\n",
"-439.9\n",
"-440.9\n",
"-441.9\n",
"-442.9\n",
"-443.9\n",
"-444.9\n",
"-445.9\n",
"-446.9\n",
"-447.9\n",
"-448.9\n",
"-449.9\n",
"-450.9\n",
"-451.9\n",
"-452.9\n",
"-453.9\n",
"-454.9\n",
"-455.9\n",
"-456.9\n",
"-457.9\n",
"-458.9\n",
"-459.9\n",
"-460.9\n",
"-461.9\n",
"-462.9\n",
"-463.9\n",
"-464.9\n",
"-465.9\n",
"-466.9\n",
"-467.9\n",
"-468.9\n",
"-469.9\n",
"-470.9\n",
"-471.9\n",
"-472.9\n",
"-473.9\n",
"-474.9\n",
"-475.9\n",
"-476.9\n",
"-477.9\n",
"-478.9\n",
"-479.9\n",
"-480.9\n",
"-481.9\n",
"-482.9\n",
"-483.9\n",
"-484.9\n",
"-485.9\n",
"-486.9\n",
"-487.9\n",
"-488.9\n",
"-489.9\n",
"-490.9\n",
"-491.9\n",
"-492.9\n",
"-493.9\n",
"-494.9\n",
"-495.9\n",
"-496.9\n",
"-497.9\n",
"-498.9\n",
"-499.9\n",
"-500.9\n",
"-501.9\n",
"-502.9\n",
"-503.9\n",
"-504.9\n",
"-505.9\n",
"-506.9\n",
"-507.9\n",
"-508.9\n",
"-509.9\n",
"-510.9\n",
"-511.9\n",
"-512.9\n",
"-513.9\n",
"-514.9\n",
"-515.9\n",
"-516.9\n",
"-517.9\n",
"-518.9\n",
"-519.9\n",
"-520.9\n",
"-521.9\n",
"-522.9\n",
"-523.9\n",
"-524.9\n",
"-525.9\n",
"-526.9\n",
"-527.9\n",
"-528.9\n",
"-529.9\n",
"-530.9\n",
"-531.9\n",
"-532.9\n",
"-533.9\n",
"-534.9\n",
"-535.9\n",
"-536.9\n",
"-537.9\n",
"-538.9\n",
"-539.9\n",
"-540.9\n",
"-541.9\n",
"-542.9\n",
"-543.9\n",
"-544.9\n",
"-545.9\n",
"-546.9\n",
"-547.9\n",
"-548.9\n",
"-549.9\n",
"-550.9\n",
"-551.9\n",
"-552.9\n",
"-553.9\n",
"-554.9\n",
"-555.9\n",
"-556.9\n",
"-557.9\n",
"-558.9\n",
"-559.9\n",
"-560.9\n",
"-561.9\n",
"-562.9\n",
"-563.9\n",
"-564.9\n",
"-565.9\n",
"-566.9\n",
"-567.9\n",
"-568.9\n",
"-569.9\n",
"-570.9\n",
"-571.9\n",
"-572.9\n",
"-573.9\n",
"-574.9\n",
"-575.9\n",
"-576.9\n",
"-577.9\n",
"-578.9\n",
"-579.9\n",
"-580.9\n",
"-581.9\n",
"-582.9\n",
"-583.9\n",
"-584.9\n",
"-585.9\n",
"-586.9\n",
"-587.9\n",
"-588.9\n",
"-589.9\n",
"-590.9\n",
"-591.9\n",
"-592.9\n",
"-593.9\n",
"-594.9\n",
"-595.9\n",
"-596.9\n",
"-597.9\n",
"-598.9\n",
"-599.9\n",
"-600.9\n",
"-601.9\n",
"-602.9\n",
"-603.9\n",
"-604.9\n",
"-605.9\n",
"-606.9\n",
"-607.9\n",
"-608.9\n",
"-609.9\n",
"-610.9\n",
"-611.9\n",
"-612.9\n",
"-613.9\n",
"-614.9\n",
"-615.9\n",
"-616.9\n",
"-617.9\n",
"-618.9\n",
"-619.9\n",
"-620.9\n",
"-621.9\n",
"-622.9\n",
"-623.9\n",
"-624.9\n",
"-625.9\n",
"-626.9\n",
"-627.9\n",
"-628.9\n",
"-629.9\n",
"-630.9\n",
"-631.9\n",
"-632.9\n",
"-633.9\n",
"-634.9\n",
"-635.9\n",
"-636.9\n",
"-637.9\n",
"-638.9\n",
"-639.9\n",
"-640.9\n",
"-641.9\n",
"-642.9\n",
"-643.9\n",
"-644.9\n",
"-645.9\n",
"-646.9\n",
"-647.9\n",
"-648.9\n",
"-649.9\n",
"-650.9\n",
"-651.9\n",
"-652.9\n",
"-653.9\n",
"-654.9\n",
"-655.9\n",
"-656.9\n",
"-657.9\n",
"-658.9\n",
"-659.9\n",
"-660.9\n",
"-661.9\n",
"-662.9\n",
"-663.9\n",
"-664.9\n",
"-665.9\n",
"-666.9\n",
"-667.9\n",
"-668.9\n",
"-669.9\n",
"-670.9\n",
"-671.9\n",
"-672.9\n",
"-673.9\n",
"-674.9\n",
"-675.9\n",
"-676.9\n",
"-677.9\n",
"-678.9\n",
"-679.9\n",
"-680.9\n",
"-681.9\n",
"-682.9\n",
"-683.9\n",
"-684.9\n",
"-685.9\n",
"-686.9\n",
"-687.9\n",
"-688.9\n",
"-689.9\n",
"-690.9\n",
"-691.9\n",
"-692.9\n",
"-693.9\n",
"-694.9\n",
"-695.9\n",
"-696.9\n",
"-697.9\n",
"-698.9\n",
"-699.9\n",
"-700.9\n",
"-701.9\n",
"-702.9\n",
"-703.9\n",
"-704.9\n",
"-705.9\n",
"-706.9\n",
"-707.9\n",
"-708.9\n",
"-709.9\n",
"-710.9\n",
"-711.9\n",
"-712.9\n",
"-713.9\n",
"-714.9\n",
"-715.9\n",
"-716.9\n",
"-717.9\n",
"-718.9\n",
"-719.9\n",
"-720.9\n",
"-721.9\n",
"-722.9\n",
"-723.9\n",
"-724.9\n",
"-725.9\n",
"-726.9\n",
"-727.9\n",
"-728.9\n",
"-729.9\n",
"-730.9\n",
"-731.9\n",
"-732.9\n",
"-733.9\n",
"-734.9\n",
"-735.9\n",
"-736.9\n",
"-737.9\n",
"-738.9\n",
"-739.9\n",
"-740.9\n",
"-741.9\n",
"-742.9\n",
"-743.9\n",
"-744.9\n",
"-745.9\n",
"-746.9\n",
"-747.9\n",
"-748.9\n",
"-749.9\n",
"-750.9\n",
"-751.9\n",
"-752.9\n",
"-753.9\n",
"-754.9\n",
"-755.9\n",
"-756.9\n",
"-757.9\n",
"-758.9\n",
"-759.9\n",
"-760.9\n",
"-761.9\n",
"-762.9\n",
"-763.9\n",
"-764.9\n",
"-765.9\n",
"-766.9\n",
"-767.9\n",
"-768.9\n",
"-769.9\n",
"-770.9\n",
"-771.9\n",
"-772.9\n",
"-773.9\n",
"-774.9\n",
"-775.9\n",
"-776.9\n",
"-777.9\n",
"-778.9\n",
"-779.9\n",
"-780.9\n",
"-781.9\n",
"-782.9\n",
"-783.9\n",
"-784.9\n",
"-785.9\n",
"-786.9\n",
"-787.9\n",
"-788.9\n",
"-789.9\n",
"-790.9\n",
"-791.9\n",
"-792.9\n",
"-793.9\n",
"-794.9\n",
"-795.9\n",
"-796.9\n",
"-797.9\n",
"-798.9\n",
"-799.9\n",
"-800.9\n",
"-801.9\n",
"-802.9\n",
"-803.9\n",
"-804.9\n",
"-805.9\n",
"-806.9\n",
"-807.9\n",
"-808.9\n",
"-809.9\n",
"-810.9\n",
"-811.9\n",
"-812.9\n",
"-813.9\n",
"-814.9\n",
"-815.9\n",
"-816.9\n",
"-817.9\n",
"-818.9\n",
"-819.9\n",
"-820.9\n",
"-821.9\n",
"-822.9\n",
"-823.9\n",
"-824.9\n",
"-825.9\n",
"-826.9\n",
"-827.9\n",
"-828.9\n",
"-829.9\n",
"-830.9\n",
"-831.9\n",
"-832.9\n",
"-833.9\n",
"-834.9\n",
"-835.9\n",
"-836.9\n",
"-837.9\n",
"-838.9\n",
"-839.9\n",
"-840.9\n",
"-841.9\n",
"-842.9\n",
"-843.9\n",
"-844.9\n",
"-845.9\n",
"-846.9\n",
"-847.9\n",
"-848.9\n",
"-849.9\n",
"-850.9\n",
"-851.9\n",
"-852.9\n",
"-853.9\n",
"-854.9\n",
"-855.9\n",
"-856.9\n",
"-857.9\n",
"-858.9\n",
"-859.9\n",
"-860.9\n",
"-861.9\n",
"-862.9\n",
"-863.9\n",
"-864.9\n",
"-865.9\n",
"-866.9\n",
"-867.9\n",
"-868.9\n",
"-869.9\n",
"-870.9\n",
"-871.9\n",
"-872.9\n",
"-873.9\n",
"-874.9\n",
"-875.9\n",
"-876.9\n",
"-877.9\n",
"-878.9\n",
"-879.9\n",
"-880.9\n",
"-881.9\n",
"-882.9\n",
"-883.9\n",
"-884.9\n",
"-885.9\n",
"-886.9\n",
"-887.9\n",
"-888.9\n",
"-889.9\n",
"-890.9\n",
"-891.9\n",
"-892.9\n",
"-893.9\n",
"-894.9\n",
"-895.9\n",
"-896.9\n",
"-897.9\n",
"-898.9\n",
"-899.9\n",
"-900.9\n",
"-901.9\n",
"-902.9\n",
"-903.9\n",
"-904.9\n",
"-905.9\n",
"-906.9\n",
"-907.9\n",
"-908.9\n",
"-909.9\n",
"-910.9\n",
"-911.9\n",
"-912.9\n",
"-913.9\n",
"-914.9\n",
"-915.9\n",
"-916.9\n",
"-917.9\n",
"-918.9\n",
"-919.9\n",
"-920.9\n",
"-921.9\n",
"-922.9\n",
"-923.9\n",
"-924.9\n",
"-925.9\n",
"-926.9\n",
"-927.9\n",
"-928.9\n",
"-929.9\n",
"-930.9\n",
"-931.9\n",
"-932.9\n",
"-933.9\n",
"-934.9\n",
"-935.9\n",
"-936.9\n",
"-937.9\n",
"-938.9\n",
"-939.9\n",
"-940.9\n",
"-941.9\n",
"-942.9\n",
"-943.9\n",
"-944.9\n",
"-945.9\n",
"-946.9\n",
"-947.9\n",
"-948.9\n",
"-949.9\n",
"-950.9\n",
"-951.9\n",
"-952.9\n",
"-953.9\n",
"-954.9\n",
"-955.9\n",
"-956.9\n",
"-957.9\n",
"-958.9\n",
"-959.9\n",
"-960.9\n",
"-961.9\n",
"-962.9\n",
"-963.9\n",
"-964.9\n",
"-965.9\n",
"-966.9\n",
"-967.9\n",
"-968.9\n",
"-969.9\n",
"-970.9\n",
"-971.9\n",
"-972.9\n",
"-973.9\n",
"-974.9\n",
"-975.9\n",
"-976.9\n",
"-977.9\n",
"-978.9\n",
"-979.9\n",
"-980.9\n",
"-981.9\n",
"-982.9\n",
"-983.9\n",
"-984.9\n",
"-985.9\n",
"-986.9\n",
"-987.9\n",
"-988.9\n",
"-989.9\n",
"-990.9\n",
"-991.9\n",
"-992.9\n",
"-993.9\n",
"-994.9\n",
"-995.9\n",
"-996.9\n",
"-997.9\n",
"-998.9\n",
"-999.9\n",
"-1000.9\n",
"-1001.9\n",
"-1002.9\n",
"-1003.9\n",
"-1004.9\n",
"-1005.9\n",
"-1006.9\n",
"-1007.9\n",
"-1008.9\n",
"-1009.9\n",
"-1010.9\n",
"-1011.9\n",
"-1012.9\n",
"-1013.9\n",
"-1014.9\n",
"-1015.9\n",
"-1016.9\n",
"-1017.9\n",
"-1018.9\n",
"-1019.9\n",
"-1020.9\n",
"-1021.9\n",
"-1022.9\n",
"-1023.9\n",
"-1024.9\n",
"-1025.9\n",
"-1026.9\n",
"-1027.9\n",
"-1028.9\n",
"-1029.9\n",
"-1030.9\n",
"-1031.9\n",
"-1032.9\n",
"-1033.9\n",
"-1034.9\n",
"-1035.9\n",
"-1036.9\n",
"-1037.9\n",
"-1038.9\n",
"-1039.9\n",
"-1040.9\n",
"-1041.9\n",
"-1042.9\n",
"-1043.9\n",
"-1044.9\n",
"-1045.9\n",
"-1046.9\n",
"-1047.9\n",
"-1048.9\n",
"-1049.9\n",
"-1050.9\n",
"-1051.9\n",
"-1052.9\n",
"-1053.9\n",
"-1054.9\n",
"-1055.9\n",
"-1056.9\n",
"-1057.9\n",
"-1058.9\n",
"-1059.9\n",
"-1060.9\n",
"-1061.9\n",
"-1062.9\n",
"-1063.9\n",
"-1064.9\n",
"-1065.9\n",
"-1066.9\n",
"-1067.9\n",
"-1068.9\n",
"-1069.9\n",
"-1070.9\n",
"-1071.9\n",
"-1072.9\n",
"-1073.9\n",
"-1074.9\n",
"-1075.9\n",
"-1076.9\n",
"-1077.9\n",
"-1078.9\n",
"-1079.9\n",
"-1080.9\n",
"-1081.9\n",
"-1082.9\n",
"-1083.9\n",
"-1084.9\n",
"-1085.9\n",
"-1086.9\n",
"-1087.9\n",
"-1088.9\n",
"-1089.9\n",
"-1090.9\n",
"-1091.9\n",
"-1092.9\n",
"-1093.9\n",
"-1094.9\n",
"-1095.9\n",
"-1096.9\n",
"-1097.9\n",
"-1098.9\n",
"-1099.9\n",
"-1100.9\n",
"-1101.9\n",
"-1102.9\n",
"-1103.9\n",
"-1104.9\n",
"-1105.9\n",
"-1106.9\n",
"-1107.9\n",
"-1108.9\n",
"-1109.9\n",
"-1110.9\n",
"-1111.9\n",
"-1112.9\n",
"-1113.9\n",
"-1114.9\n",
"-1115.9\n",
"-1116.9\n",
"-1117.9\n",
"-1118.9\n",
"-1119.9\n",
"-1120.9\n",
"-1121.9\n",
"-1122.9\n",
"-1123.9\n",
"-1124.9\n",
"-1125.9\n",
"-1126.9\n",
"-1127.9\n",
"-1128.9\n",
"-1129.9\n",
"-1130.9\n",
"-1131.9\n",
"-1132.9\n",
"-1133.9\n",
"-1134.9\n",
"-1135.9\n",
"-1136.9\n",
"-1137.9\n",
"-1138.9\n",
"-1139.9\n",
"-1140.9\n",
"-1141.9\n",
"-1142.9\n",
"-1143.9\n",
"-1144.9\n",
"-1145.9\n",
"-1146.9\n",
"-1147.9\n",
"-1148.9\n",
"-1149.9\n",
"-1150.9\n",
"-1151.9\n",
"-1152.9\n",
"-1153.9\n",
"-1154.9\n",
"-1155.9\n",
"-1156.9\n",
"-1157.9\n",
"-1158.9\n",
"-1159.9\n",
"-1160.9\n",
"-1161.9\n",
"-1162.9\n",
"-1163.9\n",
"-1164.9\n",
"-1165.9\n",
"-1166.9\n",
"-1167.9\n",
"-1168.9\n",
"-1169.9\n",
"-1170.9\n",
"-1171.9\n",
"-1172.9\n",
"-1173.9\n",
"-1174.9\n",
"-1175.9\n",
"-1176.9\n",
"-1177.9\n",
"-1178.9\n",
"-1179.9\n",
"-1180.9\n",
"-1181.9\n",
"-1182.9\n",
"-1183.9\n",
"-1184.9\n",
"-1185.9\n",
"-1186.9\n",
"-1187.9\n",
"-1188.9\n",
"-1189.9\n",
"-1190.9\n",
"-1191.9\n",
"-1192.9\n",
"-1193.9\n",
"-1194.9\n",
"-1195.9\n",
"-1196.9\n",
"-1197.9\n",
"-1198.9\n",
"-1199.9\n",
"-1200.9\n",
"-1201.9\n",
"-1202.9\n",
"-1203.9\n",
"-1204.9\n",
"-1205.9\n",
"-1206.9\n",
"-1207.9\n",
"-1208.9\n",
"-1209.9\n",
"-1210.9\n",
"-1211.9\n",
"-1212.9\n",
"-1213.9\n",
"-1214.9\n",
"-1215.9\n",
"-1216.9\n",
"-1217.9\n",
"-1218.9\n",
"-1219.9\n",
"-1220.9\n",
"-1221.9\n",
"-1222.9\n",
"-1223.9\n",
"-1224.9\n",
"-1225.9\n",
"-1226.9\n",
"-1227.9\n",
"-1228.9\n",
"-1229.9\n",
"-1230.9\n",
"-1231.9\n",
"-1232.9\n",
"-1233.9\n",
"-1234.9\n",
"-1235.9\n",
"-1236.9\n",
"-1237.9\n",
"-1238.9\n",
"-1239.9\n",
"-1240.9\n",
"-1241.9\n",
"-1242.9\n",
"-1243.9\n",
"-1244.9\n",
"-1245.9\n",
"-1246.9\n",
"-1247.9\n",
"-1248.9\n",
"-1249.9\n",
"-1250.9\n",
"-1251.9\n",
"-1252.9\n",
"-1253.9\n",
"-1254.9\n",
"-1255.9\n",
"-1256.9\n",
"-1257.9\n",
"-1258.9\n",
"-1259.9\n",
"-1260.9\n",
"-1261.9\n",
"-1262.9\n",
"-1263.9\n",
"-1264.9\n",
"-1265.9\n",
"-1266.9\n",
"-1267.9\n",
"-1268.9\n",
"-1269.9\n",
"-1270.9\n",
"-1271.9\n",
"-1272.9\n",
"-1273.9\n",
"-1274.9\n",
"-1275.9\n",
"-1276.9\n",
"-1277.9\n",
"-1278.9\n",
"-1279.9\n",
"-1280.9\n",
"-1281.9\n",
"-1282.9\n",
"-1283.9\n",
"-1284.9\n",
"-1285.9\n",
"-1286.9\n",
"-1287.9\n",
"-1288.9\n",
"-1289.9\n",
"-1290.9\n",
"-1291.9\n",
"-1292.9\n",
"-1293.9\n",
"-1294.9\n",
"-1295.9\n",
"-1296.9\n",
"-1297.9\n",
"-1298.9\n",
"-1299.9\n",
"-1300.9\n",
"-1301.9\n",
"-1302.9\n",
"-1303.9\n",
"-1304.9\n",
"-1305.9\n",
"-1306.9\n",
"-1307.9\n",
"-1308.9\n",
"-1309.9\n",
"-1310.9\n",
"-1311.9\n",
"-1312.9\n",
"-1313.9\n",
"-1314.9\n",
"-1315.9\n",
"-1316.9\n",
"-1317.9\n",
"-1318.9\n",
"-1319.9\n",
"-1320.9\n",
"-1321.9\n",
"-1322.9\n",
"-1323.9\n",
"-1324.9\n",
"-1325.9\n",
"-1326.9\n",
"-1327.9\n",
"-1328.9\n",
"-1329.9\n",
"-1330.9\n",
"-1331.9\n",
"-1332.9\n",
"-1333.9\n",
"-1334.9\n",
"-1335.9\n",
"-1336.9\n",
"-1337.9\n",
"-1338.9\n",
"-1339.9\n",
"-1340.9\n",
"-1341.9\n",
"-1342.9\n",
"-1343.9\n",
"-1344.9\n",
"-1345.9\n",
"-1346.9\n",
"-1347.9\n",
"-1348.9\n",
"-1349.9\n",
"-1350.9\n",
"-1351.9\n",
"-1352.9\n",
"-1353.9\n",
"-1354.9\n",
"-1355.9\n",
"-1356.9\n",
"-1357.9\n",
"-1358.9\n",
"-1359.9\n",
"-1360.9\n",
"-1361.9\n",
"-1362.9\n",
"-1363.9\n",
"-1364.9\n",
"-1365.9\n",
"-1366.9\n",
"-1367.9\n",
"-1368.9\n",
"-1369.9\n",
"-1370.9\n",
"-1371.9\n",
"-1372.9\n",
"-1373.9\n",
"-1374.9\n",
"-1375.9\n",
"-1376.9\n",
"-1377.9\n",
"-1378.9\n",
"-1379.9\n",
"-1380.9\n",
"-1381.9\n",
"-1382.9\n",
"-1383.9\n",
"-1384.9\n",
"-1385.9\n",
"-1386.9\n",
"-1387.9\n",
"-1388.9\n",
"-1389.9\n",
"-1390.9\n",
"-1391.9\n",
"-1392.9\n",
"-1393.9\n",
"-1394.9\n",
"-1395.9\n",
"-1396.9\n",
"-1397.9\n",
"-1398.9\n",
"-1399.9\n",
"-1400.9\n",
"-1401.9\n",
"-1402.9\n",
"-1403.9\n",
"-1404.9\n",
"-1405.9\n",
"-1406.9\n",
"-1407.9\n",
"-1408.9\n",
"-1409.9\n",
"-1410.9\n",
"-1411.9\n",
"-1412.9\n",
"-1413.9\n",
"-1414.9\n",
"-1415.9\n",
"-1416.9\n",
"-1417.9\n",
"-1418.9\n",
"-1419.9\n",
"-1420.9\n",
"-1421.9\n",
"-1422.9\n",
"-1423.9\n",
"-1424.9\n",
"-1425.9\n",
"-1426.9\n",
"-1427.9\n",
"-1428.9\n",
"-1429.9\n",
"-1430.9\n",
"-1431.9\n",
"-1432.9\n",
"-1433.9\n",
"-1434.9\n",
"-1435.9\n",
"-1436.9\n",
"-1437.9\n",
"-1438.9\n",
"-1439.9\n",
"-1440.9\n",
"-1441.9\n",
"-1442.9\n",
"-1443.9\n",
"-1444.9\n",
"-1445.9\n",
"-1446.9\n",
"-1447.9\n",
"-1448.9\n",
"-1449.9\n",
"-1450.9\n",
"-1451.9\n",
"-1452.9\n",
"-1453.9\n",
"-1454.9\n",
"-1455.9\n",
"-1456.9\n",
"-1457.9\n",
"-1458.9\n",
"-1459.9\n",
"-1460.9\n",
"-1461.9\n",
"-1462.9\n",
"-1463.9\n",
"-1464.9\n",
"-1465.9\n",
"-1466.9\n",
"-1467.9\n",
"-1468.9\n",
"-1469.9\n",
"-1470.9\n",
"-1471.9\n",
"-1472.9\n",
"-1473.9\n",
"-1474.9\n",
"-1475.9\n",
"-1476.9\n",
"-1477.9\n",
"-1478.9\n",
"-1479.9\n",
"-1480.9\n",
"-1481.9\n",
"-1482.9\n",
"-1483.9\n",
"-1484.9\n",
"-1485.9\n",
"-1486.9\n",
"-1487.9\n",
"-1488.9\n",
"-1489.9\n",
"-1490.9\n",
"-1491.9\n",
"-1492.9\n",
"-1493.9\n",
"-1494.9\n",
"-1495.9\n",
"-1496.9\n",
"-1497.9\n",
"-1498.9\n",
"-1499.9\n",
"-1500.9\n",
"-1501.9\n",
"-1502.9\n",
"-1503.9\n",
"-1504.9\n",
"-1505.9\n",
"-1506.9\n",
"-1507.9\n",
"-1508.9\n",
"-1509.9\n",
"-1510.9\n",
"-1511.9\n",
"-1512.9\n",
"-1513.9\n",
"-1514.9\n",
"-1515.9\n",
"-1516.9\n",
"-1517.9\n",
"-1518.9\n",
"-1519.9\n",
"-1520.9\n",
"-1521.9\n",
"-1522.9\n",
"-1523.9\n",
"-1524.9\n",
"-1525.9\n",
"-1526.9\n",
"-1527.9\n",
"-1528.9\n",
"-1529.9\n",
"-1530.9\n",
"-1531.9\n",
"-1532.9\n",
"-1533.9\n",
"-1534.9\n",
"-1535.9\n",
"-1536.9\n",
"-1537.9\n",
"-1538.9\n",
"-1539.9\n",
"-1540.9\n",
"-1541.9\n",
"-1542.9\n",
"-1543.9\n",
"-1544.9\n",
"-1545.9\n",
"-1546.9\n",
"-1547.9\n",
"-1548.9\n",
"-1549.9\n",
"-1550.9\n",
"-1551.9\n",
"-1552.9\n",
"-1553.9\n",
"-1554.9\n",
"-1555.9\n",
"-1556.9\n",
"-1557.9\n",
"-1558.9\n",
"-1559.9\n",
"-1560.9\n",
"-1561.9\n",
"-1562.9\n",
"-1563.9\n",
"-1564.9\n",
"-1565.9\n",
"-1566.9\n",
"-1567.9\n",
"-1568.9\n",
"-1569.9\n",
"-1570.9\n",
"-1571.9\n",
"-1572.9\n",
"-1573.9\n",
"-1574.9\n",
"-1575.9\n",
"-1576.9\n",
"-1577.9\n",
"-1578.9\n",
"-1579.9\n",
"-1580.9\n",
"-1581.9\n",
"-1582.9\n",
"-1583.9\n",
"-1584.9\n",
"-1585.9\n",
"-1586.9\n",
"-1587.9\n",
"-1588.9\n",
"-1589.9\n",
"-1590.9\n",
"-1591.9\n",
"-1592.9\n",
"-1593.9\n",
"-1594.9\n",
"-1595.9\n",
"-1596.9\n",
"-1597.9\n",
"-1598.9\n",
"-1599.9\n",
"-1600.9\n",
"-1601.9\n",
"-1602.9\n",
"-1603.9\n",
"-1604.9\n",
"-1605.9\n",
"-1606.9\n",
"-1607.9\n",
"-1608.9\n",
"-1609.9\n",
"-1610.9\n",
"-1611.9\n",
"-1612.9\n",
"-1613.9\n",
"-1614.9\n",
"-1615.9\n",
"-1616.9\n",
"-1617.9\n",
"-1618.9\n",
"-1619.9\n",
"-1620.9\n",
"-1621.9\n",
"-1622.9\n",
"-1623.9\n",
"-1624.9\n",
"-1625.9\n",
"-1626.9\n",
"-1627.9\n",
"-1628.9\n",
"-1629.9\n",
"-1630.9\n",
"-1631.9\n",
"-1632.9\n",
"-1633.9\n",
"-1634.9\n",
"-1635.9\n",
"-1636.9\n",
"-1637.9\n",
"-1638.9\n",
"-1639.9\n",
"-1640.9\n",
"-1641.9\n",
"-1642.9\n",
"-1643.9\n",
"-1644.9\n",
"-1645.9\n",
"-1646.9\n",
"-1647.9\n",
"-1648.9\n",
"-1649.9\n",
"-1650.9\n",
"-1651.9\n",
"-1652.9\n",
"-1653.9\n",
"-1654.9\n",
"-1655.9\n",
"-1656.9\n",
"-1657.9\n",
"-1658.9\n",
"-1659.9\n",
"-1660.9\n",
"-1661.9\n",
"-1662.9\n",
"-1663.9\n",
"-1664.9\n",
"-1665.9\n",
"-1666.9\n",
"-1667.9\n",
"-1668.9\n",
"-1669.9\n",
"-1670.9\n",
"-1671.9\n",
"-1672.9\n",
"-1673.9\n",
"-1674.9\n",
"-1675.9\n",
"-1676.9\n",
"-1677.9\n",
"-1678.9\n",
"-1679.9\n",
"-1680.9\n",
"-1681.9\n",
"-1682.9\n",
"-1683.9\n",
"-1684.9\n",
"-1685.9\n",
"-1686.9\n",
"-1687.9\n",
"-1688.9\n",
"-1689.9\n",
"-1690.9\n",
"-1691.9\n",
"-1692.9\n",
"-1693.9\n",
"-1694.9\n",
"-1695.9\n",
"-1696.9\n",
"-1697.9\n",
"-1698.9\n",
"-1699.9\n",
"-1700.9\n",
"-1701.9\n",
"-1702.9\n",
"-1703.9\n",
"-1704.9\n",
"-1705.9\n",
"-1706.9\n",
"-1707.9\n",
"-1708.9\n",
"-1709.9\n",
"-1710.9\n",
"-1711.9\n",
"-1712.9\n",
"-1713.9\n",
"-1714.9\n",
"-1715.9\n",
"-1716.9\n",
"-1717.9\n",
"-1718.9\n",
"-1719.9\n",
"-1720.9\n",
"-1721.9\n",
"-1722.9\n",
"-1723.9\n",
"-1724.9\n",
"-1725.9\n",
"-1726.9\n",
"-1727.9\n",
"-1728.9\n",
"-1729.9\n",
"-1730.9\n",
"-1731.9\n",
"-1732.9\n",
"-1733.9\n",
"-1734.9\n",
"-1735.9\n",
"-1736.9\n",
"-1737.9\n",
"-1738.9\n",
"-1739.9\n",
"-1740.9\n",
"-1741.9\n",
"-1742.9\n",
"-1743.9\n",
"-1744.9\n",
"-1745.9\n",
"-1746.9\n",
"-1747.9\n",
"-1748.9\n",
"-1749.9\n",
"-1750.9\n",
"-1751.9\n",
"-1752.9\n",
"-1753.9\n",
"-1754.9\n",
"-1755.9\n",
"-1756.9\n",
"-1757.9\n",
"-1758.9\n",
"-1759.9\n",
"-1760.9\n",
"-1761.9\n",
"-1762.9\n",
"-1763.9\n",
"-1764.9\n",
"-1765.9\n",
"-1766.9\n",
"-1767.9\n",
"-1768.9\n",
"-1769.9\n",
"-1770.9\n",
"-1771.9\n",
"-1772.9\n",
"-1773.9\n",
"-1774.9\n",
"-1775.9\n",
"-1776.9\n",
"-1777.9\n",
"-1778.9\n",
"-1779.9\n",
"-1780.9\n",
"-1781.9\n",
"-1782.9\n",
"-1783.9\n",
"-1784.9\n",
"-1785.9\n",
"-1786.9\n",
"-1787.9\n",
"-1788.9\n",
"-1789.9\n",
"-1790.9\n",
"-1791.9\n",
"-1792.9\n",
"-1793.9\n",
"-1794.9\n",
"-1795.9\n",
"-1796.9\n",
"-1797.9\n",
"-1798.9\n",
"-1799.9\n",
"-1800.9\n",
"-1801.9\n",
"-1802.9\n",
"-1803.9\n",
"-1804.9\n",
"-1805.9\n",
"-1806.9\n",
"-1807.9\n",
"-1808.9\n",
"-1809.9\n",
"-1810.9\n",
"-1811.9\n",
"-1812.9\n",
"-1813.9\n",
"-1814.9\n",
"-1815.9\n",
"-1816.9\n",
"-1817.9\n",
"-1818.9\n",
"-1819.9\n",
"-1820.9\n",
"-1821.9\n",
"-1822.9\n",
"-1823.9\n",
"-1824.9\n",
"-1825.9\n",
"-1826.9\n",
"-1827.9\n",
"-1828.9\n",
"-1829.9\n",
"-1830.9\n",
"-1831.9\n",
"-1832.9\n",
"-1833.9\n",
"-1834.9\n",
"-1835.9\n",
"-1836.9\n",
"-1837.9\n",
"-1838.9\n",
"-1839.9\n",
"-1840.9\n",
"-1841.9\n",
"-1842.9\n",
"-1843.9\n",
"-1844.9\n",
"-1845.9\n",
"-1846.9\n",
"-1847.9\n",
"-1848.9\n",
"-1849.9\n",
"-1850.9\n",
"-1851.9\n",
"-1852.9\n",
"-1853.9\n",
"-1854.9\n",
"-1855.9\n",
"-1856.9\n",
"-1857.9\n",
"-1858.9\n",
"-1859.9\n",
"-1860.9\n",
"-1861.9\n",
"-1862.9\n",
"-1863.9\n",
"-1864.9\n",
"-1865.9\n",
"-1866.9\n",
"-1867.9\n",
"-1868.9\n",
"-1869.9\n",
"-1870.9\n",
"-1871.9\n",
"-1872.9\n",
"-1873.9\n",
"-1874.9\n",
"-1875.9\n",
"-1876.9\n",
"-1877.9\n",
"-1878.9\n",
"-1879.9\n",
"-1880.9\n",
"-1881.9\n",
"-1882.9\n",
"-1883.9\n",
"-1884.9\n",
"-1885.9\n",
"-1886.9\n",
"-1887.9\n",
"-1888.9\n",
"-1889.9\n",
"-1890.9\n",
"-1891.9\n",
"-1892.9\n",
"-1893.9\n",
"-1894.9\n",
"-1895.9\n",
"-1896.9\n",
"-1897.9\n",
"-1898.9\n",
"-1899.9\n",
"-1900.9\n",
"-1901.9\n",
"-1902.9\n",
"-1903.9\n",
"-1904.9\n",
"-1905.9\n",
"-1906.9\n",
"-1907.9\n",
"-1908.9\n",
"-1909.9\n",
"-1910.9\n",
"-1911.9\n",
"-1912.9\n",
"-1913.9\n",
"-1914.9\n",
"-1915.9\n",
"-1916.9\n",
"-1917.9\n",
"-1918.9\n",
"-1919.9\n",
"-1920.9\n",
"-1921.9\n",
"-1922.9\n",
"-1923.9\n",
"-1924.9\n",
"-1925.9\n",
"-1926.9\n",
"-1927.9\n",
"-1928.9\n",
"-1929.9\n",
"-1930.9\n",
"-1931.9\n",
"-1932.9\n",
"-1933.9\n",
"-1934.9\n",
"-1935.9\n",
"-1936.9\n",
"-1937.9\n",
"-1938.9\n",
"-1939.9\n",
"-1940.9\n",
"-1941.9\n",
"-1942.9\n",
"-1943.9\n",
"-1944.9\n",
"-1945.9\n",
"-1946.9\n",
"-1947.9\n",
"-1948.9\n",
"-1949.9\n",
"-1950.9\n",
"-1951.9\n",
"-1952.9\n",
"-1953.9\n",
"-1954.9\n",
"-1955.9\n",
"-1956.9\n",
"-1957.9\n",
"-1958.9\n",
"-1959.9\n",
"-1960.9\n",
"-1961.9\n",
"-1962.9\n",
"-1963.9\n",
"-1964.9\n",
"-1965.9\n",
"-1966.9\n",
"-1967.9\n",
"-1968.9\n",
"-1969.9\n",
"-1970.9\n",
"-1971.9\n",
"-1972.9\n",
"-1973.9\n",
"-1974.9\n",
"-1975.9\n",
"-1976.9\n",
"-1977.9\n",
"-1978.9\n",
"-1979.9\n",
"-1980.9\n",
"-1981.9\n",
"-1982.9\n",
"-1983.9\n",
"-1984.9\n",
"-1985.9\n",
"-1986.9\n",
"-1987.9\n",
"-1988.9\n",
"-1989.9\n",
"-1990.9\n",
"-1991.9\n",
"-1992.9\n",
"-1993.9\n",
"-1994.9\n",
"-1995.9\n",
"-1996.9\n",
"-1997.9\n",
"-1998.9\n",
"-1999.9\n",
"-2000.9\n",
"-2001.9\n",
"-2002.9\n",
"-2003.9\n",
"-2004.9\n",
"-2005.9\n",
"-2006.9\n",
"-2007.9\n",
"-2008.9\n",
"-2009.9\n",
"-2010.9\n",
"-2011.9\n",
"-2012.9\n",
"-2013.9\n",
"-2014.9\n",
"-2015.9\n",
"-2016.9\n",
"-2017.9\n",
"-2018.9\n",
"-2019.9\n",
"-2020.9\n",
"-2021.9\n",
"-2022.9\n",
"-2023.9\n",
"-2024.9\n",
"-2025.9\n",
"-2026.9\n",
"-2027.9\n",
"-2028.9\n",
"-2029.9\n",
"-2030.9\n",
"-2031.9\n",
"-2032.9\n",
"-2033.9\n",
"-2034.9\n",
"-2035.9\n",
"-2036.9\n",
"-2037.9\n",
"-2038.9\n",
"-2039.9\n",
"-2040.9\n",
"-2041.9\n",
"-2042.9\n",
"-2043.9\n",
"-2044.9\n",
"-2045.9\n",
"-2046.9\n",
"-2047.9\n",
"-2048.9\n",
"-2049.9\n",
"-2050.9\n",
"-2051.9\n",
"-2052.9\n",
"-2053.9\n",
"-2054.9\n",
"-2055.9\n",
"-2056.9\n",
"-2057.9\n",
"-2058.9\n",
"-2059.9\n",
"-2060.9\n",
"-2061.9\n",
"-2062.9\n",
"-2063.9\n",
"-2064.9\n",
"-2065.9\n",
"-2066.9\n",
"-2067.9\n",
"-2068.9\n",
"-2069.9\n",
"-2070.9\n",
"-2071.9\n",
"-2072.9\n",
"-2073.9\n",
"-2074.9\n",
"-2075.9\n",
"-2076.9\n",
"-2077.9\n",
"-2078.9\n",
"-2079.9\n",
"-2080.9\n",
"-2081.9\n",
"-2082.9\n",
"-2083.9\n",
"-2084.9\n",
"-2085.9\n",
"-2086.9\n",
"-2087.9\n",
"-2088.9\n",
"-2089.9\n",
"-2090.9\n",
"-2091.9\n",
"-2092.9\n",
"-2093.9\n",
"-2094.9\n",
"-2095.9\n",
"-2096.9\n",
"-2097.9\n",
"-2098.9\n",
"-2099.9\n",
"-2100.9\n",
"-2101.9\n",
"-2102.9\n",
"-2103.9\n",
"-2104.9\n",
"-2105.9\n",
"-2106.9\n",
"-2107.9\n",
"-2108.9\n",
"-2109.9\n",
"-2110.9\n",
"-2111.9\n",
"-2112.9\n",
"-2113.9\n",
"-2114.9\n",
"-2115.9\n",
"-2116.9\n",
"-2117.9\n",
"-2118.9\n",
"-2119.9\n",
"-2120.9\n",
"-2121.9\n",
"-2122.9\n",
"-2123.9\n",
"-2124.9\n",
"-2125.9\n",
"-2126.9\n",
"-2127.9\n",
"-2128.9\n",
"-2129.9\n",
"-2130.9\n",
"-2131.9\n",
"-2132.9\n",
"-2133.9\n",
"-2134.9\n",
"-2135.9\n",
"-2136.9\n",
"-2137.9\n",
"-2138.9\n",
"-2139.9\n",
"-2140.9\n",
"-2141.9\n",
"-2142.9\n",
"-2143.9\n",
"-2144.9\n",
"-2145.9\n",
"-2146.9\n",
"-2147.9\n",
"-2148.9\n",
"-2149.9\n",
"-2150.9\n",
"-2151.9\n",
"-2152.9\n",
"-2153.9\n",
"-2154.9\n",
"-2155.9\n",
"-2156.9\n",
"-2157.9\n",
"-2158.9\n",
"-2159.9\n",
"-2160.9\n",
"-2161.9\n",
"-2162.9\n",
"-2163.9\n",
"-2164.9\n",
"-2165.9\n",
"-2166.9\n",
"-2167.9\n",
"-2168.9\n",
"-2169.9\n",
"-2170.9\n",
"-2171.9\n",
"-2172.9\n",
"-2173.9\n",
"-2174.9\n",
"-2175.9\n",
"-2176.9\n",
"-2177.9\n",
"-2178.9\n",
"-2179.9\n",
"-2180.9\n",
"-2181.9\n",
"-2182.9\n",
"-2183.9\n",
"-2184.9\n",
"-2185.9\n",
"-2186.9\n",
"-2187.9\n",
"-2188.9\n",
"-2189.9\n",
"-2190.9\n",
"-2191.9\n",
"-2192.9\n",
"-2193.9\n",
"-2194.9\n",
"-2195.9\n",
"-2196.9\n",
"-2197.9\n",
"-2198.9\n",
"-2199.9\n",
"-2200.9\n",
"-2201.9\n",
"-2202.9\n",
"-2203.9\n",
"-2204.9\n",
"-2205.9\n",
"-2206.9\n",
"-2207.9\n",
"-2208.9\n",
"-2209.9\n",
"-2210.9\n",
"-2211.9\n",
"-2212.9\n",
"-2213.9\n",
"-2214.9\n",
"-2215.9\n",
"-2216.9\n",
"-2217.9\n",
"-2218.9\n",
"-2219.9\n",
"-2220.9\n",
"-2221.9\n",
"-2222.9\n",
"-2223.9\n",
"-2224.9\n",
"-2225.9\n",
"-2226.9\n",
"-2227.9\n",
"-2228.9\n",
"-2229.9\n",
"-2230.9\n",
"-2231.9\n",
"-2232.9\n",
"-2233.9\n",
"-2234.9\n",
"-2235.9\n",
"-2236.9\n",
"-2237.9\n",
"-2238.9\n",
"-2239.9\n",
"-2240.9\n",
"-2241.9\n",
"-2242.9\n",
"-2243.9\n",
"-2244.9\n",
"-2245.9\n",
"-2246.9\n",
"-2247.9\n",
"-2248.9\n",
"-2249.9\n",
"-2250.9\n",
"-2251.9\n",
"-2252.9\n",
"-2253.9\n",
"-2254.9\n",
"-2255.9\n",
"-2256.9\n",
"-2257.9\n",
"-2258.9\n",
"-2259.9\n",
"-2260.9\n",
"-2261.9\n",
"-2262.9\n",
"-2263.9\n",
"-2264.9\n",
"-2265.9\n",
"-2266.9\n",
"-2267.9\n",
"-2268.9\n",
"-2269.9\n",
"-2270.9\n",
"-2271.9\n",
"-2272.9\n",
"-2273.9\n",
"-2274.9\n",
"-2275.9\n",
"-2276.9\n",
"-2277.9\n",
"-2278.9\n",
"-2279.9\n",
"-2280.9\n",
"-2281.9\n",
"-2282.9\n",
"-2283.9\n",
"-2284.9\n",
"-2285.9\n",
"-2286.9\n",
"-2287.9\n",
"-2288.9\n",
"-2289.9\n",
"-2290.9\n",
"-2291.9\n",
"-2292.9\n",
"-2293.9\n",
"-2294.9\n",
"-2295.9\n",
"-2296.9\n",
"-2297.9\n",
"-2298.9\n",
"-2299.9\n",
"-2300.9\n",
"-2301.9\n",
"-2302.9\n",
"-2303.9\n",
"-2304.9\n",
"-2305.9\n",
"-2306.9\n",
"-2307.9\n",
"-2308.9\n",
"-2309.9\n",
"-2310.9\n",
"-2311.9\n",
"-2312.9\n",
"-2313.9\n",
"-2314.9\n",
"-2315.9\n",
"-2316.9\n",
"-2317.9\n",
"-2318.9\n",
"-2319.9\n",
"-2320.9\n",
"-2321.9\n",
"-2322.9\n",
"-2323.9\n",
"-2324.9\n",
"-2325.9\n",
"-2326.9\n",
"-2327.9\n",
"-2328.9\n",
"-2329.9\n",
"-2330.9\n",
"-2331.9\n",
"-2332.9\n",
"-2333.9\n",
"-2334.9\n",
"-2335.9\n",
"-2336.9\n",
"-2337.9\n",
"-2338.9\n",
"-2339.9\n",
"-2340.9\n",
"-2341.9\n",
"-2342.9\n",
"-2343.9\n",
"-2344.9\n",
"-2345.9\n",
"-2346.9\n",
"-2347.9\n",
"-2348.9\n",
"-2349.9\n",
"-2350.9\n",
"-2351.9\n",
"-2352.9\n",
"-2353.9\n",
"-2354.9\n",
"-2355.9\n",
"-2356.9\n",
"-2357.9\n",
"-2358.9\n",
"-2359.9\n",
"-2360.9\n",
"-2361.9\n",
"-2362.9\n",
"-2363.9\n",
"-2364.9\n",
"-2365.9\n",
"-2366.9\n",
"-2367.9\n",
"-2368.9\n",
"-2369.9\n",
"-2370.9\n",
"-2371.9\n",
"-2372.9\n",
"-2373.9\n",
"-2374.9\n",
"-2375.9\n",
"-2376.9\n",
"-2377.9\n",
"-2378.9\n",
"-2379.9\n",
"-2380.9\n",
"-2381.9\n",
"-2382.9\n",
"-2383.9\n",
"-2384.9\n",
"-2385.9\n",
"-2386.9\n",
"-2387.9\n",
"-2388.9\n",
"-2389.9\n",
"-2390.9\n",
"-2391.9\n",
"-2392.9\n",
"-2393.9\n",
"-2394.9\n",
"-2395.9\n",
"-2396.9\n",
"-2397.9\n",
"-2398.9\n",
"-2399.9\n",
"-2400.9\n",
"-2401.9\n",
"-2402.9\n",
"-2403.9\n",
"-2404.9\n",
"-2405.9\n",
"-2406.9\n",
"-2407.9\n",
"-2408.9\n",
"-2409.9\n",
"-2410.9\n",
"-2411.9\n",
"-2412.9\n",
"-2413.9\n",
"-2414.9\n",
"-2415.9\n",
"-2416.9\n",
"-2417.9\n",
"-2418.9\n",
"-2419.9\n",
"-2420.9\n",
"-2421.9\n",
"-2422.9\n",
"-2423.9\n",
"-2424.9\n",
"-2425.9\n",
"-2426.9\n",
"-2427.9\n",
"-2428.9\n",
"-2429.9\n",
"-2430.9\n",
"-2431.9\n",
"-2432.9\n",
"-2433.9\n",
"-2434.9\n",
"-2435.9\n",
"-2436.9\n",
"-2437.9\n",
"-2438.9\n",
"-2439.9\n",
"-2440.9\n",
"-2441.9\n",
"-2442.9\n",
"-2443.9\n",
"-2444.9\n",
"-2445.9\n",
"-2446.9\n",
"-2447.9\n",
"-2448.9\n",
"-2449.9\n",
"-2450.9\n",
"-2451.9\n",
"-2452.9\n",
"-2453.9\n",
"-2454.9\n",
"-2455.9\n",
"-2456.9\n",
"-2457.9\n",
"-2458.9\n",
"-2459.9\n",
"-2460.9\n",
"-2461.9\n",
"-2462.9\n",
"-2463.9\n",
"-2464.9\n",
"-2465.9\n",
"-2466.9\n",
"-2467.9\n",
"-2468.9\n",
"-2469.9\n",
"-2470.9\n",
"-2471.9\n",
"-2472.9\n",
"-2473.9\n",
"-2474.9\n",
"-2475.9\n",
"-2476.9\n",
"-2477.9\n",
"-2478.9\n",
"-2479.9\n",
"-2480.9\n",
"-2481.9\n",
"-2482.9\n",
"-2483.9\n",
"-2484.9\n",
"-2485.9\n",
"-2486.9\n",
"-2487.9\n",
"-2488.9\n",
"-2489.9\n",
"-2490.9\n",
"-2491.9\n",
"-2492.9\n",
"-2493.9\n",
"-2494.9\n",
"-2495.9\n",
"-2496.9\n",
"-2497.9\n",
"-2498.9\n",
"-2499.9\n",
"-2500.9\n",
"-2501.9\n",
"-2502.9\n",
"-2503.9\n",
"-2504.9\n",
"-2505.9\n",
"-2506.9\n",
"-2507.9\n",
"-2508.9\n",
"-2509.9\n",
"-2510.9\n",
"-2511.9\n",
"-2512.9\n",
"-2513.9\n",
"-2514.9\n",
"-2515.9\n",
"-2516.9\n",
"-2517.9\n",
"-2518.9\n",
"-2519.9\n",
"-2520.9\n",
"-2521.9\n",
"-2522.9\n",
"-2523.9\n",
"-2524.9\n",
"-2525.9\n",
"-2526.9\n",
"-2527.9\n",
"-2528.9\n",
"-2529.9\n",
"-2530.9\n",
"-2531.9\n",
"-2532.9\n",
"-2533.9\n",
"-2534.9\n",
"-2535.9\n",
"-2536.9\n",
"-2537.9\n",
"-2538.9\n",
"-2539.9\n",
"-2540.9\n",
"-2541.9\n",
"-2542.9\n",
"-2543.9\n",
"-2544.9\n",
"-2545.9\n",
"-2546.9\n",
"-2547.9\n",
"-2548.9\n",
"-2549.9\n",
"-2550.9\n",
"-2551.9\n",
"-2552.9\n",
"-2553.9\n",
"-2554.9\n",
"-2555.9\n",
"-2556.9\n",
"-2557.9\n",
"-2558.9\n",
"-2559.9\n",
"-2560.9\n",
"-2561.9\n",
"-2562.9\n",
"-2563.9\n",
"-2564.9\n",
"-2565.9\n",
"-2566.9\n",
"-2567.9\n",
"-2568.9\n",
"-2569.9\n",
"-2570.9\n",
"-2571.9\n",
"-2572.9\n",
"-2573.9\n",
"-2574.9\n",
"-2575.9\n",
"-2576.9\n",
"-2577.9\n",
"-2578.9\n",
"-2579.9\n",
"-2580.9\n",
"-2581.9\n",
"-2582.9\n",
"-2583.9\n",
"-2584.9\n",
"-2585.9\n",
"-2586.9\n",
"-2587.9\n",
"-2588.9\n",
"-2589.9\n",
"-2590.9\n",
"-2591.9\n",
"-2592.9\n",
"-2593.9\n",
"-2594.9\n",
"-2595.9\n",
"-2596.9\n",
"-2597.9\n",
"-2598.9\n",
"-2599.9\n",
"-2600.9\n",
"-2601.9\n",
"-2602.9\n",
"-2603.9\n",
"-2604.9\n",
"-2605.9\n",
"-2606.9\n",
"-2607.9\n",
"-2608.9\n",
"-2609.9\n",
"-2610.9\n",
"-2611.9\n",
"-2612.9\n",
"-2613.9\n",
"-2614.9\n",
"-2615.9\n",
"-2616.9\n",
"-2617.9\n",
"-2618.9\n",
"-2619.9\n",
"-2620.9\n",
"-2621.9\n",
"-2622.9\n",
"-2623.9\n",
"-2624.9\n",
"-2625.9\n",
"-2626.9\n",
"-2627.9\n",
"-2628.9\n",
"-2629.9\n",
"-2630.9\n",
"-2631.9\n",
"-2632.9\n",
"-2633.9\n",
"-2634.9\n",
"-2635.9\n",
"-2636.9\n",
"-2637.9\n",
"-2638.9\n",
"-2639.9\n",
"-2640.9\n",
"-2641.9\n",
"-2642.9\n",
"-2643.9\n",
"-2644.9\n",
"-2645.9\n",
"-2646.9\n",
"-2647.9\n",
"-2648.9\n",
"-2649.9\n",
"-2650.9\n",
"-2651.9\n",
"-2652.9\n",
"-2653.9\n",
"-2654.9\n",
"-2655.9\n",
"-2656.9\n",
"-2657.9\n",
"-2658.9\n",
"-2659.9\n",
"-2660.9\n",
"-2661.9\n",
"-2662.9\n",
"-2663.9\n",
"-2664.9\n",
"-2665.9\n",
"-2666.9\n",
"-2667.9\n",
"-2668.9\n",
"-2669.9\n",
"-2670.9\n",
"-2671.9\n",
"-2672.9\n",
"-2673.9\n",
"-2674.9\n",
"-2675.9\n",
"-2676.9\n",
"-2677.9\n",
"-2678.9\n",
"-2679.9\n",
"-2680.9\n",
"-2681.9\n",
"-2682.9\n",
"-2683.9\n",
"-2684.9\n",
"-2685.9\n",
"-2686.9\n",
"-2687.9\n",
"-2688.9\n",
"-2689.9\n",
"-2690.9\n",
"-2691.9\n",
"-2692.9\n",
"-2693.9\n",
"-2694.9\n",
"-2695.9\n",
"-2696.9\n",
"-2697.9\n",
"-2698.9\n",
"-2699.9\n",
"-2700.9\n",
"-2701.9\n",
"-2702.9\n",
"-2703.9\n",
"-2704.9\n",
"-2705.9\n",
"-2706.9\n",
"-2707.9\n",
"-2708.9\n",
"-2709.9\n",
"-2710.9\n",
"-2711.9\n",
"-2712.9\n",
"-2713.9\n",
"-2714.9\n",
"-2715.9\n",
"-2716.9\n",
"-2717.9\n",
"-2718.9\n",
"-2719.9\n",
"-2720.9\n",
"-2721.9\n",
"-2722.9\n",
"-2723.9\n",
"-2724.9\n",
"-2725.9\n",
"-2726.9\n",
"-2727.9\n",
"-2728.9\n",
"-2729.9\n",
"-2730.9\n",
"-2731.9\n",
"-2732.9\n",
"-2733.9\n",
"-2734.9\n",
"-2735.9\n",
"-2736.9\n",
"-2737.9\n",
"-2738.9\n",
"-2739.9\n",
"-2740.9\n",
"-2741.9\n",
"-2742.9\n",
"-2743.9\n",
"-2744.9\n",
"-2745.9\n",
"-2746.9\n",
"-2747.9\n",
"-2748.9\n",
"-2749.9\n",
"-2750.9\n",
"-2751.9\n",
"-2752.9\n",
"-2753.9\n",
"-2754.9\n",
"-2755.9\n",
"-2756.9\n",
"-2757.9\n",
"-2758.9\n",
"-2759.9\n",
"-2760.9\n",
"-2761.9\n",
"-2762.9\n",
"-2763.9\n",
"-2764.9\n",
"-2765.9\n",
"-2766.9\n",
"-2767.9\n",
"-2768.9\n",
"-2769.9\n",
"-2770.9\n",
"-2771.9\n",
"-2772.9\n",
"-2773.9\n",
"-2774.9\n",
"-2775.9\n",
"-2776.9\n",
"-2777.9\n",
"-2778.9\n",
"-2779.9\n",
"-2780.9\n",
"-2781.9\n",
"-2782.9\n",
"-2783.9\n",
"-2784.9\n",
"-2785.9\n",
"-2786.9\n",
"-2787.9\n",
"-2788.9\n",
"-2789.9\n",
"-2790.9\n",
"-2791.9\n",
"-2792.9\n",
"-2793.9\n",
"-2794.9\n",
"-2795.9\n",
"-2796.9\n",
"-2797.9\n",
"-2798.9\n",
"-2799.9\n",
"-2800.9\n",
"-2801.9\n",
"-2802.9\n",
"-2803.9\n",
"-2804.9\n",
"-2805.9\n",
"-2806.9\n",
"-2807.9\n",
"-2808.9\n",
"-2809.9\n",
"-2810.9\n",
"-2811.9\n",
"-2812.9\n",
"-2813.9\n",
"-2814.9\n",
"-2815.9\n",
"-2816.9\n",
"-2817.9\n",
"-2818.9\n",
"-2819.9\n",
"-2820.9\n",
"-2821.9\n",
"-2822.9\n",
"-2823.9\n",
"-2824.9\n",
"-2825.9\n",
"-2826.9\n",
"-2827.9\n",
"-2828.9\n",
"-2829.9\n",
"-2830.9\n",
"-2831.9\n",
"-2832.9\n",
"-2833.9\n",
"-2834.9\n",
"-2835.9\n",
"-2836.9\n",
"-2837.9\n",
"-2838.9\n",
"-2839.9\n",
"-2840.9\n",
"-2841.9\n",
"-2842.9\n",
"-2843.9\n",
"-2844.9\n",
"-2845.9\n",
"-2846.9\n",
"-2847.9\n",
"-2848.9\n",
"-2849.9\n",
"-2850.9\n",
"-2851.9\n",
"-2852.9\n",
"-2853.9\n",
"-2854.9\n",
"-2855.9\n",
"-2856.9\n",
"-2857.9\n",
"-2858.9\n",
"-2859.9\n",
"-2860.9\n",
"-2861.9\n",
"-2862.9\n",
"-2863.9\n",
"-2864.9\n",
"-2865.9\n",
"-2866.9\n",
"-2867.9\n",
"-2868.9\n",
"-2869.9\n",
"-2870.9\n",
"-2871.9\n",
"-2872.9\n",
"-2873.9\n",
"-2874.9\n",
"-2875.9\n",
"-2876.9\n",
"-2877.9\n",
"-2878.9\n",
"-2879.9\n",
"-2880.9\n",
"-2881.9\n",
"-2882.9\n",
"-2883.9\n",
"-2884.9\n",
"-2885.9\n",
"-2886.9\n",
"-2887.9\n",
"-2888.9\n",
"-2889.9\n",
"-2890.9\n",
"-2891.9\n",
"-2892.9\n",
"-2893.9\n",
"-2894.9\n",
"-2895.9\n",
"-2896.9\n",
"-2897.9\n",
"-2898.9\n",
"-2899.9\n",
"-2900.9\n",
"-2901.9\n",
"-2902.9\n",
"-2903.9\n",
"-2904.9\n",
"-2905.9\n",
"-2906.9\n",
"-2907.9\n",
"-2908.9\n",
"-2909.9\n",
"-2910.9\n",
"-2911.9\n",
"-2912.9\n",
"-2913.9\n",
"-2914.9\n",
"-2915.9\n",
"-2916.9\n",
"-2917.9\n",
"-2918.9\n",
"-2919.9\n",
"-2920.9\n",
"-2921.9\n",
"-2922.9\n",
"-2923.9\n",
"-2924.9\n",
"-2925.9\n",
"-2926.9\n",
"-2927.9\n",
"-2928.9\n",
"-2929.9\n",
"-2930.9\n",
"-2931.9\n",
"-2932.9\n",
"-2933.9\n",
"-2934.9\n",
"-2935.9\n",
"-2936.9\n",
"-2937.9\n",
"-2938.9\n",
"-2939.9\n",
"-2940.9\n",
"-2941.9\n",
"-2942.9\n",
"-2943.9\n",
"-2944.9\n",
"-2945.9\n",
"-2946.9\n",
"-2947.9\n",
"-2948.9\n",
"-2949.9\n",
"-2950.9\n",
"-2951.9\n",
"-2952.9\n"
]
},
{
"ename": "RecursionError",
"evalue": "maximum recursion depth exceeded while calling a Python object",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-29-43e3ad331761>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mcountdown\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3.1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-1-10499518927d>\u001b[0m in \u001b[0;36mcountdown\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 9\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0mcountdown\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"... last 1 frames repeated, from the frame below ...\n",
"\u001b[0;32m<ipython-input-1-10499518927d>\u001b[0m in \u001b[0;36mcountdown\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 9\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0mcountdown\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded while calling a Python object"
]
}
],
"source": [
"countdown(3.1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"In the same way, a `RecursionError` occurs if we call `factorial()` with `3.1` instead of `3`."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"ename": "RecursionError",
"evalue": "maximum recursion depth exceeded in comparison",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-30-188b816be8b6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3.1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-6-88d8d933f651>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 11\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"... last 1 frames repeated, from the frame below ...\n",
"\u001b[0;32m<ipython-input-6-88d8d933f651>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 11\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded in comparison"
]
}
],
"source": [
"factorial(3.1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The infinite recursions could easily be avoided by replacing `n == 0` with `n <= 0` in both functions and thereby **generalizing** them. However, even then, calling either `countdown()` or `factorial()` with a non-integer number is still *semantically* wrong.\n",
"\n",
"Errors as above are a symptom of missing **type checking**: By design, Python allows us to pass in not only integers but objects of any type as arguments to the `countdown()` and `factorial()` functions. As long as the arguments \"behave\" like integers, we do not encounter any *runtime* errors. This is the case here as the two example functions only use the `-` and `*` operators internally, and, in the context of arithmetic, a `float` object behaves like an `int` object. So, the functions keep calling themselves until Python decides with a built-in heuristic that the recursion is likely not going to end and aborts the computations with a `RecursionError`. Strictly speaking, a `RecursionError` is, of course, a *runtime* error as well."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Duck Typing"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The missing type checking is *100% intentional* and considered a **[feature of rather than a bug](https://www.urbandictionary.com/define.php?term=It%27s%20not%20a%20bug%2C%20it%27s%20a%20feature)** in Python!\n",
"\n",
"Pythonistas use the \"technical\" term **[duck typing <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Duck_typing)** to express the idea of two objects of *different* types behaving in the *same* way in a given context. The colloquial saying goes, \"If it walks like a duck and it quacks like a duck, it must be a duck.\"\n",
"\n",
"For example, we could call `factorial()` with the `float` object `3.0`, and the recursion works out fine. So, because the `3.0` \"walks\" and \"quacks\" like a `3`, it \"must be\" a `3`."
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6.0"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3.0)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We see similar behavior when we mix objects of types `int` and `float` with arithmetic operators. For example, `1 + 2.0` works because Python implicitly views the `1` as a `1.0` at runtime and then knows how to do floating-point arithmetic: Here, the `int` \"walks\" and \"quacks\" like a `float`."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3.0"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1 + 2.0"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3.0"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1.0 + 2.0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The important lesson is that we must expect our functions to be called with objects of *any* type at runtime, as opposed to the one type we had in mind when defining the function.\n",
"\n",
"Duck typing is possible because Python is a dynamically typed language. On the contrary, in statically typed languages like C, we *must* declare (i.e., \"specify\") the data type of every parameter in a function definition. Then, a `RecursionError` as for `countdown(3.1)` or `factorial(3.1)` above could not occur. For example, if we declared the `countdown()` and `factorial()` functions to only accept `int` objects, calling the functions with a `float` argument would immediately fail *syntactically*. As a downside, we would then lose the ability to call `factorial()` with `3.0`, which is *semantically* correct nevertheless.\n",
"\n",
"So, there is no black or white answer as to which of the two language designs is better. Yet, most professional programmers have strong opinions concerning duck typing, reaching from \"love\" to \"hate.\" This is another example of how programming is a subjective art rather than \"objective\" science. Python's design is probably more appealing to beginners who intuitively regard `3` and `3.0` as interchangeable."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Type Checking & Input Validation"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We use the built-in [isinstance() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#isinstance) function to make sure `factorial()` is called with an `int` object as the argument. We further **validate** the **input** by verifying that the integer is non-negative.\n",
"\n",
"Meanwhile, we also see how we manually raise exceptions with the `raise` statement (cf., [reference <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/reference/simple_stmts.html#the-raise-statement)), another way of controlling the flow of execution.\n",
"\n",
"The first two branches in the revised `factorial()` function act as **guardians** ensuring that the code does not produce *unexpected* runtime errors: Errors may be expected when mentioned in the docstring.\n",
"\n",
"So, in essence, we are doing *two* things here: Besides checking the type, we also enforce **domain-specific** (i.e., mathematical here) rules concerning the non-negativity of `n`."
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def factorial(n):\n",
" \"\"\"Calculate the factorial of a number.\n",
"\n",
" Args:\n",
" n (int): number to calculate the factorial for; must be positive\n",
"\n",
" Returns:\n",
" factorial (int)\n",
"\n",
" Raises:\n",
" TypeError: if n is not an integer\n",
" ValueError: if n is negative\n",
" \"\"\"\n",
" if not isinstance(n, int):\n",
" raise TypeError(\"Factorial is only defined for integers\")\n",
" elif n < 0:\n",
" raise ValueError(\"Factorial is not defined for negative integers\")\n",
" elif n == 0:\n",
" return 1\n",
" return n * factorial(n - 1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The revised `factorial()` function works like the old one."
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(0)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Instead of running into a situation of infinite recursion, we now receive specific error messages."
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "Factorial is only defined for integers",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-38-188b816be8b6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3.1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-35-54b57bc2107d>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 13\u001b[0m \"\"\"\n\u001b[1;32m 14\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Factorial is only defined for integers\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 16\u001b[0m \u001b[0;32melif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 17\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Factorial is not defined for negative integers\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: Factorial is only defined for integers"
]
}
],
"source": [
"factorial(3.1)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"ename": "ValueError",
"evalue": "Factorial is not defined for negative integers",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-39-b06b2cada645>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m42\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-35-54b57bc2107d>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 15\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Factorial is only defined for integers\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 16\u001b[0m \u001b[0;32melif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 17\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Factorial is not defined for negative integers\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 18\u001b[0m \u001b[0;32melif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 19\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mValueError\u001b[0m: Factorial is not defined for negative integers"
]
}
],
"source": [
"factorial(-42)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Forcing `n` to be an `int` is a very puritan way of handling the issues discussed above. So, we can *not* call `factorial()` with, for example, `3.0`."
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "Factorial is only defined for integers",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-40-32f1a9e8cf49>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3.0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-35-54b57bc2107d>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 13\u001b[0m \"\"\"\n\u001b[1;32m 14\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Factorial is only defined for integers\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 16\u001b[0m \u001b[0;32melif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 17\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Factorial is not defined for negative integers\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: Factorial is only defined for integers"
]
}
],
"source": [
"factorial(3.0)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Type Casting"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A similar way to prevent an infinite recursion is to **cast** the **type** of the `n` argument with the built-in [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) constructor."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def factorial(n):\n",
" \"\"\"Calculate the factorial of a number.\n",
"\n",
" Args:\n",
" n (int): number to calculate the factorial for; must be positive\n",
"\n",
" Returns:\n",
" factorial (int)\n",
"\n",
" Raises:\n",
" TypeError: if n cannot be cast as an integer\n",
" ValueError: if n is negative\n",
" \"\"\"\n",
" n = int(n)\n",
" if n < 0:\n",
" raise ValueError(\"Factorial is not defined for negative integers\")\n",
" elif n == 0:\n",
" return 1\n",
" return n * factorial(n - 1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The not so strict type casting implements duck typing for `factorial()` as, for example, `3.0` \"walks\" and \"quacks\" like a `3`."
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3)"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3.0)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"However, if we now call `factorial()` with a non-integer `float` object like `3.1`, *no* error is raised. This is a potential source for *semantic* errors as the function runs for invalid input."
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3.1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We could adjust the type casting logic such that a `TypeError` is raised for `n` arguments with non-zero decimals. "
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"code_folding": [],
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"def factorial(n):\n",
" \"\"\"Calculate the factorial of a number.\n",
"\n",
" Args:\n",
" n (int): number to calculate the factorial for; must be positive\n",
"\n",
" Returns:\n",
" factorial (int)\n",
"\n",
" Raises:\n",
" TypeError: if n cannot be cast as an integer\n",
" ValueError: if n is negative\n",
" \"\"\"\n",
" if n != int(n):\n",
" raise TypeError(\"n is not integer-like; it has non-zero decimals\")\n",
" n = int(n)\n",
"\n",
" if n < 0:\n",
" raise ValueError(\"Factorial is not defined for negative integers\")\n",
" elif n == 0:\n",
" return 1\n",
" return n * factorial(n - 1)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(3.0)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "n is not integer-like; it has non-zero decimals",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-47-188b816be8b6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3.1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-45-07dc981a3422>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 13\u001b[0m \"\"\"\n\u001b[1;32m 14\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"n is not integer-like; it has non-zero decimals\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 16\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 17\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: n is not integer-like; it has non-zero decimals"
]
}
],
"source": [
"factorial(3.1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"However, using built-in constructors for type casting leads to another subtle inconsistency. As constructors are designed to take *any* object as their argument, they do not raise a `TypeError` when called with invalid input but a `ValueError` instead. So, if we, for example, called `factorial()` with `\"text\"` as the `n` argument, we see the `ValueError` raised by [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) in a situation where a `TypeError` would be more appropriate."
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"ename": "ValueError",
"evalue": "invalid literal for int() with base 10: 'text'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-48-9a12eb120fc3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"text\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-45-07dc981a3422>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 12\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0mnegative\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \"\"\"\n\u001b[0;32m---> 14\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 15\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"n is not integer-like; it has non-zero decimals\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 16\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mValueError\u001b[0m: invalid literal for int() with base 10: 'text'"
]
}
],
"source": [
"factorial(\"text\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We could, of course, use a `try` statement to suppress the exceptions raised by [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) and replace them with a custom `TypeError`. However, now the implementation as a whole is more about type checking than about the actual logic solving the problem. We took this example to the extreme on purpose. In practice, we rarely see such code!"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"def factorial(n):\n",
" \"\"\"Calculate the factorial of a number.\n",
"\n",
" Args:\n",
" n (int): number to calculate the factorial for; must be positive\n",
"\n",
" Returns:\n",
" factorial (int)\n",
"\n",
" Raises:\n",
" TypeError: if n cannot be cast as an integer\n",
" ValueError: if n is negative\n",
" \"\"\"\n",
" try:\n",
" casted_n = int(n)\n",
" except ValueError:\n",
" raise TypeError(\"n cannot be casted as an integer\") from None\n",
" else:\n",
" if n != casted_n:\n",
" raise TypeError(\"n is not integer-like; it has non-zero decimals\")\n",
" n = casted_n\n",
"\n",
" if n < 0:\n",
" raise ValueError(\"Factorial is not defined for negative integers\")\n",
" elif n == 0:\n",
" return 1\n",
" return n * factorial(n - 1)"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "n cannot be casted as an integer",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-50-9a12eb120fc3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"text\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-49-9ed22b5a2981>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 15\u001b[0m \u001b[0mcasted_n\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 16\u001b[0m \u001b[0;32mexcept\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 17\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"n cannot be casted as an integer\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 18\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 19\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mcasted_n\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: n cannot be casted as an integer"
]
}
],
"source": [
"factorial(\"text\")"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "n is not integer-like; it has non-zero decimals",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-51-188b816be8b6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfactorial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3.1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-49-9ed22b5a2981>\u001b[0m in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 18\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 19\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mcasted_n\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 20\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"n is not integer-like; it has non-zero decimals\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 21\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcasted_n\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 22\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: n is not integer-like; it has non-zero decimals"
]
}
],
"source": [
"factorial(3.1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Which way we choose for **hardening** the `factorial()` function depends on the concrete circumstances. If we are the main caller of the function ourselves, we may choose to *not* do any of the approaches at all. After all, we should be able to call our own function in the correct way. The lesson is that just because Python has no static typing, this does *not* mean that we cannot do this \"manually.\" Yet, the idea behind a dynamically typed language is to *not* deal with the types too much at all."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"## Theory of Computation"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"With everything *officially* introduced so far, Python would be what is called **[Turing complete <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Turing_completeness)**. That means that anything that could be formulated as an algorithm could be expressed with all the language features we have seen. Note that, in particular, we have *not* yet formally *introduced* the `for` and `while` statements!"
]
}
],
"metadata": {
"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.8.6"
},
"livereveal": {
"auto_select": "code",
"auto_select_fragment": true,
"scroll": true,
"theme": "serif"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {
"height": "calc(100% - 180px)",
"left": "10px",
"top": "150px",
"width": "384px"
},
"toc_section_display": false,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Reference in a new issue View git blame Copy permalink