{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Foundations of Computational Economics\n", "\n", "by Fedor Iskhakov, ANU\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## Representing numbers in a computer\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "[https://youtu.be/AMFCQXFtamo](https://youtu.be/AMFCQXFtamo)\n", "\n", "Description: Binary and hexadecimal numbers. Floating point numbers. Numerical stability and potential issues. Numerical noise." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Floating point arithmetics\n", "\n", "- Because computers only work with 0 and 1 internally, all real numbers\n", " have to be represented in *binary* format \n", "- This leads to many peculiar arithmetics properties of seemingly\n", " simple mathematical expressions \n", "- Understanding how computers work with real numbers is essential for\n", " computational economics " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Simple example\n", "\n", "What is the result of the comparison?" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide-output": false, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = 0.1\n", "b = 0.1\n", "c = 0.1\n", "a+b+c == 0.3" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### So can we now trust the following calculation?" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hide-output": false, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'1491.7920028601754438568605110'" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "interest = 0.04\n", "compounding = 365\n", "investment = 1000\n", "t=10\n", "daily = 1 + interest/compounding\n", "sum = investment*(daily**(compounding*t))\n", "\n", "format(sum, '.25f')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Compare to exact calculation" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "hide-output": false, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Amount computed using naive computation: 5.45976514222177001953e+11\n", "Amount computed using exact computation: 5.45976514236965270996e+11\n", "The difference is: 14.7882694559\n" ] } ], "source": [ "#using floats\n", "interest1 = 0.04\n", "compounding = 365*24\n", "t=100 #years\n", "investment1 = 10e9 #one billion\n", "daily1 = 1 + interest1/compounding\n", "sum1 = investment1*(daily1**(compounding*t))\n", "print('Amount computed using naive computation: %0.20e'%sum1)\n", "\n", "#the same using precise decimal representation\n", "from decimal import *\n", "getcontext().prec = 100 #set precision of decimal calculations\n", "interest2 = Decimal(interest1)\n", "daily2 = 1 + interest2/compounding\n", "investment2 = Decimal(investment1)\n", "sum2 = investment2*(daily2**(compounding*t)) #using exact decimals\n", "print('Amount computed using exact computation: %0.20e'%sum2)\n", "\n", "diff=sum2-Decimal.from_float(sum1)\n", "print('The difference is: %0.10f'%diff)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### So, what is happening?\n", "\n", "- Real numbers are represented with certain precision \n", "- In some cases, the errors may have economic significance \n", "- In order to write robust code suitable for the task at hand we have\n", " to understand what we should expect and why \n", "\n", "\n", "*Numerical stability* of the code is an important property!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Number representation in decimal form\n", "\n", "$ r $ — real number\n", "\n", "$ b $ — *base* (radix)\n", "\n", "$ d_0,d_1,d_2,...,d_k $ — digits (from lowest to highest)\n", "\n", "$$\n", "r = d_k \\cdot b^k + d_{k-1} \\cdot b^{k-1} + \\dots + d_2 \\cdot b^2 + d_1 \\cdot b + d_0\n", "$$\n", "\n", "For example for decimals $ b=10 $ (0,1,..,9) we have\n", "\n", "$$\n", "7,631 = 7 \\cdot 1000 + 6 \\cdot 100 + 3 \\cdot 10 + 1\n", "$$\n", "\n", "$$\n", "19,048 = 1 \\cdot 10000 + 9 \\cdot 1000 + 0 \\cdot 100 + 4 \\cdot 10 + 8\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Number representation in binary form\n", "\n", "Now let $ b=2 $, so we only have digits 0 and 1\n", "\n", "$$\n", "101011_{binary} = 1 \\cdot 2^5 + 0 \\cdot 2^4 + 1 \\cdot 2^3 + 0 \\cdot 2^2 + 1 \\cdot 2 + 1 = 43_{10}\n", "$$\n", "\n", "$$\n", "25_{10} = 16 + 8 + 1 = 2^4 + 2^3 + 2^0 = 11001_{binary}\n", "$$\n", "\n", "Other common bases are 8 and 16 (with digits\n", "$ 0,1,2,\\dots,9,a,b,c,d,e,f) $" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Counting in binary\n", "\n", "$ 0_{binary} $ $ \\rightarrow $ $ 1_{binary} $\n", "$ \\rightarrow $ $ 10_{binary} $ $ \\rightarrow $\n", "$ 11_{binary} $ $ \\rightarrow $ ??\n", "\n", "*Is it possible to count to 1000 using 10 fingers?*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### How many digits are needed?\n", "\n", "- In base-10 we need 1 digit to count up to 9, 2 digits to count up to 99 and so on \n", "- In base-2 we need 1 digit to count up to 1, 2 digits to count up to 11 = $ 3_{10} $ and so on \n", "- In base-16 we need 1 digit to count up to 15, 2 digits to count up to ff = $ 255_{10} $ and so on \n", "\n", "\n", "**In base-**$ b $ **it takes** $ n $ **digits to count up to up to** $ b^n - 1 $" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Similar structure for fractions\n", "\n", "In base-$ b $ using $ k $ *fractional* digits\n", "\n", "$$\n", "1.r = 1 + d_{-1} \\cdot b^{-1} + d_{-2} \\cdot b^{-2} + \\dots + d_{-k} \\cdot b^{-k}\n", "$$\n", "\n", "$$\n", "1.5627 = \\frac{15,627}{10,000} = 1 + 5 \\cdot 10^{-1} + 6 \\cdot 10^{-2} + 2 \\cdot 10^{-3} + 7 \\cdot 10^{-4}\n", "$$\n", "\n", "Yet, for some numbers there is no finite decimal representation\n", "\n", "$$\n", "\\frac{4}{3} = 1 + 3 \\cdot 10^{-1} + 3 \\cdot 10^{-2} + 3 \\cdot 10^{-3} + \\dots = 1.333\\dots\n", "$$\n", "\n", "$$\n", "\\frac{4}{3} = 1 + \\frac{1}{3} = 1 + \\frac{10}{3} 10^{-1} = 1 + 3 \\cdot 10^{-1} + \\frac{1}{3}10^{-1}\n", "$$\n", "\n", "$$\n", "= 1.3 + \\frac{10}{3} \\cdot 10^{-2} = 1.3 + 3 \\cdot 10^{-2} + \\frac{1}{3}10^{-2}\n", "$$\n", "\n", "$$\n", "= 1.33 + \\frac{10}{3} \\cdot 10^{-3} = 1.33 + 3 \\cdot 10^{-3} + \\frac{1}{3}10^{-3} = \\dots\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### In binary\n", "\n", "$$\n", "0.1 =\\frac{1}{10} = \\frac{16}{10} 2^{-4} = 0.0001_b + \\frac{6}{10} 2^{-4} =\n", "$$\n", "\n", "$$\n", "0.0001_b + \\frac{12}{10} 2^{-5} = 0.00011_b + \\frac{2}{10} 2^{-5} =\n", "$$\n", "\n", "$$\n", "0.00011_b + \\frac{16}{10} 2^{-8} = 0.00011001_b + \\frac{6}{10} 2^{-8} = 0.000110011...\n", "$$\n", "\n", "Therefore $ 0.1 $ can not be represented in binary exactly!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Scientific notation\n", "\n", "$$\n", "r = r_0 \\cdot b ^ e\n", "$$\n", "\n", "$ 0 \\le r_0 < b $ — mantissa (coefficient)\n", "\n", "$ b $ — base (radix)\n", "\n", "$ e $ — exponent\n", "\n", "- Useful for writing both big and small numbers \n", "- *Approximate representation when a finite number of digits are used to record the mantissa* " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Rounding error\n", "\n", "Squeezing infinitely many real numbers into a finite number of *bits*\n", "requires an approximate representation\n", "\n", "$ p $ — number of digits in the representation for $ r_0 $\n", "\n", "$ e $ — exponent between $ e_{min} $ and $ e_{max} $, taking up $ p_e $ bits to encode\n", "\n", "$$\n", "r \\approx \\pm d_0. d_1 d_2 \\dots d_p \\cdot b^e\n", "$$\n", "\n", "The float takes the total of $ 1 + p + p_e $ digits + one bit for the sign" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Bits in float point representation\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Distribution of representable real numbers\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### The main issues to be aware of\n", "\n", "1. Rounding errors $ \\leftrightarrow $ loss of precision when\n", " numbers are represented in binary form $ \\Rightarrow $ can not\n", " compare floats for equality \n", "1. Catastrophic cancellation $ \\leftrightarrow $ potential drastic\n", " loss of precision when substracting close real numbers represented by\n", " floats $ \\Rightarrow $ innocent formulas may in fact be\n", " numerically unstable \n", "1. Overflow $ \\leftrightarrow $ obtaining a real number that is too\n", " large to be represented as float \n", "1. Underflow $ \\leftrightarrow $ obtaining a real number that is\n", " indistinguishable from zero \n", "\n", "\n", "*Look at these cases in the Lab*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Further learning resources\n", "\n", "- Binary arithmetics on paper and in electronic circuit\n", " [https://www.youtube.com/watch?v=wvJc9CZcvBc](https://www.youtube.com/watch?v=wvJc9CZcvBc) \n", "- Counting to 1024 using fingers\n", " [https://www.youtube.com/watch?v=UixU1oRW64Q](https://www.youtube.com/watch?v=UixU1oRW64Q) \n", "- Basic intro into floating-point representation\n", " [https://www.youtube.com/watch?v=PZRI1IfStY0](https://www.youtube.com/watch?v=PZRI1IfStY0) \n", "- “What Every Computer Scientist Should Know About Floating-Point Arithmetics” by David Goldberg (pdf)\n", " [http://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf](http://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf) " ] } ], "metadata": { "celltoolbar": "Slideshow", "date": 1612589584.3453782, "download_nb": false, "filename": "03_numbers.rst", "filename_with_path": "03_numbers", "kernelspec": { "display_name": "Python", "language": "python3", "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.7.6" }, "title": "Foundations of Computational Economics" }, "nbformat": 4, "nbformat_minor": 4 }