02_NumberRepresentation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Integers\n",
    "\n",
    "Integrers number are represented by N bits words. Python 3 allows you to store integers with practically unlimited precision, the only limitation comes from the (contiguos) space available in memory.\n",
    "In python 2, N depends on the PC architercture, N=64 in modern computers.\n",
    "\n",
    "Typically 1 bit is dedicated to specifying the sign of the number, thus 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "print (sys.maxsize)\n",
    "\n",
    "# check \n",
    "print (2**63-1 == sys.maxsize)\n",
    "\n",
    "# python 3 doesn't have a limit for integers\n",
    "print (sys.maxsize+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "incidentally note that python 3 recast int to floats when dividing them with `/`. To keep the old functionality of `/`, use instead `//`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print (2/3)\n",
    "print (2//3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary and Hexadecimal representations\n",
    "\n",
    "numbers values (in python as all the other languages) are assumed to be expressed as decimal. Built-in functions allows explicitly to convert from one representation to another.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# an integer in decimal representation\n",
    "a=18\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))\n",
    "\n"
   ]
  },
  {
   "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 (\"Logical AND \", c)\n",
    "\n",
    "c = a | b;        # 61 = 0011 1101 \n",
    "print (\"Logical OR \", c)\n",
    "\n",
    "c = a ^ b;        # 49 = 0011 0001\n",
    "print (\"Logical XOR \", c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Unary operators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = ~a;           # -61 = 1100 0011\n",
    "print (\"Negation of a  \", c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Masks and 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": [
    "# Floating point numbers\n",
    "\n",
    "non-integer number cannot be represent with infinite precision on a computer. Single (also known as *float*) and double precision numbers are assigned 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 in 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 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",
    "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",
    "\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": [
    "### 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 could not store them properly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "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": [
    "# is 1/10 the same of 0.1?\n",
    "print (1/10)\n",
    "\n",
    "# but then whatch out!!\n",
    "0.1 + 0.1 + 0.1 == 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": {},
   "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 ('%.17f' % (0.1 * 0.1 * 100)) # give 15 significant digits\n",
    "\n",
    "# now repeat trying with >15 digits!\n"
   ]
  },
  {
   "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 a corresponding 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 points \n",
    "print (2**-23)\n",
    "\n",
    "# 53 bits are used for f in single precision floating points \n",
    "print (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)\n"
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (we'll see numpy soon, bear with me for the moment)\n",
    "\n",
    "# loss of precision can be a problem when calculating likelihoods\n",
    "import numpy as np\n",
    "probs = np.random.random(1000)\n",
    "print (np.prod(probs))\n",
    "\n",
    "# when multiplying lots of small numbers, work in log space\n",
    "print (np.sum(np.log(probs)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## From numbers to Functions: Stability and conditioning\n",
    "\n",
    "\n",
    "Suppose we have a computer algorithm $g(x)$ that represents the mathematical function $f(x)$. $g(x)$ is stable if for some small perturbation $\\epsilon$, $g(x+\\epsilon)\\simeq f(x)$\n",
    "\n",
    "A mathematical function $f(x)$ is well-conditioned if $f(x+\\epsilon)\\simeq f(x)$ for all small perturbations $\\epsilon$.\n",
    "\n",
    "That is, the functionf(x) is **well-conditioned** if the solution varies gradually as problem varies. For a well-conditinoed function, all small pertubations have small effects. However, a poorly-conditioned problem only needs some small perturbation to have large effects. For example, inverting a nearly singluar matrix is a poorly conditioned problem.\n",
    "\n",
    "A numerical algorithm $g(x)$ is numerically-stable if $g(x)\\simeq f(x′)$ for some $x′\\simeq x$. Note that stability is a property that relates the algorithm $g(x)$ to the problem $f(x)$.\n",
    "\n",
    "That is, the algorithm $g(x)$ is **numerically stable** if it gives nearly the right answer to nearly the right question. 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 have seen (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 numerical stabilty of the algorihtm to 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 properly redefing the function as in the example above with the likelihood. More examples follow  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The tangent function is poorly conditioned\n",
    "\n",
    "import math\n",
    "x1 = 1.57078\n",
    "x2 = 1.57079\n",
    "t1 = math.tan(x1)\n",
    "t2 = math.tan(x2)\n",
    "\n",
    "print ('t1 =', t1)\n",
    "print ('t2 =', t2)\n",
    "print ('% change in x =', 100.0*(x2-x1)/x1)\n",
    "print ('% change in tan(x) =', (100.0*(t2-t1)/t1))"
   ]
  },
  {
   "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",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "% matplotlib inline\n",
    "\n",
    "def f(x):\n",
    "    return (1 - np.cos(x))/(x*x)\n",
    "\n",
    "x = np.linspace(-4e-8, 4e-8, 100)\n",
    "plt.plot(x,f(x));\n",
    "plt.axvline(1.1e-8, color='red')\n",
    "plt.xlim([-4e-8, 4e-8]);\n"
   ]
  },
  {
   "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))) # exact answer is 6.05e-17\n",
    "print ('%2f' % ((1 - np.cos(1.1e-8))/(1.1e-8*1.1e-8)))"
   ]
  },
  {
   "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-8, 4e-8, 100)\n",
    "plt.plot(x,f1(x));\n",
    "plt.axvline(1.1e-8, color='red')\n",
    "plt.xlim([-4e-8, 4e-8]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stable and unstable version of the variance:\n",
    "\n",
    "$s^2 = \\frac{1}{n-1} \\sum (x-\\bar{x})^2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sum of squares method (vectorized version)\n",
    "# watch out! big number minus big number!\n",
    "def sum_of_squers_var(x):\n",
    "    n = len(x)\n",
    "    return (1.0/(n*(n-1))*(n*np.sum(x**2) - (np.sum(x))**2))\n",
    "\n",
    "# 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",
    "\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 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# check the performances with an array \n",
    "# of randomly distributed data around 1e12\n",
    "\n",
    "x_ = np.random.uniform(0,1,int(1e3))\n",
    "x = 1e12 + x_\n",
    "\n",
    "# correct answer\n",
    "print (np.var(x_))\n",
    "\n",
    "print (sum_of_squers_var(x))\n",
    "print (direct_var(x))\n",
    "print (welford_var(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}