{
"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
}