Demos/Ch1_ExponentialSummation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Ch1_SymbolicTaylorSeries.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNCa2zYK58rTMh/W7DTVLWO",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/stephenbeckr/numerical-analysis-class/blob/master/Demos/Ch1_ExponentialSummation.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LNDLwuliDDql",
        "colab_type": "text"
      },
      "source": [
        "In [Ch1_SymbolicTaylorSeries](Ch1_SymbolicTaylorSeries.ipynb) we saw how to use the Taylor remainder theorem to estimate error in an expansion, and this is useful if you want to calculate a function like sine or cosine using only additions/subtractions and multiplications/division.\n",
        "\n",
        "Let's try that with the exponential function.  This is a classic example in numerical analysis"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zoGrsMYdCXq6",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Load the package\n",
        "import sympy as sym\n",
        "from sympy import init_printing\n",
        "init_printing()  # This will make output look very nice!\n",
        "\n",
        "import math  # has things like math.pi (which is the numerical value of pi)"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RJ3odjv1Dt6F",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 40
        },
        "outputId": "3c934cc3-b3a0-49dc-8185-c2b7ad35d725"
      },
      "source": [
        "# First, all symbolic variables must be declared. This is in contrast to Mathematica\n",
        "x = sym.Symbol('x')\n",
        "\n",
        "# Recall the Taylor series for exp(x)... very simple!\n",
        "sym.series( sym.exp(-x), x )"
      ],
      "execution_count": 94,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAawAAAAYCAYAAACm5Ml7AAAABHNCSVQICAgIfAhkiAAACkdJREFUeJztnX/QFVUZxz8vIoFo0A/TTAYViqgorZAwtAtaDRrlmP0inVZRqgHs1xShY95i4mWMhNIy7ddrP0wUJxor0mHgLTQzSAgakIx4KQUMA9QUEOz2x/fs3H0vu3t3z+7evS+dz8wO7909e85zn/Pc5znnOWcXcDgcDofD4QDmAKuBp4FdwD3AG0qVqPXMANYjHTwNPAhcUKpE7cEcoAbcVLYgfYAq0lXw2FmmQA5rXgnchvzhfmAj8I4kN/YrUCiHqADfBs4CJgGHgOXAS0uUqdU8BswG3gy8FVgBLAXeWKZQJfM2YDoK5I5kbEbOzj/GlCuOw4KhwANABxq0jgZmAf8qUyhHNMcCLwBTyhakZHYDHy9biJIYAmwBJgLduBlWEqrAX8oW4v+Y21BQGZyxnnkoYMXxFjSDvqLxQuMM62LgRmAVSt3UgJ9kFNDRm+OQ3vdEXD8BBbQbgZehTvs58DdgH/AUcD8wjb45Qz4K+DAK3L+PKRfUQyPnIp3sBA4A24F7gfNzlbQ4bgWWACsTlC3CHi6hnlY7zCm0Maehvt4K3GE+RxFmP2n9m62+TwZ+YGQ9APQAi4CXxLTVSvqhbM+rAucGE531GQtcCswHns3Y9oXAQ8BiFADXATPRjMvnTygDMxf5iUjWoU58BtiEC1hFcCewFjnuMKYjvU8EPmH+3g78FOhEP4S95vwSend0OzMG+A9Kie6l+RpWUA9Brjfn/4kc/zzgu8DD5lq7cyX6QR5tPncTP8PK2x6GmfLP0LcC1mTggyiNfB7S204UVMIIs5+0/s1G3yOAJ8z1pcjJrzCfH4mRt1WciQLu5cgGpwBrqA9g1nH4Gvt96DsPyqH9/eboBM4ALkN+YWaInDXg6rjKJgKvRp1Q4cgNWB76bpUWt3sDMv64keEy4EkU0CYhg2ocyZ0I/AN9h/fnL2YhDABGoul+J/qOcZtPgnrwuRJ95y5TXyNHh5xrhkfrbGEUWmgeFTjXTXzAytMeOtD66Rbga/StgNXIsWiE/tmI62H2k9a/2ej7XnN+VsP5G8z578S0F4dHdju9GAWe8ebzNcCP0YzwJBSAa8CjQH9T5jXAf9HgMA+e5/DMyjw0gGhkE7CNhJmDCu0RsO4j3DA6kOOqoVFMGjzsO99WnoXADuC1MXW/GKUQfphAjqtNW2Eps1aQtV+WA9+PuBamhxchB7WN8GBli0c2R5BGD35bhwJHDTmEQ+g7BsnbHj5l2jqH+q67sgJWHr/rlcDNIeeT6K1CNv8Wpu8R5txWDneyx6GZxLPYrQN5ZLPTt6Ng8QXzeTxKVfYPlDkG+agacJE5N998Pjei3rT9uA34XkPZSwlPNV5n7n93RNu9qNAeAetNKBe9kd6jpa8j+W6xqNPDvvNt5PkGSl+MblL3VFPHexPI8XlTdmGCskWQtV9WEG1bYXp4D/Xv2x+lFGcjJzy+sYIUeGRzBGn0MBTNKoPHauB283djeilPexiN1mD861XKDVhZ7Wcgcq5fCrmWRG8Vsvm3MH1fQbzs/uwryvnH4WFvpwPQGtzj1Ad7C4ENKPX20UDZpaad68znNWgwFRVk0/bj7WgNMchcc38j55k6FkS03YsK7RGwoB6pPfPZH90sxm7jgUc2J5VGnm+hBd5JKJXgH2GLiXehUdjAJu33R8aWePRREF0k08N84GzgFLSW1YlG+pMj6g3Tw5dN3Z3Uv3vw+C1wvMV38MieaunC3j67iU4J5mUP/ZHj2Ux9HaJK+SnBLpLrbQF6VudUYBzwS/S7Gh5SbxK9VbD3b1H69tOsn4u47yZz/ZMWbXrY2+ll5t65gXP+WnANrc/53Ek9YA1GwWpDk/q7SN6PY4GDKB05EvgA2sgyI6TeIaaePzZpH2ivgDUMjQ63osW5GvAb7FNDHtmcVBp5Gh2rf1Qbyg1Ei8F3JWh/ganjV+lFz5WkeuhCqYADKK23nOhAG6WHm6mn09YDE1DQH0N95Npt8R08sgesLPbZTXjAytMevoJGwcGZaJXyA1Yavd2B1n+fRzOFu4HXhZRLqrcK9v4tSt+3Eq/Tr5rrcyza9LC309+Ze8cFzp1GfY0o+DzkSlP2ErR+VUNpvzjS2v8FwJ/R5ou/AlcRvVloHwkfEK+QvkN7iHbQYUeaujsD9z2A8q1FyNRVsDxRTDF1TW1S7ipTbhPJHz7uof36JYooPdxizu9HM7Ugx6BdgzXi04M9FGML0L72MA4F+cYdlFWSB6we+r79NFLBLmDF6TuvgNVDfnY6GAX5F2i+y68Dbco4iHYzjqc+U2pG3v3o8ziyX6D3glsebEEOJSnbU5TdFfh7GvBcwvsWobWDIKcD70MPw/U0XFtXsDxRXIQMK27WNBOth21EefDdCetux36JIkoPe82/azm8z55Ds6xpKCf/YETdRdkCtKc99Ad+hEax12aQ5Uiwnzxopu+nzL9DIu73z++NuO6Tp50OR7tnd6PZShyTjIyLgX8HyjdLSUP+/egziOZyA+2VEpyK1jz8HSxhO4PS4JEtDZS3PEehLbjLYsp82rS1AXhFxvbyopV6uNy0EaUjf/3giynb9MieEmxXexhK8lH6oowy21CG3nwqpPNvSfTdjpsuzjL3JRnc/hql7UeYzyeZe+9vcl/e/ejTz9S7JUnhCu0RsM5HI6b1aFH9ETRlHRV3UxM87J1UEfJMNPJMj7g+21xfC7w8Qzt50mo9DEfGG/VcxjJz74dStumRLWC1sz0MQluIw46HTR2rzOe0estKGXoLUiG5f0uq73bc1u6vQ9WInvmBdgrW0LOOPh1ozXlX6B2iiH70GW1kujtJ4QrlB6wJaGr5d/SyS9DDbzW0/dIWD7vOL0qeb6Ic8wkh16419a+hfV6YW4YeAH5h2vhMw/l3oWC2h/gfZRge9gGrL9tDleRrWHlTlv0EqZDMv6XVdzs+OPyoubfxbRI+k1Ha7ZqQa/7DxCNDrhXVjz7+7sYoubkQLeB1oV0eNTQd888l2g+fE6ejXO8O6lNUn9VGtrMt6/ZI3/lFydOBnpoPm3Z/zNR7CD03UQ05PIs2s1CGHnxOpv6GgeUoDbgE6ecgdm/98LBzBH3dHqqUE7DKtJ+0/s1G342vZuqk/mqmzdi/msnDPmBVUEDaDbwzcP5E9LzUYyjQhPER027jtvMi/bPPz5Duh0UVqBKf5+7JKEBSRqKtjHsI/y8o/AfK/mBZv0e6zi9SnrHm3rBXzFRpvvbQbdGmLWXpIcjx6O0C21Aq4kn0ctIzLdoEO0dwJNiDX1crA1bZ9lMlnX9rVj5K38PQWzZ2IBvdRvaX33pkS12/Hj20+wRKWa5Cs8EZxL9gdoC556HAuaL9MyhTso98ZmqOHJmHOvfUsgUpGacH4fRgh9Nbcfj/0egZLWxzlmlzQgvbdCRgE+m2Tx+pOD0Ipwc7nN6KYyCaJd7TovYGoUcjlrSoPYfD4XAcQZxD/XVNRTMapWNPaUFbDofD4XA4HA6Hw+FwOBwOh6N9+R80GpRUSMNA0wAAAABJRU5ErkJggg==\n",
            "text/latex": "$$1 - x + \\frac{x^{2}}{2} - \\frac{x^{3}}{6} + \\frac{x^{4}}{24} - \\frac{x^{5}}{120} + \\mathcal{O}\\left(x^{6}\\right)$$",
            "text/plain": [
              "         2    3    4     5        \n",
              "        x    x    x     x     ⎛ 6⎞\n",
              "1 - x + ── - ── + ── - ─── + O⎝x ⎠\n",
              "        2    6    24   120        "
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 94
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wuQIA1W-so8V",
        "colab_type": "text"
      },
      "source": [
        "Let's try to find $e^{-30}$ with about 14 digits of precision.  Recally that Taylor's remainder theorem says that the error in the Taylor series (with $n-1$ terms) is the $n$th term but evaluate the derivative at some $\\xi \\in [x_0,x]$.  We'll expand around $0$, so $x_0=0$ (we do this because we *know* that $e^0=1$; we could choose a different $x_0$ to expand about if we knew what $e^{x_0}$ is).\n",
        "\n",
        "For this remainder term, the $n$th derivative of $e^{-x}$ is $(-1)^ne^{-x}$, and since our target $x=30$ is positive, we know $\\xi \\ge 0$ and hence $e^{-\\xi} \\le 1$, so we can bound this derivative term by $1$ (in absolute value).  We also need to include the coefficient $1/n!$ and the polynomial term $(x-x_0)^n$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i-2mgqeZsyR3",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 272
        },
        "outputId": "ef89ecad-f275-405c-bdd5-c505080e0e63"
      },
      "source": [
        "X   = -30\n",
        "\n",
        "# Taylor's remainder theorem says that the remainder term at the (n-1) step is the nth Taylor series term but evaluated at some \\xi\n",
        "Rem = lambda n : abs( X**n / math.factorial(n) )\n",
        "for n in range(15):\n",
        "  print( Rem(n) )\n",
        "  # When n is large enough, eventually this sequence will start to decrease"
      ],
      "execution_count": 79,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1.0\n",
            "30.0\n",
            "450.0\n",
            "4500.0\n",
            "33750.0\n",
            "202500.0\n",
            "1012500.0\n",
            "4339285.714285715\n",
            "16272321.42857143\n",
            "54241071.428571425\n",
            "162723214.2857143\n",
            "443790584.41558444\n",
            "1109476461.038961\n",
            "2560330294.7052946\n",
            "5486422060.082774\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IZDdLHB2580s",
        "colab_type": "text"
      },
      "source": [
        "So if we want 14 digits, let's calculate a bound on the number of Taylor series we need:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "46WrYmBXtlHZ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "9a6247a5-702d-4693-f462-cf3e53187601"
      },
      "source": [
        "tol = 1.0e-14\n",
        "n = 0\n",
        "while Rem(n) > tol and n < 1e8 : # this last check is to prevent infinite loops, which are a possibility due to bugs\n",
        "  n += 1\n",
        "N = n-1\n",
        "print( \"We need at least\", N, \"terms, since Rem(n+1) is %.2e\" % Rem(N+1) )"
      ],
      "execution_count": 80,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "We need at least 106 terms, since Rem(n+1) is 9.19e-15\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iUv1tXQp6DI1",
        "colab_type": "text"
      },
      "source": [
        "Now, let's sum the Taylor series. We should have an error of 1e-14, right?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m9bs9oT5vSU0",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 357
        },
        "outputId": "2353cac6-088e-4615-d66b-085f10037a19"
      },
      "source": [
        "e = 0.\n",
        "for n in range(N+1):\n",
        "  e += X**n / math.factorial(n)\n",
        "  if ( not (n % 10 ) ) or ( n > N-10 ):  # save some output...\n",
        "    print(\"Iteration %3d\"% n, \" estimate is %29.15f\"% e, \"and error is %9.3e\" % abs(e - math.exp(X)) )"
      ],
      "execution_count": 90,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Iteration   0  estimate is             1.000000000000000 and error is 1.000e+00\n",
            "Iteration  10  estimate is     121254849.571428596973419 and error is 1.213e+08\n",
            "Iteration  20  estimate is   85291712210.032180786132812 and error is 8.529e+10\n",
            "Iteration  30  estimate is  384842612535.907775878906250 and error is 3.848e+11\n",
            "Iteration  40  estimate is   63336540117.266479492187500 and error is 6.334e+10\n",
            "Iteration  50  estimate is     878229229.277898311614990 and error is 8.782e+08\n",
            "Iteration  60  estimate is       1685584.300283375196159 and error is 1.686e+06\n",
            "Iteration  70  estimate is           622.524572911353516 and error is 6.225e+02\n",
            "Iteration  80  estimate is             0.055867710574729 and error is 5.587e-02\n",
            "Iteration  90  estimate is            -0.000084070677839 and error is 8.407e-05\n",
            "Iteration  97  estimate is            -0.000085530630269 and error is 8.553e-05\n",
            "Iteration  98  estimate is            -0.000085530022814 and error is 8.553e-05\n",
            "Iteration  99  estimate is            -0.000085530206891 and error is 8.553e-05\n",
            "Iteration 100  estimate is            -0.000085530151668 and error is 8.553e-05\n",
            "Iteration 101  estimate is            -0.000085530168071 and error is 8.553e-05\n",
            "Iteration 102  estimate is            -0.000085530163247 and error is 8.553e-05\n",
            "Iteration 103  estimate is            -0.000085530164652 and error is 8.553e-05\n",
            "Iteration 104  estimate is            -0.000085530164246 and error is 8.553e-05\n",
            "Iteration 105  estimate is            -0.000085530164362 and error is 8.553e-05\n",
            "Iteration 106  estimate is            -0.000085530164330 and error is 8.553e-05\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_9_TYrmy6IRI",
        "colab_type": "text"
      },
      "source": [
        "... but our error is in fact much worse. What went wrong?  Our estimate of the error was due to our mathematical approximation of the exponential, but we didn't include numerical error due to the summation.  We are adding and subtracting a lot of numbers of similar sizes, so we loose precision."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sLrv54ATy0IW",
        "colab_type": "text"
      },
      "source": [
        "Attempted fix #1: use better summation strategies.  Unfortunately, we'll see that this doesn't quite fix it for us.\n",
        "- Fix 1a: use Python's builtin `fsum`\n",
        "- Fix 1b: use [Kahan summation](https://en.wikipedia.org/wiki/Kahan_summation_algorithm), which is a trick that effectively let's us work with twice as many digits, or use another good summing algorithm. \n",
        "\n",
        "---\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fVEh4BM61LXD",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 38
        },
        "outputId": "e172bf0b-743f-4957-b43c-801f62600a9b"
      },
      "source": [
        "# Fix 1a.\n",
        "# See https://www.math.ubc.ca/~pwalls/math-python/python/sequences/\n",
        "series = [ X**n / math.factorial(n) for n in range(N+1) ]  # \"lazy\", or \"iterable\". This is a list comprehension\n",
        "e = math.fsum( series )\n",
        "abs( e - math.exp(X) )"
      ],
      "execution_count": 85,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQ8AAAASCAYAAABFEFvPAAAABHNCSVQICAgIfAhkiAAAB/RJREFUeJztm3uw1VMUxz90rxJ5p8Y7xXSbDDK6Go/OFRnFTGQwGAZlKM9RJGO6zCRhUvIqeUwTZrgq4xFS9ECm6KHUFXWuyJUbEXJvt64/1trO7+7z+/3Ob+9zbjJzvjO/+c3Za6291tp7/9bee+19oIgiiiiigOgDzABqgXpgI/Ae0M+hjv7A+8D3wDZgHfAa0Cuh/FVAkz6DInjGAnOADarjF2ApMAo42OI9WOuZAXyj/L8BC4HrgT0jdOwBDAY+A/4A/gSWADfGyLj64SOTDvDYT22BfHDpQ9/2ddXjw+/j/yXARGAB8DvSrtNifNhdcQTwPPIN1yPjZjxwYAR/muTjKgsPK+MGYDLwIPAs8IXSkmCs1lEHTAEeAqqABmAn8nHE4UhgC7CV+A+oAViENM5DSGcvVpkftB6DG7V8I/ASMEbltmh5FTLIbLyk9J+QdpgAfKVlUwvkh49MWvkqQ55hBfDBtQ9929dVj8/Y8vF/mdK3Aqv5fwaPzojPTcBMpK3m6u81ZE+w4DaummGwVvwisFcIvTSBwR2BHUiUOtSiVWj962Lk9wA+AL4FHiH+A2oTUT5a5Z4KlJ0NXEj2TNMR+E75B1q0iwL2HhIo3wt4U2kXF8APH5m0Prng44NPH/q0r6seH7t8+7ACOA7pkxT/z+DxHmL3LVb5OC1/JkQmTbJx1QytgU1ADeGBIynK1bA3Iui/I9E8CrchM8hZSLRzWe4bnKhysxPyj1T+iVb5VC0fGiJzktLmRtTp44eLTJpknezjQ759aCOqfV31+NiVTx8apEgePAYCs5CVUQOwFvG/VQLZQqIzYvN6sgN6OzLbt30sWpqEwSNY6blAe2A6MoD7A3cjAzppngKksRqAnjSP9CAfRTtkdg1DGbK0mgDMd9Bp40J9r0jIv13fjVZ5R32HrZRM2ZlkB1sfP3xkWiPL9JFIP1WQPUh9fMinD8MQ1b6uenzs8u1DV7QCXkG2UF2QHMxTyLc0GtnC7UpU6Pt9tSGIrcDHQFvgtBDZJOOqGe5HItUY4EuykyXzkOCSBLerwZuQvMkY4FXgb3XGXnIClCBJrGpgby2rJNmMPUx5H0MSXE3A8oT2lpDx9zyL9rKWDwmRM7NWE9A1Tz98ZNJk95FZnvfO0wfw68MwxLWvjx5Xfl//g0iRe+XxBJnvpyRQXop8qE1Atxj5QsNse++MoBt7b7LK0yQbV83wtDI1IjP2GcC+wAlk9k4fORg/ADn9CBqwFrgigv8BZD8bXOVUkix41Fp6ZgEdEtr5qMq8HUK7UmnfAAcFykuRpbPRF7TZxw8fmVFInqEDMoN0R/awO4G/kK2brw8Grn0Yhrj29dXjwp+P/wYp4oNHOdLuMyPoN6j8tTE6Co3JxI8fkxe8xypPOq6aYZJW9jdwjEVri5y+5Gpkg7uQIDQOOFble5AJQvapTbny2+WVuOU8OiAJsmok698jB/+tWv9qmg8sg1bAu8pTi7TRBGAVMnhrlFaehx+F8t3AfKwzPH0wcO3DMORqXx89rvy+/geRIj54TFP6y4SfUlQp/foYHRB/TBr2xK2EfINHFOxx1QzmCOzTCOEpSr8th5KU8k0PobVFzuZ3IB0PssSrRo7OWlv8lfh9QEcjZ9orY3hu1rpXkdkXh6EUyf18iQTWLcgM01XrbwI64edHS/jeReU2e/hgkMKtD8OQpH1d9fja5ep/lJ1RH+smkn3s58ToALmztMbhiQvgvtuWKISNq39xHZklf5wxI3IoMRHKPh4ymK50c2x3AMkj7fgcuoNYqjJ2Yg1k39yEDKake3cbbZAA9bP+9vGjJXzfn8wK0tUHA9c+tJG0fV315GuXjSj/baSIDh5tlDYvoc5dhUGIXZMi6Gal1idhfVnjKpjYmaPEbsgpjJ2h7a7v9TmUmBk0Kllpyhv0XQ88F8HbAzgZuaVYTfSqKAyH6XuHVX43cqqxDDlhqnOoM4jLkQz9K/rbx4+W8N1kz+Pu0hjYPhi49mEQLu3rqicfu8IQ5b8LzMW3sEnqv8SH+u5L9vfcDjgdyWEsSlhfznFlEkh3WOV9VfmvSAQy6Iws/YKXxy4ls7883KrnfK1nG+G322xUEr10P96yxWBPMvu5jy3afVq+hOg9uI39QspOQmarX8gEqThU4r4FiZMpI/t8HiRXtVblRgbKXX3w7UPX9nXV42tXvn2YIn7bslzpURcGz2DX3/MA90tiTuOqxGIaisx245B7HkuRveAAZAYfhPxfwWAOkl/oROZiSRVy1n4Okigz/5EpAy5AIvUIIvZODuiHHIstRFZDm5GEaW9kz1uL3Jg1uIbMqcYCJJlnI43crg1iNjIgVyLn42VI22xD7pNszNMPH1yG7GXnIwm/rUgg748so99BlvgGrj749KFP+7rq8R1bPn04QB/I5Gx6BeyvI3NdezhymvS62rcCmcQOB05BJtejQnS0NIYAnwCPI9uT1UhiuAL4GrjX4ncdV1loj9wErEGWf3VIJ/UM4U0j0egYq7wU2fcuQm79NSJJpbeQVUxSVBI9+3ZHkj7L1MZGJLAtVjl75jN1xT0fhegZDnyOJNnqkWXbk8gfjgrhh49Mb2SpvUbt2o7MorOBq8n+D4mPD659aOx1bV9XPT5jy8f/XP6kLf5TkeBWi/RHHZLzmUTyvEJL4EjgBeBH5HuuIfqPca7jqogiiiiiiCKKKKKIIoooYnfGPwfcHcMofdxfAAAAAElFTkSuQmCC\n",
            "text/latex": "$$6.843294459828891e-05$$",
            "text/plain": [
              "6.843294459828891e-05"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 85
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tEAP7T1swwd_",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "f7841ab1-8717-4dd9-eb14-fd3e698a1e17"
      },
      "source": [
        "# Kahan Summation, though doesn't work (Python might be optimizing?)\n",
        "e = 0.\n",
        "accum = 0.\n",
        "for n in range(N+1):\n",
        "  a = X**n / math.factorial(n) - accum\n",
        "  b = e + a\n",
        "  accum = (b-e) -a\n",
        "  e = b\n",
        "  if n > N-4:\n",
        "    print(\"Iteration %2d\"% n, \" estimate is %21.15f\"% e, \"and error is %9.3e\" % abs(e - math.exp(X)) )"
      ],
      "execution_count": 91,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Iteration 103  estimate is    -0.000085530164652 and error is 8.553e-05\n",
            "Iteration 104  estimate is    -0.000085530164246 and error is 8.553e-05\n",
            "Iteration 105  estimate is    -0.000085530164362 and error is 8.553e-05\n",
            "Iteration 106  estimate is    -0.000085530164330 and error is 8.553e-05\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oyti5Jrf18Tt",
        "colab_type": "text"
      },
      "source": [
        "Attempted fix #2: use some math.\n",
        "- Fix 2a: split into positive and negative terms, add those separately, then combine at the end. Good idea, but again, doesn't quite fix it.\n",
        "- Fix 2b: rewrite $e^{-x} = \\frac{1}{e^x} = \\frac{1}{1+x+x^2/2+\\ldots}$.  Finally, we have a good solution!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YCJ1vHKPzo8u",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 37
        },
        "outputId": "7fbaeb34-43fe-47d0-fac2-cd3f7a7f73f2"
      },
      "source": [
        "# Fix 2a\n",
        "seriesEven = [ X**n / math.factorial(n) for n in range(0,N+1,2) ] \n",
        "seriesOdd = [ X**n / math.factorial(n) for n in range(1,N+1,2) ] \n",
        "e = math.fsum( seriesEven ) + math.fsum( seriesOdd )\n",
        "abs( e - math.exp(X) )"
      ],
      "execution_count": 92,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQQAAAASCAYAAAC98KA4AAAABHNCSVQICAgIfAhkiAAABrNJREFUeJzt22usXUUVB/AfWKSIWnwAN4bG0sZqI0ijiPgoBBpqIo8APmMEahRD4oMKFIyJsXwwgjH4fjTxFQzRhKBBAtY3IEiIaI2SysPQc6EBKtdCA/JsvX5Ys3P33Xfvfc7eZ/fcRs8/OZl7Z9aatfb815k9s2YOY4wxxhg1OAzfw4N4Bj18GS8ZQV9tbDfV2Qfn4nY8gX/jDpyHfQuyazHd57O7xrfV+CkeTr49iF/gHSWyvRobD9fYGNTOy/DhJPcPPIWduAUfMvfZh/VrFFzuSe4zXI7f4AExZjuwGZ8VY1pEz+DjtbZGtl98DRpbjXjfp6C8DH/AIbgWd+EYnIC78Vb8q8LBIpr21cZ2G52r8H78Ez/DkzgJK/BDnJ2TXYnTK55vFU7E9TilpP0LWI9t+DmmcDDegF/j4oJ8DweJgC7iCXyxwo9B7ZyHb+Eh/A7341CciUW4Bu8WQTisX6Pgck9zn+FZ/Blbkt6BOBZHiy/hsWKyyNAz+Hi1ja8msdWWd8QMM42PF+qvSPXfrnC+i77a2G6qc0aqvw8vz9U/H9eltjNLn2Yubkvyp5W0nZvafpD6LmK/krpe+jRBEzsn4lRz34QTIkim8c6O/BoFl6PifmFJHXwu6XyzUN/TfLzKUBVfTWOrLe+WpcatJcovMrPEOrD6GVr31cZ2G50rk85HS3xemdp+W/tkgSOT7DY8r9C2v3iTTConrAo9zQKprZ0yfFo8z9c68GsUXM4n9xmOSjq/KtT3DD8hVMVXl5xTwnt+ME9I5S/xn4Li47gVLxBLpH5o2lcb2210JlJ5X4nPWd0q/Qf7I6n8rrl7vJPE8u0nya+TcQnOx5v79Ls/PiCIOl88Y3HC6cJOEc+lclcHfo2Cy/nkPsOpqfxrSVuT8SpDVXx1yTklvC/INb46lfdUKN+LNVgukix1aNpXG9ttdKZSeXiJ/NJULkh/31XR7wGC7N34Tkn7G1P5tEg+HVFovxnvwiMluhNiL5vHVnwQN3VoJ48FZvbOmypkmvg1Ci7ng/uL8EKx7z4abxOTwWUlsk3Gq4i6+OqKcyp4z68QFqVyZ0UHWf1BAxhr2lcb2210rk/lBXhprn4/XJr7vy4T/p7U5yazk0kZDknlerEcWyWWsa8Tb7TjcHWJ3vdF5nhCLHWPxEYsEYmjozqyU8RlIrBuEPvyYf0aBZfzwf1F4mRhnZgMNolJp/jlazpeRdTFV1ecU8F71VHL/yp+LB5+mcgab8RX8BcxuPcnueIyNI9sObexoj0b010iIXSL2NP+TSS2tuF4c5d4l4o97HaR/b5TZIivEG+NDR3ZyeMTuFC8Ec+qkGnq196KYbmfEKdyEyL5uFS8pV9fkBt2vOriqwvOqeE9PyFks+oi5cjqH+tjrE1fbWy30dkt9n6fEjP7OelzL94i9p9E4qYMr01y28TMWobM3mZzk0tPmpmNj6nQLyLLlh/XsZ2PiS/EFrHH3TGgP/38GgWX88F9hu3iTH+NOOO/so98hqrxyqNffHURW7W853MId6dyeUVHr0pl1b4tj6Z9tbHd1t/nxGWTywv1C5POlNjvlaEumVj0q2rifDSVB1S0F5EtSYunO8PYWYcvibfXav2/BG382pNczgf3RUyKL9VKcYw5VS9eOV559IuvYWOrEe//D8eOdVib+vtqRftCMZvuwuKafl4plp2TJX4R+8hpvHdAv96e5Ld0ZOeSVL/Z7PP4pqjya289dqzDWvXcV2F70hvkFm/VeGUYJL6Gia1WvDe97LEMr1F+0WZvvJgELy6pWylm8B14RUk7sdeaFpdY+uHaJPvJQv0aQeijZi93VygP3iViSTstjrCGtfOZJH+H2Ym1KrT1a2+8mERz7pcr35bsa+Zi0q25+rbjxeDx1ZRzGvDe7+ry3/Emsde4R+xv8tdBe2LWOtzcPU3TvprKt9W5XdznvlPsG1eI89ynxB6z6ljo9yK7fJr+pB2W/Fosjr02izE6XRDzPnFlNMMGkeS5Wcz+j6dnO1m8OW4QSaNnh7BzjrjdtltcRCnL0PeSzLB+jYLLUXC/Dp8Xybutqb9DReJuqfgdwWozb/2248Xg8dU0ttrwPguLxdHJQ8nxSdU/GOklJ5Z00Fcb+TY66/EnsQ97RlxK+YYY6CqsEM/5gMEvmBwsCJhMfk2JZFRZwud4/EhkfR8Te91HxC24s82duNvY2aD/D2lu7NCvUXC5p7k/Al8XJxFTYjm/E38U41l827Ydr6bx1SS2NmjO+xhjjDHGGGOMMcYYY4wxRhn+C0DZwsUtSasRAAAAAElFTkSuQmCC\n",
            "text/latex": "$$0.0009765625000935762$$",
            "text/plain": [
              "0.0009765625000935762"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 92
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "veG534Ry2eZL",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 38
        },
        "outputId": "4ff8a409-f014-4a19-fc20-477314310390"
      },
      "source": [
        "# Fix 2b\n",
        "series = [ abs(X)**n / math.factorial(n) for n in range(N+1) ] \n",
        "e = 1./math.fsum( series )\n",
        "abs( e - math.exp(X) )"
      ],
      "execution_count": 93,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQ8AAAASCAYAAABFEFvPAAAABHNCSVQICAgIfAhkiAAAB9NJREFUeJzt22usXVURB/BfbQu1voiCbUQUBJUihIpKS8LjgKABLEHwQVREpRAiKjWCGBPD1cQoSBCCihBIjAIm8lIBUWp9AfGF8kaaYr2VBm9qKYpIHxSuH2Ztz2bffc7Ze5/d0g/nn5zsZM2aNWvWmlmPWXMYYYQRRmgB78HFuA1PYBJX1uB/BRbjBjyM9fg3bsfJeMEA/rcn3glsxKP4GY5qSU4d/T6S6P1+z7TAU8SHcnUXD6hbl+do3IrVYsxW4hoc0KP+uViGR1L9dbgL54g5KGJcb70nWpKRR1V7ob5tT8Mp+D2exH9xJ04z2I63FTTxk8p6Tysw3o19E9Nq7ImrhHFWwWm4BP/AL/F3zMFxeBmuw3vFxBVxHs5Kcm/BWuyEt+Dn+GwLcuroNx/H9tDzIByGm/GuIXny2AX3YTpeLCbx8h516/KcK8bwMfxQjO8eOAYz8GFTnWkT/owHsQYvwkK8VTjqQuH0GcaxAy4skf8kzi8prysjQx17ob5tX4UPpD79GE/hCMzD98R4beto4ieN9T4UrxeLSkf9k8dhWGTqijY3dXwSx5fwnZJo38F2JfSZLckZVr8Mv028x7TIM00Y/V/xNdVOHlV55ooTzwReWaAdmvhWlvDN6iH3y4nnW4Xy8fSrg7oyqG8v1Jv7d+uOyY658u1wY6Id14N3W0JdP2lN747mzlWGz6f2Li6Uby9WuVXKDaEtOUV0NNNvn8S3Wuz2bfGcgWdxMMZUWzyq8ixItB/1aOcJ/GeArDz2Te0tLZSPq7941JXRhr109J/77yb66SW0+Yn2iz7tH697GtqEFcIuq9rL1kCZn9TSe8aW7F0BT6fv5kL5EeK4eaFwhKOxNzbgD2LHbkNOWzg1fa8wOH5RlWcevoqL8BuxYwxCHZ4Vwoj3FzvK2hztYLxEXGWqYlH63ltC215cBV4j7sv3pv5VHatBMtq2lzLMTd+y01hWdpBYvDblaNPFgnSCiDFcI2IxR4qT1BtxUgv9awNlftJU7ynoaO/kMUPcyyfxzgLti6n8K7k6+d+vhbEMK6eIjvr6vRCPiwHfpSWeGSIgtTzVZfDJownPEuFsa3CZGO8fCKe71dTrTB5npva/LgKOk7jH1HkZVx4sXYlD+rRfR0Yb9tLRf+6vTvSPl9CyHXhSxE3y+Eaub/mNeSbuSLS9BvRta6CXnzTVewo62ls8zk9t3VxCuyTRNotd5kAR+NtHRM4n8asW5BTRUV+/kxLPTS3yfEnsyvkXjzH9F4ImPEQwd53nOtsKESDrh4kCzy0i8FbEOeIENAezxYng22LRekpcRYaV0Ya9dPSf+w8m+sN4ea58prj6ZX3Mj/8CoWevE9ypieejA/q2NdDLT5roXYqOdhaPT6V2/lLoUIZLE30Ddi3QZotIe5UOD5JTREd9/bLdY9GgihV5FggnOK9QPqZ//KIuD/H6sBkX4HVibPfTdbhie2WYI4Jqy8VLyH4VeOga6w0tyGjDXjr6z/10/FT3iflScT18QCy+qxJtQY7nylR2tZiL4u/aRD+5T7/G9X7qLvs18c1+ftJE71J0huhghk+kNh7QvU8VcW6q0+uuenminzGknCI66un3plT/EdUDX/14ZggHeVDECfIYU74QNOGhq+v1JbTZIpD7jFhUquC14i5/f8X6eyT5j1Ws309GG/bSMXjuZ+JscbzfgH+JU8WeqU+T2C1Xf41qDn94H5nL8FCNX5UFP48qflJX71J0DLd4LEn89+l/n/6Y7jG1DNkT5OeGlFNERz39Lkr1x2rI6Mezg+o7zIVD8NDd+T/Zo5/XJ3rZ83Yv3JV4dhxUUeQUZKeFOiiTMay9MJxtzxKL2j8LZZMi3rKtoqmfZJii95Z6bTlbvATcLaLja/vUXSaU2ku8Rz9boO+dvn8bUs4wmIUTxe58RUs8G/u0tR/eLDIBl+vusk146J5SegUSs/K+EfQCXpW+VV5RFqZvWRS/roxh7KUNnCBeG76fK8uSLasspM8H2vCTMr17omPw6ry7OM7kk3K+kPjuVC32QDcY8+lC+TuEcTwudq88msjJo6P67nNiqntjjfab8GQYMzj4WYfnfbr32J0LtCPFGK/33HTwN5g65oTDZglcd+TK54ns0CJ2FUHZSZFbkEddGRma2EseHYPn/qUlZfPFzrtOd2HLcE9qs1cS1YGenzyPun5SWe/iyeNY3fTq7E50gMjkI1asM3P1l4m76W4i2HOS7kvAbSI4U8R4rr0Mp4td8wLxbn9XavPY1NZikZOfoamcuvplyPI0Liuh9UITni2Fa0Um6uEiUJb9H2SeSJWfJo75+ZjEUeLJ8Xaxiz8mgpmHiNjIhMj0zPB+fEbkdKwSSWe7i/mchZ+Ymp5eV0aGuvZC/blfKhbU+5Mu85Ks9SL4/Wih/bPE68V1YqzvFYvgziJlfqbIfdmaaOIndfX+P8b0v0ePlwie1I16D+Kf1PsZbSeR7bZKHJ/XCiPfv0E/e8mpqx8xeHUDpU14yvrZ1smDMN4l+J3IKN0sgnw3iR27iL1F3sLdYi42C4f8Y5JV3MUOEUfah0SQ7WmxWy0V/4co/o+qiYw86tgL9ef+LPwp6bJRXLm+iVf36dPbxEI9IfRfK2IMl4o/8W1tjKnvJ030HmGEEUYYYYQRRhhhhBFG2BbxP4cOrMi82uOVAAAAAElFTkSuQmCC\n",
            "text/latex": "$$1.262177448353619e-29$$",
            "text/plain": [
              "1.262177448353619e-29"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 93
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fTHg9-fB2s_E",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}