Optimisation_ Mathematical Optimisation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "y3WUp6uTTZe8"
   },
   "source": [
    "# Mathematical Optimisations\n",
    "\n",
    "Reducing the number of calculations in a piece of code will typically reduce the runtime. Many codes spend a significant portion of their time performing maths and replacing long-winded calculations with shorter calculations which are algebraically identical can reduce the runtime significantly. For instance, consider the three examples below:\n",
    "\n",
    "### Example 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jfsEy8XmTfWb"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def function1(value):\n",
    "  thousand_times=0\n",
    "\n",
    "  for i in range(1000):\n",
    "    thousand_times = thousand_times + value\n",
    "\n",
    "  return thousand_times\n",
    "\n",
    "%lprun -f function1 print(function1(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Iq-F9_jGL9Pm"
   },
   "source": [
    "We can replace the sum with a multiplication:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ovktLN-ILR7l"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def function1(value):\n",
    "  return 1000 * value\n",
    "\n",
    "%lprun -f function1 print(function1(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "p2A6G80hMUnZ"
   },
   "source": [
    "### Example 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "JR4K3vS9KnOE"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def function2(r, n):\n",
    "  geometric_sum=0\n",
    "\n",
    "  for i in range(0, n):\n",
    "    geometric_sum = geometric_sum + r ** i\n",
    "\n",
    "  return geometric_sum\n",
    "\n",
    "%lprun -f function2 print(function2(0.99, 1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0KrDKZ7UM140"
   },
   "source": [
    "We can use the geometric sum equation:\n",
    "\n",
    "$\\sum\\limits_{i=0}^{n-1}r^{i} = \\frac{1-r^{n}}{1-r}$\n",
    "\n",
    "to simplify the sum into a single expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ijcyQKuFKnuf"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def function2(r, n):\n",
    "  return (1 - r ** n) / (1 - r)\n",
    "\n",
    "%lprun -f function2 print(function2(0.99, 1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "TwUmGMisPnOe"
   },
   "source": [
    "### Example 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "nq4CRHE5TgTT"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def function3(n):\n",
    "  trig_sum = 0\n",
    "\n",
    "  for i in range(n):\n",
    "    trig_sum = trig_sum + math.sqrt(1 - math.cos(i/n) ** 2)\n",
    "\n",
    "  return trig_sum\n",
    "\n",
    "%lprun -f function3 print(function3(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kOtpu0pXS7P6"
   },
   "source": [
    "We can use the trigonometric identity:\n",
    "\n",
    "$\\sin(x) = \\sqrt{1-\\cos^{2}(x)}$\n",
    "\n",
    "This reduces the complexity of the expression evaluated in the loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "7eYZLJ9wQvSq"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def function3(n):\n",
    "  trig_sum = 0\n",
    "\n",
    "  for i in range(n):\n",
    "    trig_sum = trig_sum + math.sin(i / n)\n",
    "\n",
    "  return trig_sum\n",
    "\n",
    "%lprun -f function3 print(function3(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jFcNzQQpTimK"
   },
   "source": [
    "## Cost of Mathematical Functions\n",
    "\n",
    "A common way to optimise code is to find the least \"expensive\" (i.e. lowest running time) combination of mathematical operations which return the desired value. This may be through:\n",
    "\n",
    "- Using standard mathematical definitions to simplify the algebraic expression being evaluated\n",
    "- Rearranging the algebraic expression being solved for to reduce the number of more expensive operations being carried out\n",
    "\n",
    "Mathematical operations will be carried out on your computer by passing relevant data to the [Arithmetic Logic Unit](https://en.wikipedia.org/wiki/Arithmetic_logic_unit) (ALU) on your CPU (or GPU). ALUs typically contain circuits specifically designed to carry out fundamental operations (such as addition) and use combinations of these fundamental operations to perform more complex operations.\n",
    "\n",
    "Every mathematical operator and function will be executed by using one or more operations on your computer's ALU. These operations will take time to execute on your computer's and the number and complexity of operations required will affect the running time. Thus, some operations are more \"expensive\" to perform than others.\n",
    "\n",
    "In the example below we attempt to estimate the time it takes for various calculations to take place. This is made a little harder by the fact that every operation will involve a significant amount of time loading instruction and the value of the variable(s) into the ALU. To remove these overheads we first include line 8 which simply loads a variable. This will have the overhead of loading a variable and instruction (in this case to do nothing) into the ALU but not the cost of the operation itself. Thus, we can subtract the time spent executing line 8 from the time spent executing other lines to find the time cost of the operation on the other lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "1is_wk5YTmvq"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def mathematical_operators(a,b):\n",
    "  for i in range(1, 10000):\n",
    "    a\n",
    "  for i in range(1, 10000):\n",
    "    a == b\n",
    "  for i in range(1, 10000):\n",
    "    a < b\n",
    "  for i in range(1, 10000):\n",
    "    a + b\n",
    "  for i in range(1, 10000):\n",
    "    a - b\n",
    "  for i in range(1, 10000):\n",
    "    a * b\n",
    "  for i in range(1, 10000):\n",
    "    a / b\n",
    "  for i in range(1, 10000):\n",
    "    a ** b\n",
    "  for i in range(1, 10000):\n",
    "    math.log(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.log(a, b)\n",
    "  for i in range(1, 10000):\n",
    "    math.sqrt(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.exp(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.sin(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.acos(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.tan(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.atan(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.cosh(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.asinh(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.tanh(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.atanh(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.ceil(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.gamma(a)\n",
    "  for i in range(1, 10000):\n",
    "    math.factorial(4)\n",
    "  for i in range(1, 10000):\n",
    "    math.factorial(40)\n",
    "\n",
    "%lprun -f mathematical_operators mathematical_operators(0.96, 4.12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CYkb5pBfTtR7"
   },
   "source": [
    "The results as calculated when I executed this code in Colab are below:\n",
    "\n",
    "| Operation | Execution time (us per 10,000 operations) |\n",
    "| ----| ---|\n",
    "| == | 255 |\n",
    "| < | 436 |\n",
    "| + | 282 |\n",
    "| - | 383 |\n",
    "| * | 294 |\n",
    "| / | 412 |\n",
    "| ** | 1462 |\n",
    "| math.log(a) | 2022 |\n",
    "| math.log(a, b) | 2222 |\n",
    "| math.sqrt | 1173 |\n",
    "| math.exp | 3499 |\n",
    "| math.sin | 1658 |\n",
    "| math.acos | 1705 |\n",
    "| math.tan | 1761 |\n",
    "| math.atan | 1664 |\n",
    "| math.cosh | 1832 |\n",
    "| math.asinh | 2298 |\n",
    "| math.tanh | 2081 |\n",
    "| math.atanh | 2598 |\n",
    "| math.ceil | 2420 |\n",
    "| math.gamma | 3347 |\n",
    "| math.factorial(4) | 1224 |\n",
    "| math.factorial(40) | 5157 |\n",
    "\n",
    "This is a fairly crude approximation of execution time for different operators and functions, but serves to demonstrate that fundamental arithmetic operators are significantly cheaper than more complex ones.\n",
    "\n",
    "Note as well that when functions should have the same result, the more specialised function will normally have the shorter run-time. For example,  ```math.sqrt(a)``` will be faster than ```math.pow(a, 0.5)``` and ```math.log10(a)``` will be faster than ```math.log(a, 10)```. This is because these more specialised versions can employ shortcuts which their more generally applicable counterparts cannot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "pXC2LCvwT2Fy"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "def mathematical_operator_comparisons():\n",
    "  for i in range(1, 10000):\n",
    "    math.sqrt(3.5)\n",
    "\n",
    "  for i in range(1, 10000):\n",
    "    math.pow(3.5, 0.5)\n",
    "\n",
    "  for i in range(1, 10000):\n",
    "    math.log10(3.5)\n",
    "\n",
    "  for i in range(1, 10000):\n",
    "    math.log(3.5, 10)\n",
    "\n",
    "%lprun -f mathematical_operator_comparisons mathematical_operator_comparisons()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7o--NCP2T2-j"
   },
   "source": [
    "It's also worth remembering that, if there's a intrinsic version of a function available or a version from a package you can import, it is almost certainly faster than anything you could write. This is partially because most functions in modules such as the math module actually execute compiled code written in the \"C\" language which is much faster than Python and partially because the authors of Python's intrinsic functions and modules are very good programmers. As a result, if there is an intrinsic version of a function, it is almost always preferable to use it rather than write your own.\n",
    "\n",
    "In many cases, it is unavoidable to carry out expensive calculations, but it is often possible to reduce the number of expensive operations performed, even if it increases the number of more fundamental operations which are required.\n",
    "\n",
    "## Exercise\n",
    "Below there are number of sample functions. In each case, there are two copies (plus a sample solution in a hidden cell). Edit the second copy, using mathematical identities to simplify the code. Ensure both codes give the same answer to within five significant figures. How much faster does it run?\n",
    "\n",
    "### Function 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "1Oqz8VZnUAVL"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "# The original function\n",
    "def function1():\n",
    "  total_value=0\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    tanx= math.tan(i / 1e4)\n",
    "    cosx = math.cos(i / 1e4)\n",
    "    total_value = total_value + tanx * cosx\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function1 print(function1())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "e2knArQDUBJi"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "# Simplify this version\n",
    "def function1():\n",
    "  total_value=0\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    tanx= math.tan(i / 1e4)\n",
    "    cosx = math.cos(i / 1e4)\n",
    "    total_value = total_value + tanx * cosx\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function1 print(function1())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "colab": {},
    "colab_type": "code",
    "id": "_y0I1lZGUDAq"
   },
   "outputs": [],
   "source": [
    "#@title\n",
    "\n",
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#A sample optimisation\n",
    "def function1():\n",
    "  total_value=0\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    #Recall tan(x)*cos(x)=sin(x)\n",
    "    total_value = total_value + math.sin(i / 1e4)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function1 print(function1())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "W5_gVOyfUFpq"
   },
   "source": [
    "### Function 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Sdu9ysVVUKZL"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#The original function\n",
    "def function2():\n",
    "  total_value=0\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    total_value = total_value + math.log(1+ i / 1e5)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function2 print(function2())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "5VGcE47qUMXq"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#Simplify this version\n",
    "def function2():\n",
    "  total_value=0\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    total_value = total_value + math.log(1+ i / 1e5)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function2 print(function2())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "colab": {},
    "colab_type": "code",
    "id": "SbGsXrhCUN_6"
   },
   "outputs": [],
   "source": [
    "#@title\n",
    "\n",
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "# A sample optimisation\n",
    "def function2():\n",
    "  total_value=0\n",
    "\n",
    "  #Recall log(a)+log(b)=log(ab)\n",
    "  #Use an intermediate value to keep track of the product of all variables that were previously logged\n",
    "  x=1\n",
    "  for i in range(1, 10001):\n",
    "    x = x *(1 + i / 1e5)\n",
    "\n",
    "  #Now take the log of the intermediate value\n",
    "  #Note we've replaced 10000 log calculations with 1 log and 10000 additions\n",
    "  total_value = total_value + math.log(x)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function2 print(function2())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Stz_qqpZUQAq"
   },
   "source": [
    "### Function 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "1n15UDsaUUDS"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#The original\n",
    "def function3():\n",
    "  total_value=1\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    total_value = total_value * 2 ** (i / 1e7)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function3 print(function3())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "1mvM-syVUUvC"
   },
   "outputs": [],
   "source": [
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#For you to edit\n",
    "def function3():\n",
    "  total_value=1\n",
    "\n",
    "  for i in range(1, 10001):\n",
    "    total_value = total_value * 2 ** (i / 1e7)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function3 print(function3())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "colab": {},
    "colab_type": "code",
    "id": "u2ZfrJJ1UWYK"
   },
   "outputs": [],
   "source": [
    "#@title\n",
    "\n",
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#First optimised solution\n",
    "def function3():\n",
    "  total_value=1\n",
    "\n",
    "  # Recall 2^(a)*2^(b)=2^(a+b)\n",
    "  # This replaces most exponent operators with additions\n",
    "  x=0\n",
    "  for i in range(1, 10001):\n",
    "    x = x + i / 1e7\n",
    "    \n",
    "  total_value = total_value * 2 ** x\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function3 print(function3())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "colab": {},
    "colab_type": "code",
    "id": "FqHVa04VWAWo"
   },
   "outputs": [],
   "source": [
    "#@title\n",
    "\n",
    "%pip install line_profiler\n",
    "import math\n",
    "\n",
    "%load_ext line_profiler\n",
    "\n",
    "#Second optimised solution\n",
    "def function3():\n",
    "  total_value=1\n",
    "\n",
    "  # Note that x is an arithmetic sum, and so we can simplify using the arithmetic sum formula:\n",
    "  total_value = total_value * 2 ** ((1e-7 + 1e-3) * 0.5 * 1e4)\n",
    "\n",
    "  return total_value\n",
    "\n",
    "%lprun -f function3 print(function3())"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyMF8YMhfyEpk8ZAbQ5Any6n",
   "collapsed_sections": [],
   "name": "Optimisation_ Mathematical Optimisation.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3.9.13 64-bit (microsoft store)",
   "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.13"
  },
  "vscode": {
   "interpreter": {
    "hash": "5dbf766eb95023f9dddb799b5381b4ed6a9322e38632e8ac1570872c767b304b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}