{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"CPSC231-4Data.ipynb","provenance":[],"authorship_tag":"ABX9TyMfmp1DCuJ+XYpnWuzZ7MjY"},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"0BSE6wknoqJ2"},"source":["# Topic 4: Information and Data"]},{"cell_type":"markdown","metadata":{"id":"cJrB__Blr-KV"},"source":["## Base 2 decimals"]},{"cell_type":"markdown","metadata":{"id":"IgZoN08eovEO"},"source":["A decimal number is a sum of values in 10s, 100s, 1000s and 1/10s, 1/100s, 1/1000s, etc\n","\n","Ex.\n","\n","1/8 in base 10\n","\n","0.125 base 10 = 1/10 + 2/100 + 5/1000 in base 10"]},{"cell_type":"markdown","metadata":{"id":"oGpcN_rwpA7F"},"source":["We can represent a binary decimal the same way\n","2s, 4s, 8s, and 1/2s, 1/4s, 1/8s\n","\n","Ex.\n","\n","1/8 in base 10 to base 2\n","\n","0.001 base 2 = 0/2 + 0/4 + 1/8 \n"]},{"cell_type":"markdown","metadata":{"id":"at11QfSGp41-"},"source":["Some numbers are not repeating in either base like 1/8\n","\n","However some are\n","\n","0.1 = 1/10 is non-repeating in base 10\n","\n","but is repeating in base 2"]},{"cell_type":"markdown","metadata":{"id":"_9r_mwI_pXOW"},"source":["You've done decimal approximation in the past. Often when you need to approximate a base 10 number you do\n","\n","1/3 = 0.33333..... repeating\n","\n","or use \n","\n","3/10 or 33/100 or 333/1000 for a level of accuracy"]},{"cell_type":"markdown","metadata":{"id":"hY6ExRmDpvqG"},"source":["However what is repeating in base 10 is not repeating in base 2\n","\n","1/10 which is not repeating in base 10 is repeating in base 2\n","\n","1/8 is not repeating in base 2 or base 10\n"]},{"cell_type":"markdown","metadata":{"id":"qr0RlImIry6l"},"source":["Convering 0.1 base 10 to base 2\n","\n","0.1 * 2 = 0.2   -> 0\n","\n","0.2 * 2 = 0.4   -> 0\n","\n","0.4 * 2 = 0.8   -> 0\n","\n","0.8 * 2 = 1.6   -> 1\n","\n","0.6 * 2 = 1.2   -> 1\n","\n","0.2 * 2 = 0.4   -> 0\n","\n"," ... forever\n","\n","0.0001100110011001100... base 2"]},{"cell_type":"markdown","metadata":{"id":"4SKk1Q9PsA4t"},"source":["## Danger of repeating base 2 decimals"]},{"cell_type":"markdown","metadata":{"id":"Yh8aEZ29sIKt"},"source":["Let's look at what is stored for some base 10 decimals in python"]},{"cell_type":"code","metadata":{"id":"ds9DAEnzpp4i","executionInfo":{"status":"ok","timestamp":1601320884942,"user_tz":360,"elapsed":614,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"685e4089-0e4c-4ebd-c40e-df2801ff0dd3","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["print(1/10)\n","print(1/8)"],"execution_count":1,"outputs":[{"output_type":"stream","text":["0.1\n","0.125\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"GFI_fbcbsR2t"},"source":["Seems fine?"]},{"cell_type":"code","metadata":{"id":"8zjOGQ0EsSzl","executionInfo":{"status":"ok","timestamp":1598477681652,"user_tz":360,"elapsed":345,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"e2a346b5-335d-41b9-bb39-4c9826c884d8","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["print(\"%.50f\" % (1/10))\n","print(\"%.50f\" % (1/8))"],"execution_count":null,"outputs":[{"output_type":"stream","text":["0.10000000000000000555111512312578270211815834045410\n","0.12500000000000000000000000000000000000000000000000\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"ZBCuUiB7sdz-"},"source":["Wait that's a lot of junk in the 1/10?"]},{"cell_type":"markdown","metadata":{"id":"hQjMzHQ-siS-"},"source":["## Storing base 2 fractions (storing floating point numbers in python)"]},{"cell_type":"markdown","metadata":{"id":"E1q6jMptsqIV"},"source":["We use binary fractions to represent floats\n"]},{"cell_type":"code","metadata":{"id":"126mtQ9Lsuz-","executionInfo":{"status":"ok","timestamp":1598477844412,"user_tz":360,"elapsed":344,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"91bff0a9-aac8-434e-d7e7-71141f15faf7","colab":{"base_uri":"https://localhost:8080/","height":68}},"source":["var = 1/10\n","#Before garbage is seen\n","print(\"%.16f\" % var)\n","#Bit of garbage\n","print(\"%.17f\" % var)\n","#All the garbage\n","print(\"%.55f\" % var)"],"execution_count":null,"outputs":[{"output_type":"stream","text":["0.1000000000000000\n","0.10000000000000001\n","0.1000000000000000055511151231257827021181583404541015625\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"z4HGSJU7s5W-"},"source":["I'm going to recreate that garbage filled float"]},{"cell_type":"code","metadata":{"id":"lX4Y86Egs-EG","executionInfo":{"status":"ok","timestamp":1601310410507,"user_tz":360,"elapsed":507,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"cfe3cf76-ad12-47e6-dd87-26b8bfcdb884","colab":{"base_uri":"https://localhost:8080/","height":34}},"source":["num = 3602879701896397 / (2 ** 55)\n","print(\"%.55f\" % (num))\n"],"execution_count":3,"outputs":[{"output_type":"stream","text":["0.1000000000000000055511151231257827021181583404541015625\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"cBTAkO2atAiX"},"source":["How did I know that"]},{"cell_type":"code","metadata":{"id":"AYoc07hPtABW","executionInfo":{"status":"ok","timestamp":1601310588215,"user_tz":360,"elapsed":649,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"2ee92fce-d197-4eb8-831e-9ec3935539ef","colab":{"base_uri":"https://localhost:8080/","height":68}},"source":["var = 0.1\n","print(var.as_integer_ratio())\n","print(3602879701896397)\n","print((2 ** 55))"],"execution_count":5,"outputs":[{"output_type":"stream","text":["(3602879701896397, 36028797018963968)\n","3602879701896397\n","36028797018963968\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"mxqUphYJtYn4"},"source":["Store a numerator (integer) using first 53 bits (1 is sign bit) \n","\n","Store a exponent (integer) using 11 bits"]},{"cell_type":"markdown","metadata":{"id":"eA2JijtqtAPG"},"source":["## What are the issues?"]},{"cell_type":"markdown","metadata":{"id":"J3j9bA7Etztl"},"source":["Floating point error. This can really screw up your math program. Doing 'math class' is not doing the same as 'computing' math"]},{"cell_type":"code","metadata":{"id":"jAxV5gOPtkht","executionInfo":{"status":"ok","timestamp":1601321351727,"user_tz":360,"elapsed":354,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"03c384e4-37aa-4d67-cf1e-64bf8b2f8563","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["print(0.1+0.1+0.1)\n","print(0.3)"],"execution_count":2,"outputs":[{"output_type":"stream","text":["0.30000000000000004\n","0.3\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"0Exch0Ootpz9","executionInfo":{"status":"ok","timestamp":1598478001028,"user_tz":360,"elapsed":343,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"ddc6a8d2-7faf-46af-92c7-36b6e867110d","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["print(\"%.55f\" % (0.1+0.1+0.1))\n","print(\"%.55f\" % (0.3))"],"execution_count":null,"outputs":[{"output_type":"stream","text":["0.3000000000000000444089209850062616169452667236328125000\n","0.2999999999999999888977697537484345957636833190917968750\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"e43RnxLbtr4f","executionInfo":{"status":"ok","timestamp":1601310843335,"user_tz":360,"elapsed":444,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"6ffe793f-a202-4991-cf63-3bcb16456d3e","colab":{"base_uri":"https://localhost:8080/","height":34}},"source":["print( (0.1+0.1+0.1) == (0.3) )"],"execution_count":8,"outputs":[{"output_type":"stream","text":["False\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"CeTRhPEQtvNO","executionInfo":{"status":"ok","timestamp":1601310887228,"user_tz":360,"elapsed":447,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"1626893f-5484-489d-95bb-957dee3fb0bf","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["var1 = 0.1+0.1+0.1\n","var2 = 0.3\n","print(var1.as_integer_ratio())\n","print(var2.as_integer_ratio())"],"execution_count":9,"outputs":[{"output_type":"stream","text":["(1351079888211149, 4503599627370496)\n","(5404319552844595, 18014398509481984)\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"4CMXrfHVkZ81","executionInfo":{"status":"ok","timestamp":1601321656779,"user_tz":360,"elapsed":310,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"0182dc18-3661-4e7a-8e3e-ae8f77513d07","colab":{"base_uri":"https://localhost:8080/","height":34}},"source":["epsilon = 0.0000000001\n","print( abs((0.1+0.1+0.1) - 0.3) < epsilon) "],"execution_count":6,"outputs":[{"output_type":"stream","text":["True\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"uVIB3p7atyRN","executionInfo":{"status":"ok","timestamp":1601321606155,"user_tz":360,"elapsed":338,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"8cce0ea1-4b1a-4deb-b9dd-4ee2ee41e269","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["print(0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1)\n","print(\"%.55f\" % (0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1))"],"execution_count":3,"outputs":[{"output_type":"stream","text":["10\n","10.0000000000000000000000000000000000000000000000000000000\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"BlP_Rq-ft_xF"},"source":["## Max representation sizes"]},{"cell_type":"markdown","metadata":{"id":"OkHxIVtWuJgF"},"source":["Integers"]},{"cell_type":"code","metadata":{"id":"UJPKjqK3uEQB","executionInfo":{"status":"ok","timestamp":1601321734263,"user_tz":360,"elapsed":378,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"400a0732-9385-4f94-a69a-a6ab2a98dddc","colab":{"base_uri":"https://localhost:8080/","height":68}},"source":["import sys\n","print(sys.maxsize)\n","##32 bit computer\n","print(2**31-1)\n","##64 bit computer\n","print(2**63-1)\n","\n"],"execution_count":7,"outputs":[{"output_type":"stream","text":["9223372036854775807\n","2147483647\n","9223372036854775807\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"PfXvXZcQuSKt"},"source":["However if we overflow our int (integer) type then python uses a different storage structure to get a bigger size"]},{"cell_type":"code","metadata":{"id":"YI2mRu3EuQu9","executionInfo":{"status":"ok","timestamp":1601311187284,"user_tz":360,"elapsed":478,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"0eebf963-c433-49b7-bf89-e5550c9b99cb","colab":{"base_uri":"https://localhost:8080/","height":51}},"source":["print(sys.maxsize+1)"],"execution_count":15,"outputs":[{"output_type":"stream","text":["9223372036854775808\n","<class 'int'>\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"97-oSGfvuhUm"},"source":["Floating points"]},{"cell_type":"code","metadata":{"id":"Lv0fJiYtoSJx","executionInfo":{"status":"ok","timestamp":1601322004165,"user_tz":360,"elapsed":528,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"8809bbdd-9fbd-4b4d-a968-bd47c9cc07aa","colab":{"base_uri":"https://localhost:8080/","height":71}},"source":["print(\"%.100f\" % sys.float_info.max)\n","print(sys.float_info.max.as_integer_ratio())\n","\n","\n","\n","\n","\n"],"execution_count":8,"outputs":[{"output_type":"stream","text":["179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n","(179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368, 1)\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"IsJnC2Wkulpf"},"source":["Note if we get bigger from our max floating point that info just disappears"]},{"cell_type":"code","metadata":{"id":"yQNDSYtwulF-","executionInfo":{"status":"ok","timestamp":1601322099476,"user_tz":360,"elapsed":343,"user":{"displayName":"Jonathan Hudson","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GifRN6odU4-8ypKAmFbKYslWLQ1fivgoGwgrjiH6ZI=s64","userId":"10663523637423141362"}},"outputId":"f8cc7b8d-0cc2-4075-ebf7-18575bca3e89","colab":{"base_uri":"https://localhost:8080/","height":123}},"source":["\n","print(\"%.100f\" % (sys.float_info.max+1))\n","print((sys.float_info.max== (sys.float_info.max+1)))\n","print((sys.float_info.max== (sys.float_info.max+0.1)))\n","\n","\n","print(sys.float_info.max.as_integer_ratio())\n","\n","print((sys.float_info.max+1).as_integer_ratio())\n"],"execution_count":9,"outputs":[{"output_type":"stream","text":["179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n","True\n","True\n","(179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368, 1)\n","(179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368, 1)\n"],"name":"stdout"}]}]}