03 Types, type conversions and floating point arithmetic.ipynb

{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Introduction\n\nWe have thus far avoided discussing directly *types*. The '*type*' is the type of object that a variable is associated with. This affects how a computer stores the object in memory, and how operations, such as multiplication and division, are performed.\n\nIn *statically typed* languages, like C and C++, types come up from the very beginning because \nyou usually need to specify types explicitly in your programs. Python is a *dynamically typed* language, which means types are deduced when a program is run. This is why we have been able to postpone the discussion until now.\nIt is important to have a basic understanding of types, and how types can affect how your programs behave. One can go very deep into this topic, especially for numerical computations, but we will cover the general concept from a high level, \nshow some examples, and highlight some potential pitfalls for engineering computations. \n\nThis is a dry topic - it contains important background information that you need to know for later, so hang in there. The below account highlights what can go wrong without an awareness of types and how computers process numbers."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Patriot Missile failure and the Ariane 5 explosion\n\nThere have been numerous accidents due to programs not correctly handling types, type conversions and floating point arithmetic. Here are two examples: \n\n1. In 1991, a US Patriot missile failed to intercept an Iraqi Scud missile at Dhahran in Saudi Arabi, leading to \n   a loss of life. The subsequent investigation found that the Patriot missile failed to intercept the Scud   missile due to a software flaw. The software developers did not account for the effects of 'floating point \n   arithmetic'. \n   This led to a small error in computing the time, which in turn caused the Patriot to miss the incoming Scud \n   missile. \n\n   <img src=\"https://upload.wikimedia.org/wikipedia/commons/e/eb/Patriot_System_2.jpg\" width=\"300\" />\n\n   We will reproduce the precise mistake the developers of the Patriot Missile software made. See\n   https://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran for more background on the interception \n   failure.\n   \n\n1. Poor programming related to how computers store numbers led in 1996 to a European Space Agency *Ariane 5* \n   unmanned rocket exploding shortly after lift-off. The rocket payload, worth US\\$500 M, was destroyed. You can \n   find background at https://en.wikipedia.org/wiki/Cluster_(spacecraft)#Launch_failure. \n   We will reproduce their mistake, and show how a few lines code would have saved over US\\$500 M. \n   \n   <img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/3/3c/Ariane_5ES_with_ATV_4_on_its_way_to_ELA-3.jpg/320px-Ariane_5ES_with_ATV_4_on_its_way_to_ELA-3.jpg\" width=\"200\" />"
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Background: bits and bytes\n\nAn important part of understanding types is appreciating how computer storage works. Computer memory is made up of *bits*, and each bit can take on one of two \nvalues - 0 or 1. A bit is the smallest building block of memory.\nBits are very fine-grained, so for many computer architectures the smallest 'block' we can normally work with is a *byte*. One byte is made up of 8 bits. This why when we talk about bits, e.g. a 64-bit operating system, the number of bits will almost always be a multiple of 8 (one byte).\n\nThe 'bigger' a thing we want to store, the more bytes we need. This is important for engineering computations since the the number of bytes used to store a number determines the accuracy with which the number can be stored,\nand how big or small the number can be. The more bytes the greater the accuracy, but the price to be paid is higher memory usage. Also, it can be more expensive to perform operations like multiplication and division when using more bytes."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Objectives\n\n- Introduce primitive data types (booleans, strings and numerical types)\n- Type inspection\n- Basic type conversion\n- Introduction to pitfalls of floating point arithmetic "
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# What is type?\n\nAll variables have a 'type', which indicates what the variable is, e.g. a number, a string of characters, etc. In 'statically typed' languages we usually need to be explicit in declaring the type of a variable in a program. In a dynamically typed language, such as Python, variables still have types but the interpreter can determine types dynamically.\n\nType is important because it determines how a variable is stored, how it behaves when we perform operations on it, and how it interacts with other variables. For example, multiplication of two real numbers is different from multiplication of two complex numbers."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Introspection \n\nBefore getting into types, we look at how we can check the type in Python. A powerful feature of Python is *introspection*. This means that we can probe a program to ask about the type of a variable. To check \nthe type of a variable we use the function `type`:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "x = True\nprint(type(x))\n\na = 1\nprint(type(a))\n\na = 1.0\nprint(type(a))",
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": "<class 'bool'>\n<class 'int'>\n<class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Note that `a = 1` and `a = 1.0` are different types! This distinction is very important for numerical computations.\nMore on this further down.\n\nUse `type` freely when exploring and testing, to develop an understanding for what your program is doing."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Booleans\n\nYou have already seen the 'Boolean' type that can take on one of two values - true or false. This is the simplest type."
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = True\nb = False\ntest = a or b  # test will be True if a or b are True\nprint(test, type(test))",
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": "True <class 'bool'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "In principle, we could represent a boolean with just one bit (0 or 1 switch)."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Strings\n\nA string is a collection of characters. We have been using strings in previous activities for printing informative messages. In Python we create a string using single or double quotes (the choice is personal preference), e.g.\n\n    my_string = 'This is a string.'\n    \nor\n\n    my_string = \"This is a string.\"\n    \nBelow we assign a string to a variable, display the string, and then check its type:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "my_string = \"This is a string.\"\nprint(my_string)\nprint(type(my_string))",
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": "This is a string.\n<class 'str'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We can perform many different operations on strings. We can extract a particular character as a new string:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "# Get 3rd character (Python counts from zero)\ns2 = my_string[2]\nprint(s2)\nprint(type(s2))",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": "i\n<class 'str'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "or extract a range of characters:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "# Get first six characters, print and check type\ns3 = my_string[0:6]\nprint(s3)\nprint(type(s3))\n\n# Get last four characters and print\ns4 = my_string[-4:]\nprint(s4)",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": "This i\n<class 'str'>\ning.\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We can add strings together:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "introduction = \"My name is:\"\nname = \"Joe\"\n\npersonal_introduction = introduction + \" \" + name\nprint(personal_introduction)",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": "My name is: Joe\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We can also check the length (number of characters) of a string using `len`:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(len(personal_introduction))",
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": "15\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "There are *many* more operations that can be performed on strings. We will see more in later activities."
    },
    {
      "metadata": {
        "collapsed": true
      },
      "cell_type": "markdown",
      "source": "# Numeric types\n\nNumeric types are important in many computing applications, and particularly in scientific and engineering programs. Python 3 has three native numerical types:\n\n- integers (`int`)\n- floating point numbers (`float`)\n- complex numbers (`complex`)\n\nThis is typical for most programming languages, although there can be some subtle differences."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Integers\n\nIntegers (`int`) are whole numbers, and can be postive or negative. Integers should be used when a value can only take on a whole number, e.g. the year, or the number of students following this course. Python infers the type of a number from the way we input it. It will infer an `int` if we assign a number with no decimal place:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 2\nprint(type(a))",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "<class 'int'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "If we add a decimal point, the variable type becomes a `float` (more on this later)"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 2.0\nprint(type(a))",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": "<class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Integer operations that result in an integer, such as multiplying or adding two integers, are performed exactly (there is no error). This does however depend on a variable having enough memory (sufficient bytes) to represent the result."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Integer storage and overflow\n\nIn most languages, a fixed number of bits are used to store a given type of integer. In C and C++ a standard integer (`int`) is usually stored using 32 bits (it is possible to declare shorter and longer integer types). \nThe largest integer that can be stored using 32 bits is $2^{31} - 1 = 2,147,483,647$.\nWe explain later where this comes from. The message for now is that for a fixed number of bits, there is a bound on the largest number that can be represented/stored.\n\n####  Integer overflow\n\nInteger overflow is when an operation creates an integer that is too big to be represented by the given integer type. For example, attempting to assign $2^{31} + 1$ to a 32-bit integer will cause an overflow and potentially unpredictable program response. This would usually be a *bug*.\n\nThe Ariane 5 rocket explosion in 1996 was caused by integer overflow. The rocket navigation software was taken from the older, slower Ariane 4 rocket. The program assigned the rocket speed to a 16-bit integer (the largest number a 16-bit integer can store is $2^{15} - 1 = 32767$), but the Ariane 5 could travel faster than the older generation of rocket and the speed value exceeded $32767$. The resulting integer overflow led to \nfailure of the rocket's navigation system and\nexplosion of the rocket; a very costly rocket and a very expensive payload were destroyed.\nWe will reproduce the error that caused this failure when we look at *type conversions*.\n\nPython avoids integer overflows by dynamically changing the number of bits used to represent an integer. You can inspect the number of bits required to store an integer in binary (not including the bit for the sign) using the function [bit_length](https://docs.python.org/3/library/stdtypes.html#int.bit_length):"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 8\nprint(type(a))\nprint(a.bit_length())",
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": "<class 'int'>\n4\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We see that 4 bits are necessary to represent the number 8. If we increase the size of the number dramatically by raising it to the power of 12:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "b = a**12\nprint(b)\ntype(b)\nprint(b.bit_length())",
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "text": "68719476736\n37\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We see that 37 bits are required to represent the number. If the `int` type was limited to 32 bits for storing the value, this operation would have caused an overflow."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "#### Gangnam Style\n\nIn 2014, Google switched from 32-bit integers to 64-bit integers to count views when the video \"Gangnam Style\" was viewed more than 2,147,483,647 times, which is the limit of 32-bit integers (see https://plus.google.com/+YouTube/posts/BUXfdWqu86Q)."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "#### Boeing 787 Dreamliner bug\n\nDue to an integer overflow bug, the electricity generators on a Boeing 787 will shut down if the plane is\npowered continuously for 248 days, due to an overflow. The 'quick fix' was to make sure that \ngenerator control units do not operate for more than 248 days.\nSee \nhttps://www.theguardian.com/business/2015/may/01/us-aviation-authority-boeing-787-dreamliner-bug-could-cause-loss-of-control and \nhttps://s3.amazonaws.com/public-inspection.federalregister.gov/2015-10066.pdf for background."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "##  Floating point storage\n\nMost engineering calculations involve numbers that cannot be represented as integers. Numbers that have a \ndecimal point are stored using the `float` type. Computers store floating point numbers by storing the sign, the significand (also known as the mantissa) and the exponent, e.g.: for $10.45$\n\n$$\n10.45 = \\underbrace{+}_{\\text{sign}} \\underbrace{1045}_{\\text{significand}} \\times \\underbrace{10^{-2}}_{\\text{exponent} = -2}\n$$\n\nPython uses 64 bits to store a `float` (in C and C++ this is known as a `double`). The sign requires one bit, and there are standards that specify how many bits should be used for the significand and how many for the exponent.\n\nSince a finite number of bits are used to store a number, the precision with which numbers can be represented is limited. As a guide, using 64 bits a floating point number is precise to 15 to 17 significant figures.\nMore on this, and why the Patriot missile failed, later."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Floats\n\nWe can declare a float by adding a decimal point:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 2.0\nprint(a)\nprint(type(a))\n\nb = 3.\nprint(b)\nprint(type(b))",
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": "2.0\n<class 'float'>\n3.0\n<class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "or by using `e` or `E` (the choice between `e` and `E` is just a matter of taste):"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 2e0\nprint(a, type(a))\n\nb = 2e3\nprint(b, type(b))\n\nc = 2.1E3\nprint(c, type(c))",
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": "2.0 <class 'float'>\n2000.0 <class 'float'>\n2100.0 <class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Complex numbers\n\nA complex number is a more elaborate float with two parts - the real and imaginary components. We can declare a complex number in Python by adding `j` or `J` after the complex part of the number:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 2j\nprint(a, type(a))\n\nb = 4 - 3j\nprint(b, type(b))",
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "text": "2j <class 'complex'>\n(4-3j) <class 'complex'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The usual addition, subtraction, multiplication and division operations can all be performed on complex numbers. The real and imaginary parts can be extracted:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(b.imag)\nprint(b.real)",
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "stream",
          "text": "-3.0\n4.0\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "and the complex conjugate can be taken:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(b.conjugate())",
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "text": "(4+3j)\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We can compute the modulus of a complex number using `abs`:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(abs(b))",
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "text": "5.0\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "More generally, `abs` returns the absolute value, e.g.:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = -21.6\na = abs(a)\nprint(a)",
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": "21.6\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Type conversions (casting)\n\nWe can often change between types. This is called *type conversion* or *type casting*. In some cases it happens implicitly, and in other cases we can instruct our program to change the type.\n\nIf we add two integers, the results will be an integer:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 4\nb = 15\nc = a + b\nprint(c, type(c))",
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": "19 <class 'int'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "However, if we add an `int` and a `float`, the result will be a float:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 4\nb = 15.0  # Adding the '.0' tells Python that it is a float\nc = a + b\nprint(c, type(c))",
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "text": "19.0 <class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "If we divide two integers, the result will be a `float`:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 16\nb = 4\nc = a/b\nprint(c, type(c))\nb = 2",
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "text": "4.0 <class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "When dividing two integers, we can do 'integer division' using `//`, e.g."
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 16\nb = 3\nc = a//b\nprint(c, type(c))",
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "text": "5 <class 'int'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "in which case the result is an `int`.\n\nIn general, operations that mix an `int` and `float` will generate a `float`, and operations that mix an `int` or a `float` with `complex` will return a `complex` type. If in doubt, use `type` to experiment and check.  "
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Explicit type conversion\n\nWe can explicitly change the type (perform a cast), e.g. cast from an `int` to a `float`:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 1\nprint(a, type(a))\n\na = float(a)  # This converts the int associated with 'a' to a float, and assigns the result to the variable 'a'\nprint(a, type(a))",
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "text": "1 <class 'int'>\n1.0 <class 'float'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Going the other way,"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "y = 1.99\nprint(y, type(y))\n\nz = int(y)\nprint(z, type(z))",
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "stream",
          "text": "1.99 <class 'float'>\n1 <class 'int'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Note that rounding is applied when converting from a `float` to an `int`; the values after the decimal point are discarded. This type of rounding is called 'round towards zero' or 'truncation'.\n\nA common task is converting numerical types to-and-from strings. We might read a number from a file as a string, or a user might input a value which Python reads in as a string. Converting a float to a string:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = 1.023\nb = str(a)\nprint(b, type(b))",
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "stream",
          "text": "1.023 <class 'str'>\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "and in the other direction:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = \"15.07\"\nb = \"18.07\"\n\nprint(a + b)\nprint(float(a) + float(b))",
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "stream",
          "text": "15.0718.07\n33.14\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "If we tried \n```python\nprint(int(a) + int(b))\n```\nwe could get an error that the strings could not be converted to `int`. It works in the case:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = \"15\"\nb = \"18\"\nprint(int(a) + int(b))",
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "stream",
          "text": "33\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "since these strings can be correctly cast to integers."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Ariane 5 rocket explosion and type conversion\n\nThe Ariane 5 rocket explosion was caused by an integer overflow. The speed of the rocket was stored as a 64-bit float, and this was converted in the navigation software to a 16-bit integer. However, the value of the float was greater than $32767$, the largest number a 16-bit integer can represent, and this led to an overflow that in turn caused the navigation system to fail and the rocket to explode.\n\nWe can demonstrate what happened in the rocket program. We consider a speed of $40000.54$ (units are not relevant to what is being demonstrated), stored as a `float` (64 bits):"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "speed_float = 40000.54",
      "execution_count": 28,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "If we first convert the float to a 32-bit `int` (we use NumPy to get integers with a fixed number of bits, more on NumPy in a later notebook):"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "import numpy as np\nspeed_int = np.int32(speed_float)  # Convert the speed to a 32-bit int\nprint(speed_int)",
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "text": "40000\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The conversion behaves as we would expect. Now, if we convert the speed from the `float` to a 16-bit integer:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "speed_int = np.int16(speed_float)\nprint(speed_int)",
      "execution_count": 30,
      "outputs": [
        {
          "output_type": "stream",
          "text": "-25536\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "We see clearly the result of an integer overflow since the 16-bit integer has too few bits to represent the number \n40000.\n\nThe Ariane 5 failure would have been averted with pre-launch testing and the following few lines:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "if abs(speed_float) > np.iinfo(np.int16).max:\n    print(\"***Error, cannot assign speed to 16-bit int. Will cause overflow.\")\n    # Call command here to exit program\nelse:\n    speed_int = np.int16(speed_float)",
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "stream",
          "text": "***Error, cannot assign speed to 16-bit int. Will cause overflow.\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "These few lines and careful testing would have saved the $500M payload and the cost of the rocket.\n\nThe Ariane 5 incident is an example not only of a poor piece of programming, but also very poor testing and software engineering. Careful pre-launch testing of the software would have detected this problem. The program should have checked the value of the velocity before performing the conversion, and triggered an error message that the type conversion would cause an overflow."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Binary representation and floating point arithmetic\n\n## Binary (base 2) representation\n\nComputers store data using 'bits', and a bit is a switch that can have a value of 0 or 1. This means that computers store numbers in binary (base 2), whereas we almost always work with decimal numbers (base 10).\nFor example, the binary number $110$ is equal to $0 \\times 2^{0} + 1 \\times 2^{1} + 1 \\times 2^{2} = 6$\n(read $110$ right-to-left).\nBelow is a table with decimal (base 10) and the corresponding binary (base 2) representation of some numbers. See <https://en.wikipedia.org/wiki/Binary_number> if you want to learn more.\n\n|Decimal | Binary  |\n| ------ |-------- |\n|0       |\t   0   | \n|1       |\t1      | \n|2       |\t10     |\n|3       |\t11     |\n|4       |\t100    |\n|5       |\t101    |\n|6       |\t110    |\n|7       |\t111    |\n|8       |\t1000   |\n|9       |\t1001   |\n|10      |\t1010   |\n|11\t     |  1011   |\n|12\t     |  1100   |\n|13      |\t1101   |\n|14      |\t1110   |\n|15      |\t1111   |\n\nTo represent any integer, all we need are enough bits to store the binary representation. If we have $n$ bits, the largest number we can store is $2^{n -1} - 1$ (the power is $n - 1$ because we use one bit to store the sign of the integer).\n\nWe can display the binary representation of an integer in Python using the function `bin`:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(bin(2))\nprint(bin(6))\nprint(bin(110))",
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0b10\n0b110\n0b1101110\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The prefix `0b` is to denote that the representation is binary."
    },
    {
      "metadata": {
        "collapsed": true
      },
      "cell_type": "markdown",
      "source": "## Floating point numbers\n\nWe introduced the representation\n\n$$\n10.45 = \\underbrace{+}_{\\text{sign}} \\underbrace{1045}_{\\text{significand}} \\times \\underbrace{10^{-2}}_{\\text{exponent}}\n$$\n\nearlier. However, this was a little misleading because computers do not use base 10\nto store the significand and the exponent, but base 2. \n\nWhen using the familiar base 10, we cannot represent $1/3$ exactly as a decimal. If we liked using base 3 (ternary numeral system) for our mental arithmetic (which we really don't), we could represent $1/3$ exactly. However, fractions that are simple to represent exactly in base 10 might not be representable in another base.\nA consequence is that fractions that are simple in base 10 cannot necessarily be represented exactly by computers using binary.\n\nA classic example is $1/10 = 0.1$. This simple number cannot be represented exactly in\nbinary. On the contrary, $1/2 = 0.5$ can be represented exactly. To explore this, let's assign the number 0.1 to the variable `x` and print the result:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "x = 0.1\nprint(x)",
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0.1\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "This looks fine, but the `print` statement is hiding some details. Asking the `print` statement to use 30 characters we see that `x` is not exactly 0.1:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print('{0:.30f}'.format(x))",
      "execution_count": 34,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0.100000000000000005551115123126\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The difference between 0.1 and the binary representation is the *roundoff error* (we'll look at print formatting syntax in a later activity). From the above, we can see that the representation is accurate to about 17 significant figures.\n\nChecking for 0.5, we see that it appears to be represented exactly:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print('{0:.30f}'.format(0.5))",
      "execution_count": 35,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0.500000000000000000000000000000\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The round-off error for the 0.1 case is small, and in many cases will not present a problem. However, sometimes round-off errors can accumulate and destroy accuracy."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Example: inexact representation\n\nIt is trivial that\n\n$$\nx = 11x - 10x\n$$\n\nIf $x = 0.1$, we can  write\n\n$$\nx = 11x - 1\n$$\n\nNow, starting with $x = 0.1$ we evaluate the right-hand side to get a 'new' $x$, and use this new $x$ to then evaluate the right-hand side again. The arithmetic is trivial: $x$ should remain equal to $0.1$.\nWe test this in a program that repeats this process 20 times: "
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "x = 0.1\nfor i in range(20):\n    x = x*11 - 1\n    print(x)",
      "execution_count": 36,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0.10000000000000009\n0.10000000000000098\n0.10000000000001075\n0.10000000000011822\n0.10000000000130038\n0.1000000000143042\n0.10000000015734622\n0.10000000173080847\n0.10000001903889322\n0.10000020942782539\n0.10000230370607932\n0.10002534076687253\n0.10027874843559781\n0.1030662327915759\n0.13372856070733485\n0.4710141677806834\n4.181155845587517\n44.992714301462684\n493.9198573160895\n5432.118430476985\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The solution blows up and deviates widely from $x = 0.1$. Round-off errors are amplified at each step, leading to a completely wrong answer. The computer representation of $0.1$ is not exact, and every time we multiply $0.1$ by $11$, we increase the error by around a factor of 10 (we can see above that we lose a digit of accuracy in each step). \nYou can observe the same issue using spreadsheet programs."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "If we use $x = 0.5$, which can be represented exactly in binary:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "x = 0.5\nfor i in range(20):\n    x = x*11 - 5\n    print(x)",
      "execution_count": 37,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n0.5\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The result is exact in this case.\n\nBy default, Python uses 64 bits to store a float. We can use the module NumPy to create a \nfloat that uses only 32 bits. Testing this for the $x = 0.1$ case:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "x = np.float32(0.1)\nfor i in range(20):\n    x = x*11 - 1\n    print(x)",
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0.10000001639127731\n0.10000018030405045\n0.1000019833445549\n0.10002181679010391\n0.10023998469114304\n0.1026398316025734\n0.12903814762830734\n0.41941962391138077\n3.6136158630251884\n38.74977449327707\n425.2475194260478\n4676.722713686526\n51442.949850551784\n565871.4483560696\n6224584.931916766\n68470433.25108442\n753174764.7619286\n8284922411.381214\n91134146524.19336\n1002475611765.127\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The error blows up faster in this case compared to the 64 bit case - using 32 bits leads to a poorer approximation of $0.1$ than when using 64 bits.\n\n*Note:* Some languages have special tools for performing decimal (base 10) arithmetic (e.g., https://docs.python.org/3/library/decimal.html). This would, for example, allow $0.1$ to be represented exactly. However, decimal is not the 'natural' arithmetic of computers so operations in decimal could be expected to be much slower."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Patriot Missile Failure\n\nThe inexact representation of $0.1$ was the cause of the software error in the Patriot missile system (see preamble to this notebook). \nThe missile system tracked time from boot (system start) using an integer counter that was incremented every $1/10$ of a second. To\nget the time in seconds, the missile software multiplied the counter by the float representation of $0.1$. \nThe control software used 24 bits to store floats. The round-off error due to the inexact representation of $0.1$ lead to an error of $0.32$ s after 100 hours of operation (time since boot), which due to the high velocity of the missile was enough to cause failure to intercept the incoming Scud.\n\nWe don't have 24-bit floats in Python, but we can test with 16, 32 and 64 bit floats.\nWe first compute what the system counter (an integer) would be after 100 hours:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "# Compute internal system counter after 100 hours (counter increments every 1/10 s)\nnum_hours = 100\nnum_seconds = num_hours*60*60\nsystem_counter = num_seconds*10  # system clock counter",
      "execution_count": 39,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Converting the system counter to seconds using different representations of 0.1:"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "# Test with 16 bit float\ndt = np.float16(0.1)\ntime = dt*system_counter\nprint(\"Time error after 100 hours using 16 bit float (s):\", abs(time - num_seconds))\n\n# Test with 32 bit float\ndt = np.float32(0.1)\ntime = dt*system_counter\nprint(\"Time error after 100 hours using 32 bit float (s):\", abs(time - num_seconds))\n\n# Test with 64 bit float\ndt = np.float64(0.1)\ntime = dt*system_counter\nprint(\"Time error after 100 hours using 64 bit float (s):\", abs(time - num_seconds))",
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Time error after 100 hours using 16 bit float (s): 87.890625\nTime error after 100 hours using 32 bit float (s): 0.005364418029785156\nTime error after 100 hours using 64 bit float (s): 0.0\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "The time computation with 16-bit floats is more than a minute off after 100 hours! The stop-gap measure \nfor the Patriot missiles at the time was to reboot the missile systems frequently, thereby resetting the system counter and reducing the time error."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Summary\n\nThe key points from this activity are:\n\n- The size of an integer that a computer can store is determined by the number of bits used to represent the \n  integer.\n- Computers do not perform exact arithmetic with non-integer numbers. This does not usually cause a problem, but \n  it can in cases. Problems can often be avoided with careful programming.\n- Be thoughtful when converting between types - undesirable consequences can follow when careless with \n  conversions."
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Exercises\n\nComplete now the [03 Exercises](Exercises/03%20Exercises.ipynb) notebook."
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "mimetype": "text/x-python",
      "nbconvert_exporter": "python",
      "name": "python",
      "pygments_lexer": "ipython3",
      "version": "3.5.4",
      "file_extension": ".py",
      "codemirror_mode": {
        "version": 3,
        "name": "ipython"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 1
}