02_NumberRepresentation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Integers\n",
    "\n",
    "Integer numbers are represented by N bit words. Python3 allows you to store integers with practically **unlimited precision**, the only limitation comes from the (contiguous) space available in memory.\n",
    "In Python2 (deprecated), N depends on the PC architercture, N=64 in modern computers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check the largest integer\n",
    "import sys\n",
    "print(sys.maxsize)\n",
    "\n",
    "# Check also that corresponds to a 64-bit integer\n",
    "print(\"Is your system a 64 bit one?\", 2**63 - 1 == sys.maxsize)\n",
    "\n",
    "# Python 3 doesn't have a limit for integers\n",
    "maxint = sys.maxsize+1\n",
    "print(maxint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary and Hexadecimal representations\n",
    "\n",
    "The common assumption is that numbers (in Python as in all the other languages) are expressed as decimal numbers. Built-in functions allows explicitly to convert from one base to another.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the binary representation, typically 1 bit ($j$) is dedicated to specifying the sign of the number, and the conversion between binary and decimal representation is:\n",
    "\n",
    "$$d = (-1)^j\\sum_{i=0}^{N-1} \\alpha_i ~ 2^i$$\n",
    "\n",
    "where $\\alpha_i$ are either 0 or 1. \n",
    "$b=\\alpha_{N-1}\\alpha_{N-2}..\\alpha_0$ is the binary representation of the number.\n",
    "\n",
    "Example: an 8-bit integer in binary representation with one bit for the sign:\n",
    "\n",
    "|  j | 6 | 5 | 4 | 3 | 2 | 1 | 0  |\n",
    "|---|---|---|---|---|---|---|---|\n",
    "|  0 | 0 | 0 | 1 | 0 | 1 | 1 | 1  |\n",
    "\n",
    "corresponds to:\n",
    "\n",
    "$$d = (-1)^j\\sum_{i=0}^{N-1} \\alpha_i ~ 2^i = (-1)^{0} [ (1) \\cdot 2^0 + (1) \\cdot 2^1 + (1) \\cdot 2^2 + (0) \\cdot 2^3 + (1) \\cdot 2^4 + (0) \\cdot 2^5 + (0) \\cdot 2^6] = 0 + 1 + 2 + 4 + 16 = 23$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# an integer in decimal representation\n",
    "a = 23\n",
    "\n",
    "# its binary representation\n",
    "a_bin = bin(a)\n",
    "print('Binary representation of', a, ':', a_bin)\n",
    "\n",
    "# its hexadecimal representation\n",
    "a_hex = hex(a)\n",
    "print('Hexadecimal representation of', a, ':', a_hex)\n",
    "\n",
    "# converting back to integer\n",
    "print('Decimal representation of', a_bin, ':', int(a_bin, 2))\n",
    "print('Decimal representation of', a_hex, ':', int(a_hex, 16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bitwise operators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Logical operators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 60           # 60 = 0011 1100 \n",
    "b = 13           # 13 = 0000 1101 \n",
    "\n",
    "c = a & b        # 12 = 0000 1100\n",
    "print(\"Bitwise AND \", c)\n",
    "\n",
    "c = a | b        # 61 = 0011 1101 \n",
    "print(\"Bitwise OR  \", c)\n",
    "\n",
    "c = a ^ b        # 49 = 0011 0001\n",
    "print(\"Bitwise XOR \", c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Unary operators\n",
    "\n",
    "#### bitwise NOT\n",
    "given an integer *a*:\n",
    "\n",
    "`\n",
    "~a = ~bin(a)\n",
    "   = -(bin(a)+1)\n",
    "`\n",
    "\n",
    "i.e. it returns the complement to (-) 1 of that number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#int(\"0b11000011\",2)\n",
    "print(bin(-61),bin(~60))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = ~a           # -61 = 1100 0011\n",
    "print(\"Bitwise NOT \", c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shifts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = a << 2       # 240 = 1111 0000\n",
    "print(\"Left shift (towards most significant) of two positions \", c)\n",
    "\n",
    "c = a >> 2       # 15 = 0000 1111\n",
    "print(\"Right shift (towards least significant) of two positions \", c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more details check the python [documentation](https://realpython.com/python-bitwise-operators/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Floating point numbers\n",
    "\n",
    "Non-integer number **cannot be represented with infinite precision** on a computer. Single precision (also known as *float*) and double precision numbers use 32 and 64 bits respectively. \n",
    "Note that all floating point numbers in python are double precision (64 bits).\n",
    "A standard has been developed by IEEE such that the relative precision (see later) is the same across the whole validity range.\n",
    "\n",
    "The 32 or 64 bits are divided among 3 quantities uniquely characterizing the number:\n",
    "\n",
    "$x_{float} = (-1)^s \\times 1.f \\times 2^{e-bias}$\n",
    "\n",
    "where *s* is the sign, *f* the fractional part of the mantissa and *e* the exponent. In order to get numbers in modulo smaller than 1, a constant *bias* term is added to the exponent, such *bias* is typically equal to half of the max value of *e*.\n",
    "The mantissa is defined as:\n",
    "\n",
    "${\\rm mantissa}=1.f=1+m_{n-1}2^{-1}+m_{n-2}2^{-2}+..+m_{0}2^{-n}$\n",
    "\n",
    "where $n$ is the number of bits dedicated to *f* (see below) and $m_i$ are the binary coefficients. \n",
    "\n",
    "Numbers exceeding the maximum allowed value are *overflows* and the calculations involving them provide incorrect answers. Numbers smaller in absolute value than the minimum allowed value are *underflows* and simply set to zero, also in this case incorrect results are yielded.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Single\n",
    "\n",
    "For single precision floating point numbers, $0\\le e \\le 255$ and $bias=127$. Bits are arranged as follows:\n",
    "\n",
    "|   | *s* | *e* | *f* |\n",
    "|---|---|---|---|\n",
    "| Bit position | 31 | 30-23 | 22-0 |\n",
    "\n",
    "An example is given below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import Image\n",
    "Image(url='http://www.dspguide.com/graphics/F_4_2.gif')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Special values are also possibiles. N.B.: those are not numbers that can be used in the mathematical sense!\n",
    "\n",
    "|   |  conditions | value |\n",
    "|---|---|---|\n",
    "|  $+\\infty$ | s=0, e=255, f=0 | +INF  |\n",
    "|  $-\\infty$ | s=1, e=255, f=0 | -INF  |\n",
    "|  not a number | e=255, f>0  | NaN  |\n",
    "\n",
    "The largest value is obtained for $f\\sim 2$ and $e=254$, i.e. $2\\times2^{127}\\sim 3.4\\times10^{38}$.\n",
    "\n",
    "The value closest to zero is obtained instead for $f=2^{-23}$ and $e=0$, i.e. $2^{-149}\\sim 1.4\\times10^{-45}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Double\n",
    "\n",
    "For double precision floating point numbers, $0\\le e \\le 2047$ and $bias=1023$. Bits are arranged as follows:\n",
    "\n",
    "|   | *s* | *e* | *f* |\n",
    "|---|---|---|---|\n",
    "| Bit position | 63 | 62-52 | 51-0 |\n",
    "\n",
    "Special values are also possibiles. N.B.: those are not numbers that can be used in the mathematical sense!\n",
    "\n",
    "|   |  conditions | value |\n",
    "|---|---|---|\n",
    "|  $+\\infty$ | s=0, e=2047, f=0 | +INF  |\n",
    "|  $-\\infty$ | s=1, e=2047, f=0 | -INF  |\n",
    "|  not a number | e=2047, f>0  | NaN  |\n",
    "\n",
    "The validity range for double numbers is $2.2^{-308} - 1.8^{308}$\n",
    "\n",
    "Serious scientific calculations almost always requires at least double precision floating point numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Floating point numbers on your system\n",
    "\n",
    "Information about the floating point reresentation on your system can be obtained from sys.float_info. Definitions of the stored values are given on the python doc [page](https://docs.python.org/2/library/sys.html#sys.float_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "print(sys.float_info)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Accuracy and the perils of calculations with floats\n",
    "\n",
    "\n",
    "Floats can only have a limited number of meaningful decimal places, on the basis of how many bits are allocated for the fractional part of the mantissa: 6-7 decimal places for singles, 15-16 for doubles. In particular this means that calculations involving numbers with more than those decimal places involved do not yield the correct result, simply because the binary representation of those numbers does not allow to store them with sufficient accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Addding an increasingly small number to 7\n",
    "for e in [14, 15, 16]: print (7+1.0*10**-e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It should never been forgotten that computers store numbers in binary format. In the same way it is not possible to express the fraction 1/3 with a finite decimal places, analogously fraction well represented in the decimal base cannot be represented in binary, e.g. 1/10 is the infinitely repeating number:\n",
    "\n",
    "$0.0001100110011001100110011001100110011001100110011...$\n",
    "\n",
    "corresponding to $3602879701896397/2^{55}$ which is close to but not exactly equal to the true value of 1/10 (even though it is even printed to be like that!).\n",
    "Similarly 0.1 is not 1/10, and making calculations assuming that exactly typically yield to wrong results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print (1 / 10, 0.1)\n",
    "\n",
    "# is 1/10 the same of 0.1?\n",
    "print (1 / 10 == 0.1)\n",
    "\n",
    "# but then watch out! Does it work for 0.3, too?\n",
    "print (0.1 + 0.2 == 0.3)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A lesson of paramount importance is that you must **never** compare floating point numbers with the \"==\" operator as *what is printed is not what is stored*!\n",
    "\n",
    "The function ```float.hex()``` yield the exact value stored for a floating point number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "x = math.pi\n",
    "print(x)\n",
    "print(x.hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are ways to print floats (e.g. filling data into an output file) controlling the number of decimals:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(format(math.pi, '.13f'))  # give 13 significant digits\n",
    "\n",
    "print('%.13f' % (0.1 * 0.1 * 100)) \n",
    "\n",
    "# now repeat trying with >15 digits!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no bug here, this is simply due to the fact that the mantissa is represented by a limited amount of bits, therefore calculations can only make sense if an appropriate number of decimal digits are concerned:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 23 bits are used for f in single precision floating point\n",
    "print(\"Single precision:\", 2**-23)\n",
    "\n",
    "# 53 bits are used for f in double precision floating point\n",
    "print(\"Double precision:\", 2**-53)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A typical case is subtraction of numbers very close by in value (e.g. when dealing with spectral frequencies). The same happens with functions evaluated near critical points (see later)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 + 6.022e23 - 6.022e23"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Associative law does not necessarily hold:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print (6.022e23 - 6.022e23 + 1)\n",
    "print (1 + 6.022e23 - 6.022e23)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Distributive law does not hold"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "a = math.exp(1)\n",
    "b = math.pi\n",
    "c = math.sin(1)\n",
    "a*(b + c) == a*b + a*c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also identities after casting large numbers may not yield the expected result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 287475839859383374\n",
    "print(x == int(float(x)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## From numbers to functions: conditioning and stability\n",
    "\n",
    "#### Function conditioning\n",
    "\n",
    "A mathematical function $f(x)$ is well-conditioned if $f(x+\\epsilon)\\simeq f(x)$ for all small perturbations $\\epsilon$.\n",
    "\n",
    "In other words, the function $f(x)$ is **well-conditioned** if the solution varies gradually as the input varies. For a well-conditioned function, small pertubations in the input result in small effects in the output. However, a poorly-conditioned problem only needs some small perturbation to have large effects. For example, inverting a nearly singluar matrix (a matrix whose determinant is close to zero) is a poorly conditioned problem.\n",
    "\n",
    "#### Algorithm stability\n",
    "\n",
    "Suppose we have a computer algorithm $g(x)$ that represents the mathematical function $f(x)$. $g(x)$ is **numerically stable** if $g(x+\\epsilon) \\simeq f(x)$ and it is called **unstable** if large changes in the output are produced. Analyzing an algorithm for stability is more complicated than determining the condition of an expression, even if the algorithm simply evaluates the expression. This is because an algorithm consists of many basic calculations and each one must be analyzed and, due to roundoff error, we must consider the possibility of small errors being introduced in every computed value.\n",
    "\n",
    "Numerically unstable algorithms tend to amplify approximation errors due to computer arithmetic over time. If we used an infinite precision numerical system, stable and unstable alorithms would have the same accuracy. However, as we see below (e.g. variance calculation), when using floating point numbers, algebrically equivalent algorithms can give different results.\n",
    "\n",
    "In general, we need both a well-conditioned problem and an algorihtm with sufficient numerical stabilty to obtain reliably accurate answers. In this case, we can be sure that $g(x) \\simeq f(x)$.\n",
    "\n",
    "In most of the cases, the solution to stability issues is solved by properly redefining the function as in the example above and below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Example of a poorly conditioned function: the tangent of an angle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "# Define two numbers x and x + epsilon very close to pi/2\n",
    "x1 = 1.57078\n",
    "x2 = 1.57079\n",
    "# Calculate the tangent of the x1 and x2 angles\n",
    "t1 = math.tan(x1)\n",
    "t2 = math.tan(x2)\n",
    "\n",
    "print ('tan(x1) =', t1)\n",
    "print ('tan(x2) =', t2)\n",
    "print ('% change in x =', 100.0*(x2-x1)/x1, '%')\n",
    "print ('% change in tan(x) =', (100.0*(t2-t1)/t1), '%')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Example of a numerically unstable algorithm: the limit      $\\lim_{x \\to 0} \\frac{1-\\cos(x)}{x^2}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Catastrophic cancellation occurs when subtracitng\n",
    "# two numbers that are very close to one another\n",
    "# Here is another example\n",
    "\n",
    "# We'll see numpy and matplotlib in the next lectures: forget about the technical details, for now\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def f(x):\n",
    "    return (1 - np.cos(x))/(x*x)\n",
    "\n",
    "#x = np.linspace(-4e-1, 4e-1, 1000)\n",
    "x = np.linspace(-4e-8, 4e-8, 1000)\n",
    "plt.plot(x, f(x))\n",
    "plt.axvline(1.1e-8, color='red')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We know from L'Hopital's rule that the answer is 0.5 at 0\n",
    "# and should be very close to 0.5 throughout this tiny interval\n",
    "# but errors arisee due to catastrophic cancellation\n",
    "\n",
    "print('%.30f' % np.cos(1.1e-8))\n",
    "print('%.30f' % (1 - np.cos(1.1e-8))) # failure point: the exact answer is 6.05e-17\n",
    "print('%2f' % ((1 - np.cos(1.1e-8))/(1.1e-8*1.1e-8)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: rewrite the function using $\\sin$ instead of $\\cos$: $1-\\cos(x)$ = $2 \\sin^2 (\\frac{x}{2})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Numerically stable version of funtion using simple trignometry\n",
    "\n",
    "def f1(x):\n",
    "    return 2*np.sin(x/2)**2/(x*x)\n",
    "\n",
    "#x = np.linspace(-4e-1, 4e-1, 1000)\n",
    "x = np.linspace(-4e-8, 4e-8, 1000)\n",
    "plt.plot(x, f1(x))\n",
    "plt.axvline(1.1e-8, color='red')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Another common example of a numerically unstable algorithm. The stable and unstable version of the (unbiased sample) variance:\n",
    "\n",
    "$s^2 = \\frac{1}{n-1} \\sum (x-\\bar{x})^2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# direct method\n",
    "# squaring occuring after subtraction\n",
    "def direct_var(x):\n",
    "    n = len(x)\n",
    "    xbar = np.mean(x)\n",
    "    return 1.0/(n-1)*np.sum((x - xbar)**2)\n",
    "\n",
    "# sum of squares method (vectorized version)\n",
    "# pay attention to the subtraction of two large numbers\n",
    "def sum_of_squares_var(x):\n",
    "    n = len(x)\n",
    "    return (1.0/(n*(n-1))*(n*np.sum(x**2) - (np.sum(x))**2))\n",
    "\n",
    "# Welford's method\n",
    "# an optimized method\n",
    "def welford_var(x):\n",
    "    s = 0\n",
    "    m = x[0]\n",
    "    for i in range(1, len(x)):\n",
    "        m += (x[i]-m)/i\n",
    "        s += (x[i]-m)**2\n",
    "    return s/(len(x) - 1)\n",
    "\n",
    "\n",
    "# check the performances with an array \n",
    "# of randomly distributed data around 1e12\n",
    "x_ = np.random.uniform(0, 1, int(1e3))\n",
    "x = 1e12 + x_\n",
    "\n",
    "# correct answer from a purpose-built function in numpy\n",
    "print(\"Numpy:\", np.var(x_))\n",
    "print(\"Direct:\", direct_var(x))\n",
    "print(\"Sum of squares:\", sum_of_squares_var(x))\n",
    "print(\"Welford's:\", welford_var(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. The example of the Likelihood: $\\mathcal{L} = \\prod_{i=0}^{N} prob(x, \\mu)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# loss of precision can be a problem when calculating Likelihoods\n",
    "probs = np.random.random(1000) # Generating 1000 random numbers between 0 and 1, as if they were probabilities\n",
    "#print(probs)\n",
    "print(\"L =\", np.prod(probs))\n",
    "\n",
    "# when multiplying lots of small numbers, work in log space\n",
    "print(\"log L =\", np.sum(np.log(probs)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Summary:\n",
    "\n",
    "- Well-/ill-Conditioned refers to the problem; Stable/Unstable refers to an algorithm or numerical process.\n",
    "- If the problem is well-conditioned then there is a stable way to solve it.\n",
    "- If the problem is ill-conditioned then there is no reliable way to solve it in a stable way.\n",
    "- Mixing roundoff-error with an unstable process is a recipe for disaster.\n",
    "- With exact arithmetic (no roundoff-error), stability is not a concern."
   ]
  }
 ],
 "metadata": {
  "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}