{ "cells": [ { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "K-Y40d7IekWU", "slideshow": { "slide_type": "slide" } }, "source": [ "\"Open\n", "\n", "# Computer Arithmetics and Round-off Methods\n", "\n", "Actividades: https://classroom.github.com/a/2v-HnNqn\n", "\n", "In a symbolic computation programs, implemented in SymPy or Mathematica for example, operatios like $1/3+4/3=5/3$, $2\\times 3/4 = 3/2$, $(\\sqrt{2})^2 = 2$ are unambiguously defined, However, when one numerical programming languages are used to represent numbers in a computer, this is no longer true. The main reason of this is the so-called *finite arithmetic*, what is the way in which a numerical computer programs performs basic operations. Some features of *finite arithmetic* are stated below:" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- Only integer and rational numbers can be exactly represented.\n", "- The elements of the set in which arithmetic is performed is necessarily finite.\n", "- Any arithmetic operation between two or more numbers of this set should be another element of the set.\n", "- Non-representable numbers like irrational numbers are approximated to the closest rational number within the defined set.\n", "- Extremely large numbers produce overflows and extremely small numbers produce underflows, which are taken as null.\n", "- Operations over non-representable numbers are not exact.\n", "\n", "In spite of this, defining adequately the set of elements in which our computer will operate, round-off methods can be systematically neglected, yielding correct results within reasonable error margins. In some pathological cases, when massive iterations are required, these errors must be taken into account more seriously.\n", "\n", "- - - \n", "\n", "- [Binary machine numbers](#Binary-machine-numbers)\n", " - [Single-precision numbers](#Single-precision-numbers)\n", " - [Double-precision numbers](#Double-precision-numbers)\n", "- [Finite Arithmetic](#Finite-Arithmetic)\n", " - [Addition](#Addition)\n", " - [Multiplication](#Multiplication)\n", "\n", "- - - " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## More About Float Values \n", "See also [here](https://www.inferentialthinking.com/chapters/04/1/Numbers.html)\n", "\n", "In Python a float only represents 15 or 16 significant digits for any number; the remaining precision is lost. This limited precision is enough for the vast majority of applications.\n", "\n", "In the next evaluation extra digits are discarded before any arithmetic is carried out." ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "0.0" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "0.6666666666666666 - 0.6666666666666666123456789" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "After combining float values with arithmetic, the last few digits may be incorrect. Small rounding errors are often confusing when first encountered. For example, the expression `2**0.5` computes the square root of `2`, but squaring this value does not exactly recover `2`." ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1.4142135623730951" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "2**0.5" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2.0000000000000004" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(2**0.5)**2" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4.440892098500626e-16" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(2**0.5)**2 - 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "oqZtWoT7jolm", "slideshow": { "slide_type": "slide" } }, "source": [ "## Binary machine numbers" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "7z0MWgOrjuO2" }, "source": [ "We will obtain the general algorithm to obtain the binary r" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "6YcTBJivis_R", "slideshow": { "slide_type": "subslide" } }, "source": [ "### Integers" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "74bewmHTixif", "slideshow": { "slide_type": "-" } }, "source": [ "From [here](https://www.techcareerbooster.com/blog/binary-representation-of-an-integer): If you recall your mathematics, then it will be easy for you to find out how we turn an integer number to its binary representation. Let's take for example the number 47. (see '//' operator [here](https://stackoverflow.com/a/1535601))\n", "\n", "\n", "1. We divide 47 by 2. The quotient is `int(47//2) → 23` and the remainder is `47%2 → 1`\n", "2. We divide the quotient of the previous step by 2. The new quotient is `int(23//2) → 11` and the remainder is `23%2 → 1`.\n", "3. We divide the quotient of the previous step by 2. The new quotient is `int(11/2) → 5` and the remainder is `11%2 → 1`.\n", "5. We divide the quotient of the previous step by 2. The new quotient is `int(5//2) → 2` and the remainder is `5%2 → 1`.\n", "6. We divide the quotient of the previous step by 2. The new quotient is `int(2//2) → 1` and the remainder is `2%2 → 0`.\n", "7. We divide the quotient of the previous step by 2. The new quotient is `int(1//2) → 0` and the remainder is `1%2 → 1`\n", "8. We stop here, when the last quotient is `1//2→0`.\n", "\n", "Then, the binary representation is the series of __1__s and __0__s of the remainders, taken in reverse order to the one produced, from latest to earliest: __101111__.\n", "" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "NieG9Hn5lp0v", "slideshow": { "slide_type": "slide" } }, "source": [ "__Activity__: Implement a function that get the binary representation of an integer. " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x=47/2=23 → b=1\n", "x=23/2=11 → b=11\n", "x=11/2=5 → b=111\n", "x=5/2=2 → b=1111\n", "x=2/2=1 → b=01111\n", "x=1/2=0 → b=101111\n" ] } ], "source": [ "x=47\n", "b=''\n", "while x!=0:\n", " oldx=x\n", " b=str(x%2)+b\n", " x=x//2\n", " print(f'x={oldx}/2={x} → b={b}')" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "Vn7Cusk5orMc" }, "source": [ "__Activity__: Return as a string with 8 charactes completed with leading zeroes. Use the string method: `.rjust(8,\"0\")`" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b=00101111\n" ] } ], "source": [ "b=b.rjust(8,'0')\n", "print(f'b={b}')" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "WCU8B-h1A2Pq", "slideshow": { "slide_type": "slide" } }, "source": [ "__Activity__ Write your function in the following format" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 90 }, "colab_type": "code", "id": "aP1xnAWrBfRp", "outputId": "6b552cc2-d659-4e67-b5a1-b589d037d393", "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting mybin.py\n" ] } ], "source": [ "#!/usr/bin/env python3\n", "def mybin(x):\n", " print('__name__ = {}'.format(__name__))\n", " #Write your code here and change the next line as required\n", " return bin(x)[2:].rjust(8, \"0\")\n", "if __name__=='__main__':\n", " n=input('Escriba un entero:\\n')\n", " b=mybin(int(n))\n", " print('Su representación binaria es: {}'.format(b))" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "C9-H4KqgBpg2", "slideshow": { "slide_type": "slide" } }, "source": [ "The advantage of this standard format is that can be used directly as a python module, because in that case the variable `__name__` evaluates to the name\n", "of the function. To check this, we first use a cell of the notebook just as a editor with the Jupyter magic function `%%writefile`" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "ZVgjNnOfSDp0", "outputId": "ce7bcb24-ef4d-4fcd-c456-778555627348" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting mybin.py\n" ] } ], "source": [ "%%writefile mybin.py\n", "#!/usr/bin/env python3\n", "def mybin(x):\n", " print('__name__ = {}'.format(__name__))\n", " return bin(x)[2:].rjust(8, \"0\")\n", "if __name__=='__main__':\n", " n=input('Escriba un entero;\\n')\n", " b=mybin(int(n))\n", " print('Su representación binaria es: {}'.format(b))\n" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "8F0OTamOSLfO" }, "source": [ "We now can use the full contents of the file as an usual python module, it it is\n", "in the working directory" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 54 }, "colab_type": "code", "id": "bXohCqmKSY7r", "outputId": "09a9c4c7-9f27-47da-c1e5-e0182575ae63", "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "__name__ = mybin\n" ] }, { "data": { "text/plain": [ "'00101101'" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import mybin as my\n", "my.mybin(45)" ] }, { "cell_type": "markdown", "metadata": { "colab": {}, "colab_type": "code", "id": "s5uBqKH8ScVm" }, "source": [ "while here, or in a terminal:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'__main__'" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "__name__" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "kWhR37BchYaJ" }, "source": [ "Check with `bin`" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "nJiWGP8AgX27", "slideshow": { "slide_type": "slide" } }, "source": [ "The binary representation of a float in 32 bits done by the following steps" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "id": "YbrDjH0-hEhp", "outputId": "cc03a2db-5a03-4cd6-9764-382ff608f3d4" }, "outputs": [ { "data": { "text/plain": [ "'0b101111'" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin(47)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "5eDFv2B2u_ME" }, "source": [ "The format is not the standard one. We need drop the first '0b'" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "id": "vumsZnjDvV9Y", "outputId": "4cb26c10-6cd9-4940-83b0-21cc899f450e" }, "outputs": [ { "data": { "text/plain": [ "'101111'" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin(47)[2:]" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "wp2bXTD8vfKo" }, "source": [ "We must enforce the 8 bits representation by padding any additional leading zeroes" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "id": "uVJtGrt2v61F", "outputId": "8bcd1b63-d9a5-43ed-8cd6-c2137c488e20" }, "outputs": [ { "data": { "text/plain": [ "'00101111'" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin(47)[2:].rjust(8, '0')" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "_MAeRxAGwCA1" }, "source": [ "To convert a binary into the integer we can use the `int` function with `base=0` upont the proper Python formatted string, starting with: `0b`" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "id": "uw7yxC8HwNqV", "outputId": "79e18d0f-36eb-4b3a-d867-51d996f712b1" }, "outputs": [ { "data": { "text/plain": [ "47" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "int('0b101111',base=0)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "bN5y4Kinw-eY" }, "source": [ "or with any number of padding zeroes in between" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 34 }, "colab_type": "code", "id": "9iQptjEnwigI", "outputId": "d1373bb9-fe07-480a-cbb4-04617c1eb85d" }, "outputs": [ { "data": { "text/plain": [ "47" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "int('0b0000000101111',base=0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is rather straightforward to check that the binary representation is consistent:\n", "\n", "| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | Total |\n", "|:-----:|:----:|:----:|:----:|---|---|---|---|-------:|\n", "| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |\n", "| 0 | 0 | 32 | 0 | 8 | 4 | 2 | 1 | 47 |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Floats" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "GlLaeJuYekWV", "slideshow": { "slide_type": "slide" } }, "source": [ "Floats in 32 bits are representated trough 4 8-bit integers.\n", "\n", "The processes of obtain the binary representation for a float can be complicated because the design used to really store the number in one specific programming language like Python. In fact, from https://stackoverflow.com/a/16444778/2268280:" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "yg8dpA8M0X_o" }, "source": [ "* To obtain the four integers associated to a real number we need first to ask for the packed structure : `'!'`, in 32 bits: `'f'`, with the full string `'!f'` as" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "JFXl8fYT0m5f", "outputId": "a8829d55-beef-45e7-9b22-2f4a5d888524" }, "outputs": [ { "data": { "text/plain": [ "b'> \\x00\\x00'" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import struct\n", "packed=struct.pack('!f',0.15625)\n", "packed" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "bytes" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(packed)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "DF1X9-Q_1jj0" }, "source": [ "This is a packed Python list with the four integers inside" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "gLnTvnAQ1riZ", "outputId": "91593b85-fe3c-425d-e3b4-f7c3843ed428" }, "outputs": [ { "data": { "text/plain": [ "[62, 32, 0, 0]" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[n for n in packed]" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "fUv2SZWO14nY" }, "source": [ "Using the previous function to convert into a list of 8-bit strings" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 108 }, "colab_type": "code", "id": "7Sd2oDWN7V2v", "outputId": "6ebb1473-0091-4320-91d1-949d900dd25e" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "__name__ = __main__\n", "__name__ = __main__\n", "__name__ = __main__\n", "__name__ = __main__\n" ] }, { "data": { "text/plain": [ "['00111110', '00100000', '00000000', '00000000']" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lb=[ mybin(n) for n in packed]\n", "lb" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "VxjOcP8A-eK4" }, "source": [ "The float representation is just the string formed with the four binaries" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "X_jfXrTo_fFQ", "outputId": "b4017740-848e-471c-9f63-a2aeba2fd156" }, "outputs": [ { "data": { "text/plain": [ "'00111110001000000000000000000000'" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(lb)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "eptuC0Nk_qXZ" }, "source": [ "![32-bits](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Float_example.svg/590px-Float_example.svg.png)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "KL8J_d0y7jNI" }, "source": [ "#### Full implementation" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "colab": {}, "colab_type": "code", "id": "JaBoHSiAekWW" }, "outputs": [], "source": [ "import struct\n", "\n", "def binary(num):\n", "#num=3\n", "#if True:\n", " # Struct can provide us with the float packed into bytes. The '!' ensures that\n", " # it's in network byte order (big-endian) and the 'f' says that it should be\n", " # packed as a float: 32 bites. Alternatively, for double-precision, you could use 'd'.\n", " packed = struct.pack('!f', num)\n", " print( 'Packed: %s' % repr(packed))\n", "\n", " # For each character in the returned string, we'll turn it into its corresponding\n", " # integer code point\n", " # \n", " integers = [c for c in packed]\n", " print( 'Integers: %s' % integers)\n", "\n", " # For each integer, we'll convert it to its binary representation.\n", " binaries = [bin(i) for i in integers]\n", " print( 'Binaries: %s' % binaries)\n", "\n", " # Now strip off the '0b' from each of these\n", " stripped_binaries = [s.replace('0b', '') for s in binaries]\n", " print( 'Stripped: %s' % stripped_binaries)\n", "\n", " # Pad each byte's binary representation's with 0's to make sure it has all 8 bits:\n", " #\n", " # ['00111110', '10100011', '11010111', '00001010']\n", " padded = [s.rjust(8, '0') for s in stripped_binaries]\n", " print( 'Padded: %s' % padded)\n", "\n", " # At this point, we have each of the bytes for the network byte ordered float\n", " # in an array as binary strings. Now we just concatenate them to get the total\n", " # representation of the float:\n", " return ''.join(padded)" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 126 }, "colab_type": "code", "id": "Og6bGmhVekWZ", "outputId": "059605fc-be6d-479b-8f2e-45ba989fb38c" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Packed: b'> \\x00\\x00'\n", "Integers: [62, 32, 0, 0]\n", "Binaries: ['0b111110', '0b100000', '0b0', '0b0']\n", "Stripped: ['111110', '100000', '0', '0']\n", "Padded: ['00111110', '00100000', '00000000', '00000000']\n" ] }, { "data": { "text/plain": [ "'00111110001000000000000000000000'" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "BIN=binary(0.15625)\n", "BIN" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "G6Nycj-cekWc" }, "source": [ "![32-bits](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Float_example.svg/590px-Float_example.svg.png)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "KqAdhGWWekWd", "outputId": "b15caac7-38d8-4412-a683-09cf532a0f30" }, "outputs": [ { "data": { "text/plain": [ "'00000000000000000000010001111100'" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join( list(BIN)[::-1] ) #inverted list joined into a string" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "siRJmwCAekWg" }, "source": [ "### Binary machine numbers " ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "9gyrlmVDekWh" }, "source": [ "As everyone knows, the base of the modern computation is the binary numbers. The binary base or base-2 numeral system is the simplest one among the existing numeral bases. As every electronic devices are based on logic circuits (circuits operating with [logic gates](#LogicGates)), the implementation of a binary base is straightforward, besides, any other numeral system can be reduced to a binary representation.\n", "\n", "![LogicGates](http://www.ee.surrey.ac.uk/Projects/CAL/digital-logic/gatesfunc/graphics/symtab.gif)\n", "\n", "According to the standard [IEEE 754-2008](http://en.wikipedia.org/wiki/IEEE_floating_point), representation of real numbers can be done in several ways, [single-precision](http://en.wikipedia.org/wiki/Single-precision_floating-point_format) and [double precision](http://en.wikipedia.org/wiki/Double-precision_floating-point_format) are the most used ones." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "mTaL_rTLekWh" }, "source": [ "#### Single-precision numbers" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "i0TqQpJuekWi" }, "source": [ "Single-precision numbers are used when one does not need very accurate results and/or need to save memory. These numbers are represented by a **32-bits** (Binary digIT) lenght binary number, where the real number is stored following the next rules:\n", "\n", "![32-bits](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Float_example.svg/590px-Float_example.svg.png)\n", "\n", "3. The last 23 bits represent the fractional part of the number, `b_i`, with `i=0,...22`\n", "2. The next 8 bits represent the exponent of the number, `e`, given by\n", "$$e = \\sum_{i=0}^7 b_{23+i}2^i$$\n", "1. The fist digit (called `s`) indicates the sign of the number (`s=0` means a positive number, `s=1` a negative one).\n", "\n", "The formula for recovering the real number is then given by:\n", "\n", "$$r = \\frac{(-1)^s}{2^{127-e}} \\left( 1 + \\sum_{i=0}^{22}\\frac{b_{i}}{2^{23-i}} \\right)$$\n", "\n", "where $s$ is the sign, $b_{23-i}$ the fraction bits and $e$ is given by:\n", "\n", "\n", "Next, it is shown a little routine for calculating the value of the represented 32-bits number" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "2ycxeSJCekWj" }, "source": [ "### ACTIVITY\n", "With the binary representation please try to implement the formula to recover the number.\n", "\n", "__Hint__: Use as input the binary representation as a string and invert its order" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "sjxwZuwYekWk" }, "source": [ "__SOLUTION__:" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "gDTO3_OqekWl" }, "source": [ "The goal of this course is try to implement all the algorithms in terms of array operations, instead of use the loops of Pyhton like the `for` loop.\n", "\n", "In this way, we need to interpret the formula in terms of arrays operations. If we manage to achieve that, then NumPy will be take care of the internal loops, which are much faster than the Python loops. As a bonus, the code is more compact and readable.\n", "\n", "For example:\n", "\n", "\\begin{align}\n", "\\sum_{i=0}^{22}\\frac{b_{i}}{2^{23-i}}=&\\frac{b[0]}{2^{23}}+\\frac{b[1]}{2^{22}}\n", " +\\cdots +\\frac{b[21]}{2^2}+\\frac{b[22]}{2^1}\\nonumber\\\\\n", "=&\\frac{b[0:23]}{2^{[23,22,...,1]}}.\\operatorname{sum()}\\nonumber\\\\\n", "=&\\frac{b[0:23]}{2^{[1,2,...,23][::-1]}}.\\operatorname{sum()}\n", "\\end{align}\n", "\n", "To implement the full formula:\n", "$$r = \\frac{(-1)^s}{2^{127-e}} \\left( 1 + \\sum_{i=0}^{22}\\frac{b_{i}}{2^{23-i}} \\right)$$\n", "with \n", "$$e = \\sum_{i=0}^7 b_{23+i}2^i$$\n", "\n", "` e=(b[23:30]*2**(np.arange(8))).sum()`" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "colab": {}, "colab_type": "code", "id": "4FfRykO2ekWm" }, "outputs": [], "source": [ "import numpy as np\n", "def number32(BIN):\n", "#if True:\n", " #BIN='00111110001000000000000000000000'\n", " #Inverting binary string\n", " b_inverted=np.array(list(BIN)[::-1]).astype(int)\n", " \n", " s=b_inverted[31]\n", " #Exponent part\n", " be=b_inverted[23:31]\n", " i=np.arange(be.size)\n", " e=(be*(2**i)).sum()\n", " \n", " bf=b_inverted[0:23]\n", " i_inverted=np.arange(1,bf.size+1)[::-1]\n", "\n", " numero=( (-1)**s/2**(127-e) )*( 1 + (bf/2**i_inverted).sum() ) \n", " return numero" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "colab": {}, "colab_type": "code", "id": "mWbfh4NbekWo", "outputId": "3fefa19d-b440-4a87-97e8-c9de842157a8", "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.15625\n" ] } ], "source": [ "print(number32('00111110001000000000000000000000'))" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "9psQnJf6ekWq" }, "source": [ "Check aginst the implementation with `for`'s" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "colab": {}, "colab_type": "code", "id": "ANxSuuvyekWr" }, "outputs": [], "source": [ "## %load numtobin.py\n", "def num32( binary ):\n", " #Inverting binary string\n", " binary = binary[::-1]\n", " s=binary[31]\n", " #Decimal part\n", " dec = 1\n", " for i in range(1,24):\n", " dec += int(binary[23-i])*2**-i\n", " #Exponent part\n", " exp = 0\n", " for i in range(0,8):\n", " exp += int(binary[23+i])*2**i\n", " #Total number\n", " number =( (-1)**int(s)/2**(127-exp) )*dec\n", " return number" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "colab": {}, "colab_type": "code", "id": "IUlLc8yjekWu", "outputId": "a7708d76-57a1-4bde-b201-02355da9bdb9" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.15625\n" ] } ], "source": [ "print(num32('00111110001000000000000000000000'))" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "_XvzBid9ekWw" }, "source": [ "%load sln.py" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "WJr54n_TekWx" }, "source": [ "Single-precision system can represent real numbers within the interval $\\pm 10^{-38} \\cdots 10^{38}$, with $7-8$ decimal digits." ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 163 }, "colab_type": "code", "id": "rFsolRCzekWx", "outputId": "185b8e85-53a6-4c2f-8c35-0f219d19a6b3" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "Decimal digits contributions for single precision number\n", "1.1920928955078125e-07 3.0517578125e-05 0.03125 \n", "\n", "Largest and smallest exponent for single precision number\n", "3.402823669209385e+38 5.877471754111438e-39 \n", "\n" ] } ], "source": [ "#Decimal digits \n", "print(\"\\n\")\n", "print( \"Decimal digits contributions for single precision number\")\n", "print( 2**-23., 2**-15., 2**-5. , \"\\n\")\n", "\n", "#Largest and smallest exponent \n", "emax = 0 \n", "for i in range(0,8):\n", " emax += 2**i\n", "print( \"Largest and smallest exponent for single precision number\" )\n", "print( 2**(emax-127.), 2**(-127.),\"\\n\" )" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "8qJB0mI5ekW0" }, "source": [ "#### Double-precision numbers" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "Dvz9JGLvekW0" }, "source": [ "Double-precision numbers are used when high accuracy is required. These numbers are represented by a **64-bits** (Binary digIT) lenght binary number, where the real number is stored following the next rules:\n", "\n", "![64-bits](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/IEEE_754_Double_Floating_Point_Format.svg/618px-IEEE_754_Double_Floating_Point_Format.svg.png)\n", "\n", "1. The fist digit (called *s*) indicates the sign of the number (s=0 means a positive number, s=1 a negative one).\n", "2. The next 11 bits represent the exponent of the number.\n", "3. The last bits represent the fractional part of the number.\n", "\n", "The formula for recovering the real number is then given by:\n", "\n", "$$r = (-1)^s\\times \\left( 1 + \\sum_{i=1}^{52}b_{52-i}2^{-i} \\right)\\times 2^{e-1023}$$\n", "\n", "where $s$ is the sign, $b_{23-i}$ the fraction bits and $e$ is given by:\n", "\n", "$$e = \\sum_{i=0}^{10} b_{52+i}2^i$$\n", "\n", "Double-precision system can represent real numbers within the interval $\\pm 10^{-308} \\cdots 10^{308}$, with $16-17$ decimal digits." ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1e+308" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1e307 * 10" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "inf" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1e307 * 20" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1e-323" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1e-323" ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1e-324" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "Frp255HEekW1" }, "source": [ "### ACTIVITY\n", "\n", "**1.** Write a python script that calculates the double precision number represented by a 64-bits binary.\n", "\n", " \n", "**2.** What is the number represented by:\n", "\n", "0 10000000011 1011100100001111111111111111111111111111111111111111\n", "\n", "\n", " **ANSWER:** 27.56640625" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "PuIokoT9ekW2" }, "source": [ "## Finite Arithmetic" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "4W64J6WhekW2" }, "source": [ "The most basic arithmetic operations are addition and multiplication. Further operations such as subtraction, division and power are secondary as they can be reached by iteratively use the latter ones." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "EMlWF2h_ekW3" }, "source": [ "### Addition" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "BXt1BtnPekW4" }, "source": [ "" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "scamzqF1UiO-", "outputId": "97a18d7d-b5a4-42dd-a2fc-97185eee043c" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error: 5.676632830464712e-08\n" ] } ], "source": [ "import numpy as np\n", "print(\"Error:\", np.float32(5/7.+1/3.)-22/21.)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "yJUY315tUjn-" }, "source": [ "Therefore, at the numerical computation level we must be aware that an expected \n", "zero result is really\n", "$$0\\approx 10^{-16}$$\n" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "vdb_-iBaekW_" }, "source": [ "### Multiplication" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "FY_9Ec5VekXA" }, "source": [ "For multiplication it is applied the same round-off rules as the addition, however, be aware that multiplicative errors propagate more quickly than additive errors." ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "Sj_QSq39ekXA", "outputId": "c8cc779b-b7d7-4f80-dc04-75e795eff040", "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "expected: 2.000000000000003; obtained: 1.9958053041750938\n" ] } ], "source": [ "N = 20\n", "xe=1; x = 1\n", "for i in range(N):\n", " xe *= float(2.0**(1.0/N))\n", " x *= np.float16(2.0**(1.0/N))\n", "print('expected: {}; obtained: {}'.format(xe,x))" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "colab": {}, "colab_type": "code", "id": "xYyfjPVNXfdM" }, "outputs": [], "source": [ "N = 20\n", "xe=1; x = 1\n", "for i in range(N):\n", " xe *= 2.0**(1.0/N)" ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "Q8j81laNZQf7", "outputId": "1a6b37cf-3f62-479c-e55a-98a0a5ace425" }, "outputs": [ { "data": { "text/plain": [ "3.14" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.float16(3.1415926535897932384626433832795028841971)" ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "0A-QGfXKZAAj", "outputId": "7857977b-4b31-4d4c-a492-20fce75cab80" }, "outputs": [ { "data": { "text/plain": [ "3.1415927" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.float32(3.1415926535897932384626433832795028841971)" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "eZSEwotrZqNK", "outputId": "3fbeb6c1-d2f0-4a60-c674-7786a6d04c97" }, "outputs": [ { "data": { "text/plain": [ "3.141592653589793" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "float(3.1415926535897932384626433832795028841971)" ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "yMgja3peZJIb", "outputId": "f63bfb3c-d4aa-49c2-c8f8-f32300f020cb" }, "outputs": [ { "data": { "text/plain": [ "3.141592653589793" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.float64(3.1415926535897932384626433832795028841971)" ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 35 }, "colab_type": "code", "id": "V6iuTVtpYx0z", "outputId": "b7e66df6-48ed-4483-9e00-039f96c7b748" }, "outputs": [ { "data": { "text/plain": [ "3.141592653589793116" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.float128(3.1415926535897932384626433832795028841971)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "F21OUbxcekXD" }, "source": [ "The final result has an error at the third decimal digit, one more than the case of addition." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "uvZ8RXy6ekXE" }, "source": [ "### ACTIVITY\n", "\n", "Find the error associated to the finite representation in the next operations \n", "\n", "\n", "\n", "$$\n", "x-u, \\frac{x-u}{w}, (x-u)*v, u+v \n", "$$\n", "\n", "considering the values \n", "\n", "$$\n", "x = \\frac{5}{7}, y = \\frac{1}{3}, u = 0.71425\n", "$$\n", "\n", "\n", "\n", "$$\n", "v = 0.98765\\times 10^5, w = 0.111111\\times 10^{-4}\n", "$$\n" ] } ], "metadata": { "celltoolbar": "Slideshow", "colab": { "include_colab_link": true, "name": "Copia de computer-arithmetics.ipynb", "provenance": [] }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.2" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "189px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": false, "toc_section_display": "block", "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }