{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Programming with Python\n", "#### Vedran Šego, [vsego.org](http://vsego.org/)\n", "\n", "## Contents:\n", "\n", "1. What are algorithms and what are programs?\n", "\n", "2. Basic input and output\n", "\n", "3. Variables and operators" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## An algorithm\n", "\n", "* _A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer_
\n", " http://www.oxforddictionaries.com/definition/english/algorithm?q=algorithm\n", "* Informal definition from Wikipedia: *a set of rules that precisely defines a sequence of operations*.\n", "* More precisely (albeit still a bit unformal):
\n", " *A **sequence** of actions that are always executed in a **finite** number of steps, used to solve a certain problem.*\n", "* Simplified: a cookbook, often very general\n", "\n", "Important parts of an algorithm:\n", "\n", "1. get the input data,\n", "2. solve the problem,\n", "3. output the result(s)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Example:** preparing a frozen pizza. Steps:\n", " 1. Get temperature *temp* and time *t* (written on the box).\n", " 2. Heat oven to the temperature *temp*.\n", " 3. Discard all packaging (recycle the cartoon :-)).\n", " 4. Cook for a time *t*.\n", " 5. Get pizza out of the oven.
\n", " Use some heat-resistent hands protection or execute the \"go to the ER\" subroutine.\n", "\n", "Example of the input data:\n", "* *temp* = \"conventional oven: 190C; fan oven: 180C\",\n", "* *T* = between 15 and 17 minutes." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## A program\n", "\n", "* _A series of coded software instructions to control the operation of a computer or other machine._
\n", " http://www.oxforddictionaries.com/definition/english/programme\n", "* Simplified: precise instructions writen in some programming language" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Our focus\n", "\n", "* **Algorithms**, not programs!\n", "* We shall use programs to test algorithms and to see how they work.\n", "* **Aim:** Learn to solve problems using a computer, **regardless of the choice of language** (which may or may not be Python in the courses you take in your future work or studies)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Types of programming languages
(implementations)\n", "\n", "### Compiled\n", "* Require compilation (translation) of the code to the machine code (popular, albeit a bit meaningless, \"zeroes and ones\"),\n", "* Usually strictly typed,\n", "* Usually faster than interpreters.\n", "\n", "### Interpreted\n", "* Translated during the execution,\n", "* Usually untyped or loosly typed,\n", "* Usually slow(ish)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Where is Python?\n", "\n", "* Simplified: an interpreter.\n", "* Programs get semi-translated when run (_pseudocompiler_).\n", "* Untyped, slower than compiled languages (but with various ways to speed up).\n", "\n", "**No details** – too technical and they depend on the specific Python implementation." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Python versions\n", "\n", "Many implementations, but two major versions\n", " * Python 2\n", " * Python 3 \n", " \n", "Minor differences in what we need (they will be mentioned)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## An example: Hello world" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Hello, World!\n" ] } ], "source": [ "print(\"Hello, World!\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The output can be nicely formated, but more on that in the near future." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### What is \"Hello World\"?\n", "\n", "A very simple program, used to show the basic syntax of a programming language.\n", "\n", "See the [The Hello World Collection](http://www.roesler-ac.de/wolfram/hello.htm) for the examples in many other programming languages.\n", "\n", "The need for such an example can be clearly seen from the examples of more complex, but still fairly readable languages (for example, various versions of C++ and Java).
\n", "Beware of the Assembler-Z80-Console and BIT examples. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Note:** A full program should always start with the following:\n", "\n", "* the first line: #!/usr/bin/env python3 \n", " This has no meaning on Windows, but it makes your programs easier to run on Linux and Mac OSX.\n", "* Right after that, a description what they do, possibly with some other info (system requirements, authors name and contact, etc), between the triple quotation marks. This is called a *docstring* and it will be further addressed next week.\n", "\n", "So, a full \"Hello World\" program would look like this:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Hello, World!\n" ] } ], "source": [ "#!/usr/bin/env python3\n", "\n", "\"\"\"\n", "A program that prints the \"Hello, World!\" message.\n", "\"\"\"\n", "\n", "print(\"Hello, World!\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We shall ommit these elements in the lectures, as we shall mostly present chunks of code (that are not necessarily full programs) and to save the screen space." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The following line that Spyder adds to new files\n", "python\n", "# -*- coding: utf-8 -*-\n", "\n", "is not necessary in Python 3. However, if you are using international characters in some encoding other than UTF-8 (which you really shouldn't do!), this is a way to specify that encoding.\n", "\n", "In this course we shall not cover encodings, as it is a very technical subject and most of the time it is enough to just use UTF-8 (find it in your editor's settings). However, if you're ever to build an application with the need for the international characters, do look up the encodings on the internet (the [Wikipedia page](http://en.wikipedia.org/wiki/Character_encoding) is a good start) and use [UTF-8](http://en.wikipedia.org/wiki/UTF-8) whenever possible, as it is a widely accepted standard and the default in Python 3. You should also make sure that your editor saves files using the UTF-8 encoding (Spyder does that by default).\n", "\n", "In Python 2, the default encoding is [ASCII](http://en.wikipedia.org/wiki/ASCII) and the UTF-8 support has to be enabled manually." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Comments\n", "\n", "It is often useful to add human language notes in the code. These are called *comments* and are ignored by a computer, but they help programmers read the code.\n", "\n", "In Python, comments are done by prepending the hash sign # in front of it. Each comments ends with the end of the line.\n", "\n", "It is a standard to **always write comments in English**:\n", "> Python coders from non-English speaking countries: please write your comments in English, unless you are 120% sure that the code will never be read by people who don't speak your language \n", "> Source: [PEP 8](https://www.python.org/dev/peps/pep-0008/#id22)\n", "\n", "For example:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "\n", "\"\"\"\n", "A program that prints the \"Hello, World!\" message.\n", "\"\"\"\n", "\n", "# A welcome message\n", "print(\"Hello, World!\")\n", "# TODO: ask user their name and save it as a file" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As you can see, the above code runs just as the previous one, but a programmer reading it can get more information about the code itself.\n", "\n", "Some editors will recognize certain *tags* in comments and highlight them to make them more noticable (like the TODO tag in the previous example). Some of the more common ones are, as listed in the [Wikipedia's comments article](http://en.wikipedia.org/wiki/Comment_%28computer_programming%29#Tags):\n", "\n", "* FIXME to mark potential problematic code that requires special attention and/or review.\n", "\n", "* NOTE to document inner workings of code and indicate potential pitfalls.\n", "\n", "* TODO to indicate planned enhancements.\n", "\n", "* XXX to warn other programmers of problematic or misguiding code." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We shall often use the comments to denote what certain parts of the code do. These should always be descriptive and not merely rewritten code.\n", "\n", "For example, this is good:\n", "python\n", "# Get the sum of primes in L as prime_sum\n", "for x in L:\n", " if is_prime(x):\n", " prime_sum += x\n", "\n", "as it makes clear what the code is doing, even to someone who doesn't \"speak\" Python.\n", "\n", "This is bad:\n", "python\n", "# For each element x in the list, if x is a prime number,\n", "# add it to prime_sum.\n", "for x in L:\n", " if is_prime(x):\n", " prime_sum += x\n", "\n", "because this comment is just a rewrite of the code that follows it and, as such, it is useless." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "It is advisable to keep all lines (comments and docstrings) wrapped under 80 characters, although it shouldn't be forced when it reduces the code readability." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Input\n", "\n", "How do we **input** some data?\n", "\n", "Not surprisingly, using the function input()." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "17\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "The value of x is 17\n" ] } ], "source": [ "x = input()\n", "print(\"The value of x is\", x)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "Well, this x looks kinda important here. What could it be?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Variables\n", "\n", "* Used to store and retrieve data\n", "* Each has a value (which, in Python, *can* be undefined) and a type (partly hidden in Python)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Simple types\n", "\n", "* **Number** -- generally, what you'd consider an integer or a real number in mathematics.
\n", " For example: 17, -19, 17.19, 0, 2e3,...\n", "* **String** -- a text.
\n", " For example: \"word\", \"This is a mighty deep, philosophical sentence.\", \"ŞƿҿÇïåĿ sɹǝʇɔɐɹɐɥɔ\", \"17\",...
\n", " So called *empty string*, \"\", has no characters (its length is zero).\n", "* **Boolean** -- truth values (True and False).\n", "* **NoneType** -- the type of a special constant None that means \"no value\".
\n", " This is **not** a zero (a number), nor an empty string, nor anything else! None is different from any other constant and any other value that a variable can get.\n", "\n", "**Be careful:** 17 is a number, while \"17\" is a string!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Some not so simple types\n", "\n", "* Lists and tuples - most languages have only lists (usually called *arrays*),\n", "* Dictionaries,\n", "* Sets,\n", "* Objects,\n", "* Functions (yes, functions can be saved in variables as well),
\n", " ...\n", "\n", "More on these in the near future." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## How do variables work?\n", "\n", "Let us analize this piece of code:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "a mistery\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "The value of x is a mistery\n" ] } ], "source": [ "x = input()\n", "print(\"The value of x is\", x)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Whatever is on the right hand side of the assignment = gets computed first. Then the result is assigned to the variable on the left hand side. When this is done, the next line of code is executed." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In our example, this means:\n", "\n", "1. The function input() reads a sequence of characters from the standard input (usually user's keyboard, although it can be changed) and returns it as a **string**.\n", "2. That value is then assigned to the variable x (on the lefthand side of the assignment operator =).
\n", " Now, x holds - as a string - whatever we have typed up to the first newline, i.e., up to the first Enter key (the newline itself is omitted).\n", "3. The function print() now outputs its arguments to the standard output (usually the user's screen), in order in which they were given, separated by a single space character. So,\n", " * First, a string \"The value of x is\" is written out.\n", " * Then a singe space character is written out.\n", " * Then the value of x is written out (**not** the string \"x\" itself, because x is a variable!)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In other words, if we type \"17\", our program will write\n", "\n", " The value of x is 17\n", "\n", "And if we type \"a mistery\", our program will write\n", "\n", " The value of x is a mistery\n", "\n", "Don't expect Python to do anything *smart* here. It just writes out the values as they were given." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Python 2 remark:** In Python 2, print does not need parentheses (i.e., print \"Hello, World!\" is fine).
\n", "However, do include them even if writing a Python 2 program, to make it easier to port to Python 3, as well as to avoid problems in some more advanced uses you might encounter in the future." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## On the simple types\n", "\n", "**Be careful!** If it *looks* like a number, it *may* still **not be** one!\n", "\n", "Let us try to input two numbers in the following code, also adding the descriptions of what is expected in each of the inputs:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x: 17\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "y: 19\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "17 + 19 = 1719\n" ] } ], "source": [ "x = input(\"x: \")\n", "y = input(\"y: \")\n", "print(x, \"+\", y, \"=\", x+y)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### What did just happen here?\n", "\n", "The user types two numbers, which are saved -- as two **strings** -- in variables x and y. Then the program writes out (among other things) the value of x+y.\n", "\n", "How would we \"add\" one string to another in the real world?\n", "\n", "For example, if x = \"Bruce\" and y = \"Wayne\", what would x + y be?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "It may come as a little surprise that \"x + y\" will **not** produce \"Batman\". Python is a well defined language that keeps Bruce's secret identity well hidden.\n", "\n", "The result of x+y would, less surprisingly, be \"BruceWayne\". Notice that there is no additional space here: the strings are *glued* (concatenated) one to another, with no extra separators!\n", "\n", "So, what happens if x = \"17\" and y = \"19\"?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It would be very bad if Python looked at these and decided that they were numbers only because they have nothing but digits. Maybe we want them concatenated (as opposed to adding them one to another)!\n", "\n", "So, the result is -- by now not a bit surprisingly -- \"1719\", because the strings' addition + is a concatenation, regardless of the value of the strings in question.\n", "\n", "[![7+3=73](files/73.png)](http://www.gocomics.com/calvinandhobbes/1985/11/21)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "How do we explain Python to \"treat these two as numbers\"?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Converting basic types\n", "\n", "We can explicitly tell Python to convert a string to an integer or a real number, and vice versa." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "17\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "1.23\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "x = 17\n", "y = 1.23\n", "x+y = 18.23\n", "This is a string: \"18.23\"\n" ] } ], "source": [ "x = int(input())\n", "y = float(input())\n", "print(\"x = \", x)\n", "print(\"y = \", y)\n", "print(\"x+y = \", x+y)\n", "z = 'This is a string: \"' + str(x+y) + '\"'\n", "print(z)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "We see three conversion functions:\n", "* int(), which takes a string and converts it to an integer. If the argument is not a string representation of an integer, an error occurs.\n", "* float(), which takes a string and converts it to a \"real\" number (also called *floating point number*, hence the name of the function). If the argument is not a string representation of a real number, an error occurs.\n", "* str(), which takes a number (among other allowed types) and converts it to a string." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Python 2 remark:** In Python 2, input() is similar to float(input()) in Python 3 (actually, eval(input()), but that is well beyond this lecture), i.e., it loads a number and returns it as a floating point number (causing an error or a strange behaviour if anything else is given as the input). \n", "To load a string in Python 2, one has to call raw_input() (which does not exist in Python 3).\n", "\n", "**A note on the string creation:** There are better ways to form the variable z (using various *formatting* methods), but this will have to wait a few weeks until we cover strings in more depth than here." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## More on the assignments\n", "\n", "What will the following code print?" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The value of x was 17\n", "The value of x is 19\n" ] } ], "source": [ "x = 17\n", "print(\"The value of x was\", x)\n", "x = x + 2\n", "print(\"The value of x is\", x)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As we said before: whatever is on the right hand side of the assignment =, gets computed **first**. Only **after that**, the result is assigned to the variable on the left hand side.\n", "\n", "So, when Python encounters the command\n", "\n", "python\n", "x = x + 2\n", "\n", "\n", "while the value of x is 17, it first computes x + 2 (for x = 17), which is 19. After that, it preforms the assignment x = 19, so 19 becomes the **new value** of x (which is then printed with the second print)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In most of the modern languages, x = x + y can be written as x += y. The same shortcut works for other operators as well, i.e., x = x op y can be written as x op= y.\n", "\n", "For basic numerical operations, this means that we have the following translation:\n", "\n", "Expression | Shortcut\n", ":-----------:|:-------:\n", "x = x + y | x += y\n", "x = x - y | x -= y\n", "x = x * y | x *= y\n", "x = x / y | x /= y\n", "x = x // y | x //= y\n", "x = x % y | x %= y\n", "x = x ** y | x **= y\n", "\n", "**A note on other languages:** there are no increment (++) and decrement (--) operators in Python." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Some special operators\n", "\n", "Most of the operators from the previous slide have the same meaning as in mathematics (**@C-people:** / means the *usual*, i.e., real division). The three not used in mathematics are defined as follows:\n", "\n", "* x // y means floored quotient of x and y (also called *integer division*), i.e., x // y $:= \\left\\lfloor \\mathsf{x}\\ /\\ \\mathsf{y} \\right\\rfloor$,\n", "* x % y means the remainder of $x / y$, i.e., x % y := x - y * (x // y),\n", "* x ** y means $x^y$ (x to the power y)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Python 2 remark:** In Python 2, the ordinary real division x/y works in a C-like manner, which means that x/y is equivalent to x//y if both x and y are integers.
\n", "In Python 3, x/y always means real division. In other words,\n", "\n", "* Python 2: 3//2 = 3/2 = 1, but 3/2.0 = 3.0 / 2 = 3.0 / 2.0 = 1.5;\n", "* Python 3: 3//2 = 1, but 3/2 = 3/2.0 = 3.0 / 2 = 3.0 / 2.0 = 1.5." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Real number trouble\n", "\n", "When dealing with real numbers, one must be extremely careful!\n", "\n", "### Simple arithmetics\n", "\n", "What happens when we try to compute a + b - a for several different real values of a and b? Fairly often, the result will **not** be b!" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "a = 10 b = 0.1 -> a + b - a = 0.09999999999999964 != 0.1 = b\n", "a = 10000000 b = 1e-07 -> a + b - a = 1.0058283805847168e-07 != 1e-07 = b\n", "a = 100000000000 b = 1e-11 -> a + b - a = 0.0 != 1e-11 = b\n" ] } ], "source": [ "a = 10\n", "b = 0.1\n", "print(\"a =\", a, \" b =\", b, \" -> \", \"a + b - a =\", a + b - a, \"!=\", b, \"= b\")\n", "a = 10**7\n", "b = 10**(-7)\n", "print(\"a =\", a, \" b =\", b, \" -> \", \"a + b - a =\", a + b - a, \"!=\", b, \"= b\")\n", "a = 10**11\n", "b = 10**(-11)\n", "print(\"a =\", a, \" b =\", b, \" -> \", \"a + b - a =\", a + b - a, \"!=\", b, \"= b\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### A division\n", "\n", "There is no such thing as a *real* number in a computer. There are all actually (something like) decimals with an upper limit to the number of correctly remembered digits. The rest of the digits is lost, which can produce weird results, like x * (1 / x) ≠ 1." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.9999999999999999\n" ] } ], "source": [ "x = 474953\n", "y = 1 / x\n", "print(x * y)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Use integers whenever possible\n", "\n", "Fibonacci numbers are defined as follows:\n", "$$F_0 := 0, \\quad F_1 := 1, \\quad F_{n+1} := F_n + F_{n-1}, \\quad n \\ge 1.$$\n", "There is also a direct formula for computing $F_n$:\n", "$$F_n = \\frac{\\varphi^n - \\psi^n}{\\sqrt{5}}, \\quad \\varphi := \\frac{1 + \\sqrt{5}}{2}, \\quad \\psi := \\frac{1 - \\sqrt{5}}{2}.$$\n", "However, in a computer, this will soon give you wrong results.\n", "\n", "In the following code, fib1(n) returns the n-th Fibonacci number computed by a simple integer-arithmetics algorithm, while fib(2) uses the above formula (never use the recursive definition for computation of Fibonacci numbers!)." ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Type n (try to go for 73 or more): 100\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "|fib1(n) - fib2(n)| = |354224848179261915075 - 354224848179263111168| = 1196093\n" ] } ], "source": [ "def fib1(n):\n", " f0 = 0\n", " f1 = 1\n", " while n > 1:\n", " (f0, f1) = (f1, f0 + f1)\n", " n -= 1\n", " return f1\n", "\n", "def fib2(n):\n", " sqrt5 = 5 ** .5\n", " phi = (1 + sqrt5) / 2\n", " psi = (1 - sqrt5) / 2\n", " return int((phi**n - psi**n) / sqrt5)\n", "\n", "n = int(input(\"Type n (try to go for 73 or more): \"))\n", "fib1n = fib1(n)\n", "fib2n = fib2(n)\n", "print(\"|fib1(n) - fib2(n)| = |\" + str(fib1n), \"-\", str(fib2n) + \"| =\", abs(fib1n - fib2n))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Even a simple addition\n", "\n", "The following code computes and prints three sums:\n", "$$\\sum_{i = 0}^{999} 0.1 = 100, \\quad \\sum_{i = 0}^{9999} 0.1 = 1000, \\quad \\text{and} \\quad \\sum_{i = 0}^{9999999} 0.1 = 10^6.$$" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "99.9999999999986\n", "1000.0000000001588\n", "999999.9998389754" ] }, { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "s = 0\n", "for _ in range(1000):\n", " s += 0.1\n", "print(s)\n", "s = 0\n", "for _ in range(10000):\n", " s += 0.1\n", "print(s)\n", "s = 0\n", "for _ in range(10000000):\n", " last = s\n", " s += 0.1\n", "print(s)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "Notice how the result is sometimes smaller and sometimes bigger than the correct result." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Associativity of addition\n", "\n", "We all know that for a finite set of real numbers $\\{ a_1, \\dots, a_n \\}$, the following is true:\n", "$$\\sum_{i=1}^n a_i = \\sum_{i=n}^1 a_i = \\sum_{i=1}^n a_{P(i)},$$\n", "for any permutation $P$. However, in a computer, this isn't always so." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "sin1 = -3121.3699495895926\n", "sin2 = -2947.8076865687467\n", "sin3 = -2403.8076865683283\n", "sin4 = -1768.0\n", "|sin1 - sin4| = 1353.3699495895926\n", "the first element: 47.12388980384689\n", "the last element: 5.3966776616824465e-12\n" ] } ], "source": [ "from math import pi\n", "x = 15 * pi\n", "# Create the list of series elements\n", "elts = [ ]\n", "f = 1\n", "for k in range(1, 150, 2):\n", " elts.append(x**k / f)\n", " f *= -(k+1) * (k+2)\n", "# Summarize elements in the original order\n", "sin1 = 0\n", "for el in elts:\n", " sin1 += el\n", "print(\"sin1 =\", sin1)\n", "# Summarize elements in the reversed order\n", "sin2 = 0\n", "for el in reversed(elts):\n", " sin2 += el\n", "print(\"sin2 =\", sin2)\n", "# Summarize elements from the middle one to the ones on the edge\n", "cnt = len(elts)\n", "mid = cnt // 2\n", "sin3 = 0\n", "for i in range(mid + 1):\n", " if mid + i < cnt:\n", " sin3 += elts[mid + i]\n", " if i:\n", " sin3 += elts[mid - i]\n", "print(\"sin3 =\", sin3)\n", "# Summarize elements from the ones on the edge to the middle one\n", "sin4 = 0\n", "for i in reversed(range(mid + 1)):\n", " if mid + i < cnt:\n", " sin4 += elts[mid + i]\n", " if i:\n", " sin4 += elts[mid - i]\n", "print(\"sin4 =\", sin4)\n", "print(\"|sin1 - sin4| =\", abs(sin1 - sin4))\n", "print(\"the first element:\", elts[0])\n", "print(\"the last element:\", elts[-1])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The above is the computation of $\\sin 15\\pi$ via the first $74$ elements of the [Taylor series](http://en.wikipedia.org/wiki/Sine#Series_definition) of the sine function,\n", "* sin1 computation starting from the first element,\n", "* sin2 going towards it,\n", "* sin3 going from the center out ($a_{37} + a_{36} + a_{38} + a_{35} + a_{39} + \\dots$),\n", "* sin4 going from the edges in ($a_1 + a_{74} + a_2 + a_{73} + \\dots$).\n", "\n", "The difference between sin1 and sin4 is roughly $1353$, which may not look like much, but it is far more than the difference between any two sines should be.\n", "\n", "You might also notice that $\\sin 15\\pi$ shouldn't be nowhere near $-3000$ or even $-1768$.\n", "\n", "One might think that we should compute more elements of the sum, but this is not the case: the last element of the sum is only around $5.4 \\cdot 10^{-12}$ (and those after it would be even smaller)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "So, what happened here?\n", "\n", "Here is a hint: take a look at how big the elements of our sums are." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEGCAYAAACJnEVTAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X2QHPV95/H37INWWmnRI0gIyYjsggscfMBZAgM2Y/Mk\nwOAjB4dJfDa+inHljJPj4gSbkGK3Kpzju6qU42ByOhcQ7EuwEwIqKTwYyWZsuXwGZCSQBbIeiBRJ\n6GkR6GF30e5q5/74dTO9vf00070z3T2fV9WUeqZ7t38S7Ge++/39ugdERERERERERERERERERERE\nRERERKSJPAIcADZFOPbjwCvACPAfXfu+aX2PTcB/SnKAIiKSnI8BFxIt9M8EzgceY3zo3wA8D7QA\nncBLQFeywxQRya6WRg/AYR3wjuu1buBZYD3wM+CD1uu7MG8OY67jz7WOGwMGgdeA5ZM0XhGRzElT\n6Hv5P8BXgI8AfwI8FHL8q5iQnwbMAz4BLJrMAYqIZElbowcQYAbwUeCfHK9NCfmaNcBS4BfAIeD/\nMfG3ARGRppXm0G8B3sX0+YOUXc//h/UA+HvgNwmPS0Qks+K2dxYDLwCbgV8Df+hz3LeBbZj2S1iI\n244C/wrcYj0vAB92HVOwHrYWYK61/WHr8XzE84mISIgFwAXW9gxMVX2u65jrgWes7YuBX/p8r8eB\nt4BhYDfwBWAJZiJ3I+aN5T7r2KXWMceBfiorfqZax23GtHjcbxIiIpKglcCVrtf+N3Cb4/kWYH7d\nRiQiIu9LcvXOEkzr5kXX62dgqnLbHrSiRkSkIZIK/RnAE8AfYVoubgXXc/fkq4iI1EESq3fagX8G\n/i+mveO2FzPha1tkvTZOd3d3eceOHQkMR0SkqewAeqIeHLfSLwAPA68D3/I5ZhXwOWv7EswyzAPu\ng3bs2EG5XE794/7772/4GPIwRo1T40z7IyvjxNy5ILK4lf5lwGcxtzvYYL12L/ABa3sFZuXO9cB2\nYACzKkdERBogbuj/nGi/LdwV8zwiIpKAtN97J3WKxWKjhxAqC2MEjTNpGmeysjLOarlX1TRS2epP\niYhIRIVCAarIclX6IiJNRKEvItJEFPoiIk1EoS8i0kQU+iIiTUShLyLSRBT6IiJNRKEvItJEFPoi\nIk1EoS8i0kQU+iIiTUShLyLSRBT6TahUgsOHGz0KEWkEhX4TeuAB+MUvGj0KEWkEhX4TGh6GkZFG\nj0JEGkGh34SGh83Dz+bN8L3v1W88IlI/Cv0mFBb6r7wCq1bVbzwiUj9JhP4jwAFgk8/+InAE88Hp\nG4D7EjinxBDW3hkehhMn6jceEamfuB+MDvAo8DdAUEPgp8BNCZxLEhBW6Y+MBO8XkexKotJfB7wT\nckyaPou36YWFfth+EcmuevT0y8ClwKvAM8B5dTinBDhxIjz01d4Ryack2jthXgEWA4PAdcBK4Jw6\nnFd8ROnpq9IXyad6hP4xx/azwEPAHGDCNaG9vb3vbxeLRYrF4iQPrTlFae+o0hdJp1KpRKlUqvnr\n6xH684GDmDbPMkx/3/MmAM7Ql8mjiVyR7HIXxH19fVV9fRKh/zhwBTAP2A3cD7Rb+1YAtwB/AIxi\nWjyfSeCcUqNyWRO5Is0sidC/PWT/d6yHpMDJkyb4tU5fpDnpitwmY1fwqvRFmpNCv8nYFbwmckWa\nk0K/ydhhryWbIs1Jod9korR37NU75XJ9xiQi9aPQbzJRe/qge+6L5JFCv8lUE/pq8Yjkj0K/yUTt\n6YMmc0XySKHfZFTpizQ3hX6Tibpk03msiOSHQr/JDA9DZ2f46h37WBHJF4V+kxkehunTo/X0Ffoi\n+aPQz6Hjx/33DQ/DjBnh7Z2pU9XeEckjhX7OvP02/PZv++8fHoaurvDQDztGRLJJoZ8zR47AYc9P\nKzCiVvrTp6vSF8kjhX7ODA0Fh3WUnv7ISPgbg4hkk0I/Z4aGTFiPjXnvP3EiWqWv9o5IPin0c2Zo\nyPzpF9hR2zszZgT/xnDOObo3j0gWKfRzZnDQ/OkX2Haghy3ZDKr0x8Zg2zYYGIg3VhGpP4V+ztiV\nfljo+wW6/VGKQRO59uv2G4yIZEcSof8IcADYFHDMt4FtwKvAhQmcU3xECf1p08z2yZMT94+MQFsb\ndHT4vzG89974c4lIdiQR+o8CywP2Xw/0AGcDdwJ/m8A5xYcdxHYwuw0Pw5Qp5uEV6iMjZl+U0Fel\nL5I9SYT+OuCdgP03AY9Z2y8Cs4D5CZxXPESp9KdMgfZ2776+801B7R2R/KlHT/8MYLfj+R5gUR3O\n25TCJnJPnAiu9O3QV6Uvkk9tdTpPwfXc89NXe3t7398uFosUi8XJG1FORa30w0Jflb5IOpVKJUql\nUs1fX4/Q3wssdjxfZL02gTP0pTZJhH57u9nvtyRTE7kijeMuiPv6+qr6+nq0d1YBn7O2LwHexaz2\nkUkQdSI3rKev9o5IPiVR6T8OXAHMw/Tu7wfarX0rgGcwK3i2AwPAFxI4p/iIUul3dISv3lF7RySf\nkgj92yMcc1cC55EIolyRq4lckealK3JzZmgo+ANQnKFf65JN9fRFskuhnzNDQzBrVviSzfb28NU7\nfpW+2jsi2aXQzxk79Gu9ItdevaP2jkg+KfRzZnAwuNKPehuGsInctjaFvkgWKfRzZmgIZs+O39MP\nq/Rnz1ZPXySLFPo5EyX0Ozqi9fSDJnLnzFGlL5JFCv2cCZvIreY2DEETubNnK/RFskihnzNJTORG\nbe8o9EWyR6GfM4ODwe0d55JNv56+fe8dtXdE8kehnyPlsgnkJFbvBFX6dntHE7ki2aPQzxF7KWVn\n5+TeWlmVvkh2KfRzZGjIfP5tR8fkT+Qq9EWySaGfI0NDpsr3C/1yudK+iXtrZU3kimSTQj9HBgcr\nlb7X6p2RERP2hUK0D1EJau+opy+STQr9HLHbO3532bSreIi3ZPPECejqgrEx798WRCS9FPo5EtbT\nt5drgv9tGJztn+Fh0xJye+8988bS2alqXyRrFPo5EtbTd1b6YbdhaGkxK4G83hjs0J82TX19kaxR\n6GfM8ePwzjve+5w9/bjtHfBv8Zw4YfZ1dir0RbJGoZ8x3/kOPPCA9z5ne8drIrfa0PebzI3S3nng\nAVi9OvzvIyL1lUToLwe2ANuAezz2F4EjwAbrcV8C52xa+/f7V/phPX37DpsQfGvldutj7YMqfTv0\n/Sr9116DzZvD/z4iUl9xPxi9FXgQuArYC7wMrALecB33U+CmmOcSoL/ffyml3dOPsnrHr6dvT+RC\ncKUf1t45dsyMVUTSJW6lvwzYDuwERoAfAJ/2OK4Q8zxi6e83geolSqVfbXvH65goE7lHjyr0RdIo\nbuifAex2PN9jveZUBi4FXgWeAc6Lec6mduiQf+iHTeS6l2zWMpFbLo+fyPXr6avSF0mnuO0dj1Xc\nE7wCLAYGgeuAlcA5Xgf29va+v10sFikWizGHlz/9/TBzpvc+u9JvazPhPDpqtm3uKj7oNgz2Me43\nj9FRs5yztTW4vXP0KLz9dnV/NxEJVyqVKJVKNX993NDfiwl022JMte/krEufBR4C5gCH3d/MGfri\nrb/fhK4X+wNUoFLt+4V+2Dp9+3u4j7FbOxDe02+L+3+XiEzgLoj7+vqq+vq47Z31wNnAEmAKcBtm\nItdpPpWe/jJre0LgS7ihIRgYCO7pd3aaba/J3Kg9fXv1jlelb7d2ILinr/aOSDrFrcVGgbuAH2FW\n8jyMWbnzJWv/CuAW4A+sYweBz8Q8Z9Pq7zc3Ogvr6YN3Xz/Kkk336p1aKv0TJ8x9eY4fr9zkTUTS\nIYlfwJ+1Hk4rHNvfsR4SU38/LF5s1r97hand0wf/0I/b3nFW+n4TuceOwSmnmL7/4cMwf351f08R\nmTy6IjdDDh2CU0+FGTO8q3136Luvyk3iitwolf7Ro+YunPPmqcUjkjYK/Qzp7zeh39XlH/p2T9+r\n0k9iyWaU0LcrfYW+SPoo9DOkv98EaVDo25V+lIncsNsw1DqRq0pfJL0U+hly6FBw6EeZyE16yWZQ\nT1+hL5I+Cv0MidLeiRr6fu2dJFbvqNIXSS+FfoZU097xm8h1LtmsZSLXvXonrKevq3JF0kWhnyFh\n7Z2widywnn65PH4paFh7Rz19kexR6GdIku0dr8/AtQO/YF0/HaXSV09fJFsU+hkS1t5xTuSGrd4p\nFMy9cUZHx+93XvBV65JNu9KfO1ehL5I2Cv2MGBsz/fG5c71Df2ys8olWEL5OHyb29Z2TuF77Ibl1\n+uWy/+0kRGTyKPQz4sgRmD7dBLFX6NthbN+BM6y9AxP7+l77a5nIjdLT//nP4cor/f++IjI5FPoZ\nYbd2wDv0nf18CL8NA0xcq+/eX+tErl3pn3KKOd7rA122bYMNG/w/hEVEJodCP2VuvRX+7d8mvm6v\n3AHv0Hf28yH8LpswsX0TpdJ3hn5Hh/lN4eTJ8cccO2bGWCiYdpTXss1du8x8wsaNE/eJyORR6KfI\ngQPwxBPeQVhtpR82kQvh7Z2wu2wWCt4reI4eNVU++Ld4du40f4+XX564T0Qmj0I/RX78Y/Pnjh0T\n99nLNSF6eycs9L3aO87VO2ETueDd17crffAP/V274MYbFfoi9abQT5E1a+Ccc7xDP6y947wwC6JP\n5Iat3gmayAXvvr49kQvBlf6ttyr0RepNoZ8S5TKsXQtf+pJ/pR93IjdsyWa1E7ng3d6xJ3LB+1YM\no6Owbx9cey3s2WNWJolIfSj0U+I3vzE98uuvh+3bJ+4Pa+9EnciNu2QzrL1jf1Si/duAV6W/dy+c\ndpoZ7wUXwPr1E/++IjI5FPopsXYtXHUVnHUW7N49/kpZ8G7vOG+hUMtEbi1LNt3tHXfo21W+fSsH\nr9DftQvOPNNsL13q3+I5fHj831FE4ksi9JcDW4BtwD0+x3zb2v8qcGEC58ydNWvg6qtNoJ52mgl+\nJ2d7Z8oU8/mzzvZN1J5+2JLNaidy3T19Zz8fvG/FsHMnLFlitpct8w79oSHo7oaHH564T0RqFzf0\nW4EHMcF/HnA7cK7rmOuBHuBs4E7gb2OeM7MOH4af/nTi6yMj5nX7CtWenoktHmd7Bya2eGpZvVPr\nOv0olb6t1kp/5UpzzNe/blpfIpKMuKG/DNgO7ARGgB8An3YdcxPwmLX9IjALmB/zvJnz3HPw4Q+b\nZYpbt47f9/LLpvI97TTzvLt74mSus70D0UI/7Ipcd0/fvXrHr70TNJHrrvS9Qt9Z6Xd3w/HjsH//\n+GP+7u/ga1+Dvj74vd/zvvf/kSNmQlhEomuL+fVnAM5GxB7g4gjHLAIOuL/Z6tUxRzMJymXzGBsz\nz9vaTAukvd1sHz9uVqfYj/nz4eMfh/PPN/fBGRiAr34VnnkGvvc9eOUVuPtuePrpyjns1o7NHfrD\nw6aanjmz8po79GuZyA3r6dcykRu10r/tNrNdKMBHPmLe+G680by2d6+Z3F250pzruefgz/8cvvnN\nyvdYvdqsdBoagnPPhd/5Hbj5Zvit3zL/HbZvN499+8w9i2bONI+uLvPfcni48gDTLmtpqdy7CCr/\n7b3YcxYifjo64JprGj2KieKGftRpNvePiOfX/fEf976/PXdukXnzijUNKinlsvnhbmmp/JCPjpqK\neGTEbM+YYfrWc+fCnDnw2mvw4IOmMr/8cnjjDbjsMvP6zJnmte9+14T+DTeY77l2Ldx3X+W8PT3w\n0kuV5/bdNZ2BVEt7J4klm2ETuVErfbu9A5UWjx363/8+3HJL5e/z8MNmlc+115pj774bfvIT+OEP\n4eKL4YUX4Mknzb/zwIAJ8LPPNv+OCxea8R05Yh7Hjpn9U6aYh/35ASdPmjcD+5YS9n/vQmFiwGty\nWaKYNWtyQr9UKlEqlWr++rihvxdY7Hi+GFPJBx2zyHptgq1be2MOJz3274d160zVe+21ldenTIG/\n/mv4ylfMap3hYXPbhY99rHJMd/f4nr67tQPeoe/s+SdxG4ZaJnLdlf706SZIBwfNG8TYmFmb/4EP\nVI5ZuhRWrDDb5bJp7Tz6aGX/qaea55/7nBnTlVfCq69W3lyuvdY8HnrIBPvs2arEJb+KxSLFYvH9\n5319fVV9fdzQX4+ZoF0CvAXchpnMdVoF3IXp918CvItHaydvFiwwV5x6Wb7ctCS+9S340IfMChbn\nypvubnjzzcpvGs6VO7bJmsh1r96J0t4J6ukXCpULtDo7Tbtl1qzxY122DH7/983f96WXzBvDJZeM\nP+8115hJ3TPPhE99Ck+trea3LRHxFzf0RzGB/iPMSp6HgTeAL1n7VwDPYFbwbAcGgC/EPGcu/NVf\nmWD7xCdMxe90yikmIA8cMG8e7pU7EK2n75zItdsXbY7/4u6eftSJXHd75+DBynN3pQ+V0F+82PTz\n7Ulc28KF5nvu3Gmq/Dvu8K7Uv/zlia+JSHXihj7As9bDaYXr+V0JnCdXenrgzjvhG9+AezyubrBb\nPHbox6307UB3hmlYT9/5Obr210WZyD399PFjdfb13f1829Kl8LOfwT/+o263LDKZkgh9qdG995qJ\nxws9LlezV/Bcfnn0nn7QxVnuQIfwnn5Liwl++w3DXvXiPMbr4qwPfnD8eZyh71Xpgwn9v/gLuOgi\n8xuBiEwO3YahgWbMMJO6ra0T9zmXbUZp74TdhsEr9MOWbML43wbsK3qdvy14VfrOnj5Er/S3bzet\nHRGZPAr9lOrpGR/61bZ37LC2lxe6l2s6j7G5J3LtY+w3D3drB8IncmH8rRiCKv2eHrPWXkQmj0I/\npZzLNqO0d9wTuS0tZtLWWaVHCX33Mc7JXPckLoRfnAXRKv3Zs83n5jpbVCKSPIV+SsVt78D4vn6U\nnr579Y59TFilH3RxFlRCv1w2n//rFfoiUh8K/ZQ67TQTtu++G729466S3aHvrtKj9PSdlb5X6Idd\nnAWV0D940Ixxxgz/v7eITC6FfkoVCpVqP+rqnVoq/Womcv3aO2E9fTv0/fr5IlI/Cv0U6+42a9bb\n2ycGepTQd67giRP61bR3gip9v36+iNSPQj/FenrgxRcnVvkQPpEL46/KjbpO3716x93eCZrIdX9U\nom3uXHNFrkJfpPEU+inW3Q2//GV46J88ae746Q5bZ3vHa8lm1HX6zu8R1NN3f1SirbPTrCZ6/XW1\nd0QaTaGfYt3d8OtfT1y5A2YydHDQVNZ2a8cdttX29L1W74RN5NotpLEx736+bd48+NWvVOmLNJpC\nP8W6u80yR69Kv7XVBP3AgHc/H6pfshmlp+/+baKlxQT/e+959/Nt8+ap0hdJA917J8UWLzYtGK/Q\nh0qLZ2TEO/TdE7nuwK5l9Y670odKXz+s0h8bU6Uv0mgK/RRrbYWzzvJu70Al9Mvl2ir9Wtbpu984\noBL6QZX+3Lnmk8NmzfLeLyL1odBPue7u8Eq/tdX79gVRVu9Uc+8dv0rfnsz1utmabd48VfkiaaDQ\nT7m+Pli0yHufHfodHcn09GuZyIXKBVpHjwb39NXPF2k8hX7KLV3qv88O/bGx8NBPYslmlPaOX6V/\n0UWmvSMijaXQzzA79AuFaBO5SdyGIWwi16/S9/tcWxGpLy3ZzDA79L1utgbJ3HsnSnsnSk9fRNIh\nTujPAdYAW4HnAb91GTuB14ANwEsxzicuztD3a+84J3K9lmyG3YYhanvH7ukr9EXSLU7ofw0T+ucA\nP7aeeykDReBCYFmM84lLlNBPcslmWHsnaMmmiKRDnNC/CXjM2n4M+A8BxxYC9kmN7ND3utkaJHMb\nhmomclXpi6RfnNCfDxywtg9Yz72UgbXAeuCLMc4nLnErfWd7p1w2217tHVX6IvkRtnpnDbDA4/U/\ncz0vWw8vlwH7gFOt77cFWOd1YG9v7/vbxWKRYrEYMrzmFjaR61y9E/bB6Hbge920LepErip9kclX\nKpUolUo1f31Y6F8dsO8A5g1hP3A6cNDnuH3Wn4eApzB9/dDQl3DO0Pe6vUHYFbmtreaWzGNj3vsh\nenvn8GFV+iL14C6I+/r6qvr6OO2dVcDnre3PAys9jukE7NpvOnANsCnGOcWh2vaOO7ALhUqLx2vl\njv09krjhmoikQ5zQ/0vMbwJbgU9azwEWAk9b2wswVf1G4EXgXzDLOyUBcSdyYXzoR6n01dMXybY4\nV+QeBq7yeP0t4AZr+03gghjnkABxL86CSl/fa+WO/T3C7rI5bRq8+673RyWKSLroitwMC2vvhN2G\nASpr9cPeFCC4vXPggPdHJYpIuij0M6zaK3KDQj3uRO7+/erni2SBQj/Dpk0zbZljx2q7yyaE9/Sj\nTuTalb6IpJtCP8MKBfMB6QcP1j6R62zveK3eiTqRe/y4Kn2RLFDoZ1xXlwn9KBO5Xq2ZpCZyQZW+\nSBYo9DOuqwsGBmqfyI3S04/S3rHHIiLpptDPODto40zkRlmnPzpq7s/T5rHIV6Evkh0K/YwLC/24\nSzbt9o5fPx8qoa/2jkj6KfQzzg79uBdnhU3k+rV2oPKGo0pfJP0U+hnX1WVunOZ335yklmz6TeIC\ntLSYfar0RdJPoZ9xXV3erR0wbwQnT4bfRTNo9Y69P6jSB/Obhip9kfRT6GdcUOgXCpXJ3Fp7+vb+\noaHw0FelL5J+Cv2MCwp9MKE/MGBaMK2tE/eHLdlsaTHBf+xY8M3UVOmLZINCP+O6urwncW0dHSaw\nvQIdwnv69jFHjwZX+tOmqdIXyQKFfsZFqfTDQj9o9Y79PY4eDa70774bzj8/+rhFpDHi3E9fUiBu\n6If19CFapX/HHZGHLCINpEo/404/HU491X//1KkmsMMqfb/VO/YxYaEvItmg0M+4Sy+Fp57y32+3\nZuL09KO0d0QkG9TeybiwT6qy2zt+gR22esc+RpW+SD7EqfRvBTYDJ4GLAo5bDmwBtgH3xDif1CCJ\nnr4qfZH8iBP6m4CbgZ8FHNMKPIgJ/vOA24FzY5xTqlTNkk2/1Tuq9EXyI07obwG2hhyzDNgO7ARG\ngB8An45xTqnS1KnRlmxqIlekOUz2RO4ZwG7H8z3Wa1InYRO5au+INJewidw1wAKP1+8FVkf4/uVq\nBtPb2/v+drFYpFgsVvPl4qGai7OCjtm/X5W+SBqUSiVKpVLNXx8W+lfX/J2NvcBix/PFmGrfkzP0\nJRkdHdDfn8ySTYW+SOO5C+K+vr6qvj6p9o7fwsH1wNnAEmAKcBuwKqFzSgTVLNkMm8hVe0ck++KE\n/s2Yfv0lwNPAs9brC63nAKPAXcCPgNeBHwJvxDinVKlet2EQkWyIc3HWU9bD7S3gBsfzZ6m8IUid\nJXEbho4O82EsqvRFsk+3Yci5pG6tDKr0RfJAoZ9zSazesSt8hb5I9in0c87+uMS4PX37e4lItin0\nc84O6jgfoqL2jkh+KPRzzg7qoCWbUdbpO7+XiGSXQj/nolb6YffecX4vEckuhX7OhYV+1HvvgCp9\nkTxQ6OdclEo/6pJNVfoi2afQz7lqJnK1Tl8k/xT6OWcHdZT2jt/qHbV3RPJDoZ9zUSr9EydgdDR8\nyabaOyLZp9DPOTuog5ZsDg6awPf7kPWw7yEi2aHQz7koq3fGxvz321/b3g4t+r9FJPP0Y5xzYaHf\n2mrCPCz01c8XyQeFfs6Fhb69z6+fb38Phb5IPij0cy5s9Y69L2y/+vki+aDQz7molX7QflX6Ivmh\n0M+5KKHf3h68v6cHqvzsZRFJqTihfyuwGTgJXBRw3E7gNWAD8FKM80kNWlvNI6g9E1bpT5sGv/u7\nyY9NROovzmfkbsJ8OPqKkOPKQBE4HONcEkNHR7z2jojkR5zQ31LFsT6X/Ug9TJ0ab/WOiORHPXr6\nZWAtsB74Yh3OJy5XXAGzZ/vvD+vpi0h+hFX6a4AFHq/fC6yOeI7LgH3Aqdb32wKsizpAie/JJ4P3\nq70j0jzCQv/qBM6xz/rzEPAUsAyf0O/t7X1/u1gsUiwWEzi9hFHoi2RHqVSiVCrV/PVJ9NpfAL4K\n/MpjXyfQChwDpgPPA33Wn27lcrmcwHCkWp/8JMyaFf4bgYikT8HcKTFylsfp6d8M7AYuAZ4GnrVe\nX2g9B9MaWgdsBF4E/gXvwJcG0kSuSPOIs3rnKevh9hZwg7X9JnBBjHNIHai9I9I8dEWuKPRFmohC\nX7RkU6SJKPRFlb5IE1Hoi0JfpIko9EWrd0SaiEJf1NMXaSIKfQm9C6eI5Eea7n6pK3IbZNcuaGuD\nM85o9EhEpFrVXpGr0BcRybB63oZBREQyRqEvItJEFPoiIk1EoS8i0kQU+iIiTUShLyLSRBT6IiJN\nRKEvItJEFPoiIk1EoS8i0kTihP7/At4AXgWeBGb6HLcc2AJsA+6JcT4REYkpTug/D3wI+HfAVuDr\nHse0Ag9igv884Hbg3BjnbLhSqdToIYTKwhhB40yaxpmsrIyzWnFCfw0wZm2/CCzyOGYZsB3YCYwA\nPwA+HeOcDZeF/xGyMEbQOJOmcSYrK+OsVlI9/f8CPOPx+hnAbsfzPdZrIiLSAG0h+9cACzxevxdY\nbW3/GTAM/IPHcbpXsohIisS9n/4dwBeBK4H3PPZfAvRievpg+v5jwDc9jt0OdMccj4hIs9kB9NTj\nRMuBzcC8gGParAEtAaYAG8n4RK6ISLPaBuwCNliPh6zXFwJPO467DvgNppL3WuEjIiIiIiJ5lNaL\ntx4BDgCbHK/NwUxub8VcpzCrAeNyWwy8gGm1/Rr4Q+v1tI11KmZp70bgdeAb1utpGyeY60s2UFms\nkMYx7gRew4zzJeu1NI5zFvAE5kLO14GLSd84P0ilY7EBOIL5OUrbOMF0SzZjcukfgA7SOU5frZi2\nzxKgnXT1/D8GXMj40P+fwJ9a2/cAf1nvQXlYAFxgbc/AtNLOJZ1j7bT+bAN+CVxOOsf534G/B1ZZ\nz9M4xn/F/LA7pXGcj2GWdIP57z6TdI7T1gLswxRTaRvnEuBNTNAD/BD4POkbZ6CPAs85nn/NeqTF\nEsaH/hZgvrW9wHqeNiuBq0j3WDuBlzFXdKdtnIuAtcAnqFT6aRsjmNCf63otbeOciQkpt7SN0+ka\nYJ21nbZhkM1cAAACUElEQVRxzsEUdbMxb6CrgatJ3zgD3QJ81/H8s8DfNGgsXpYwPvTfcWwXXM/T\nYAlmcr2LdI61BfPb3DFMdQLpG+c/YX7Du4JK6KdtjGDCdAOwHrNsGtI3zgswLb1HgVcwP+vTSd84\nnR4B/qu1ncZx3on5+TkIfN96rapxNvoum1m+eKtMusY/A/hn4I8w/1M4pWWsY5ggWAR8HFNNOzV6\nnJ/C/DBtwP8alkaP0XYZ5s3pOuDLmHakUxrG2QZchFnZdxEwwMTf5NMwTtsU4EbMG79bGsbZDfw3\nTHG3EPMz/1nXMaHjbHTo78X0zmyLMbdqSKsDVK5QPh0TEGnQjgn872PaO5DesYKZKHsa+Peka5yX\nAjdhWiePA5/E/JumaYy2fdafh4CnMPe5Sts491iPl63nT2DCfz/pGqftOuBXmH9TSN+/50eAXwBv\nA6OYuxt/lCr/PRsd+uuBs6lcvHUblcmzNFqFmTjB+nNlwLH1UgAexqyM+Jbj9bSNdR6VVQXTML3I\nDaRrnPdiCo+zgM8APwH+M+kaI5g5kS5rezqmD72J9I1zP+beW+dYz6/CrDxZTbrGabsd82ZvS9u/\n5xbMXQ6mYX7ur8L83Kf139NXWi/eehx4C3Nfod3AFzATKWtJ19KoyzFtk41UlpwtJ31jPR/T192I\nWWr4J9braRun7QoqBUjaxngW5t9xI2aZrv1zk7Zxgrn1+suM/9yNNI5zOtBP5c0U0jnOP6WyZPMx\nzG/5aRyniIiIiIiIiIiIiIiIiIiIiIiIiIiIiIiIiEi+/H9z2vNOXH3Y+AAAAABJRU5ErkJggg==\n", "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "plt.plot(elts)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Powers\n", "\n", "Let us define\n", "$$f(x,n) := \\underbrace{\\sqrt{\\sqrt{\\dots\\sqrt{x}}}\\,\\hskip-1em}_{n}\\hskip1em, \\quad g(x,n) := \\hskip3.7em\\overbrace{\\hskip-3.7em\\left(\\left(\\dots\\left(x\\right)^2\\dots\\right)^2\\right)^2}^{n}.$$\n", "In other words, $f(x, n)$ is the number that we get by taking the square root of $x$, $n$ times in a row, and $g(x, n)$ is the number we get by computing the second power of $x$, $n$ times in a row.\n", "\n", "Obviously, $x = f(g(x, n), n) = g(f(x, n), n)$ for any $n \\in \\mathbb{N}$ and $x \\in \\mathbb{R}^+_0$. But, let us see what a computer has to say if we input some $x \\ne 1$ and $n = 50, 60, \\dots$:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x = 1.7\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "n = 53\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "g(f(1.7, 53), 53) = 1.0\n", "f(g(1.7, 53), 53) = inf\n" ] } ], "source": [ "from math import sqrt\n", "x = float(input(\"x = \"))\n", "n = int(input(\"n = \"))\n", "t = x\n", "for _ in range(n):\n", " t = sqrt(t)\n", "for _ in range(n):\n", " t *= t\n", "print(\"g(f(\" + str(x) + \", \" + str(n) + \"), \" + str(n) + \") =\", t)\n", "t = x\n", "for _ in range(n):\n", " t *= t\n", "for _ in range(n):\n", " t = sqrt(t)\n", "print(\"f(g(\" + str(x) + \", \" + str(n) + \"), \" + str(n) + \") =\", t)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Do these tiny errors really matter?\n", "\n", "Consider the following two systems of linear equations:\n", "\n", "$$\\left\\{\\begin{array}{rcrcr}\n", "1 \\cdot x &+& 1 \\cdot y &=& 2, \\\\\n", "1.000001 \\cdot x &+& 1 \\cdot y &=& 2.000001,\n", "\\end{array}\\right.\n", "\\quad \\text{and} \\quad\n", "\\left\\{\\begin{array}{rcrcr}\n", "1 \\cdot x &+& 1 \\cdot y &=& 2, \\\\\n", "1.000001 \\cdot x &+& 1 \\cdot y &=& 1.999999.\n", "\\end{array}\\right.$$\n", "\n", "What are their solutions?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The solution to the first one is $(x, y) = (1, 1)$, but the solution to the second one is $(x, y) = (-1, 3)$.\n", "\n", "Notice that only one element was changed, and only for an order of magnitude $10^{-6}$, which could've easily been caused by one of the small errors shown before. Similar results can be achieved with arbitrarily small errors." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Bottom line\n", "\n", "Always be extra careful when working with \"real\" numbers in a computer (or, better, avoid them altogether if possible, like in the Fibonacci example)!\n", "\n", "These errors cannot always be considered insignificant, as they can pile up and/or grow in subsequent computations.\n", "\n", "Anyone intending to do any serious computations using computers should take the course \"[Numerical Analysis 1](http://www.maths.manchester.ac.uk/study/undergraduate/courses/mathematics-bsc/course-unit-spec/?unitcode=MATH20602)\" (MATH20602), lest rockets will miss, elevators will fall, and bridges will collapse..." ] } ], "metadata": {}, "nbformat": 4, "nbformat_minor": 0 }