forward.ipynb

{
 "cells": [
  {
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  Updating registry at `~/.julia/registries/General`\n",
      "  Updating git-repo `git@github.com:JuliaRegistries/General.git`\n",
      "\u001b[?25l\u001b[2K\u001b[?25h"
     ]
    }
   ],
   "cell_type": "code",
   "source": [
    "using Pkg; Pkg.activate(\".\"); Pkg.instantiate()"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Implementing Forward Mode\n",
    "=========================\n",
    "\n",
    "In the [intro notebook](./intro.ipynb) we covered forward-mode differentiation\n",
    "thoroughly, but we don't yet have a real implementation that can work on our\n",
    "programs. Implementing AD effectively and efficiently is a field of its own,\n",
    "and we'll need to learn a few more tricks to get off the ground."
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "code",
   "source": [
    "include(\"utils.jl\");"
   ],
   "metadata": {},
   "execution_count": 2
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Up to now, we have differentiated things by creating a new Wengert list which\n",
    "contains parts of the original expression."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Wengert List\ny1 = log(x)\ny2 = sin(y1)\ny3 = 5 * y2\ny4 = 1 / x\ny5 = cos(y1)\ny6 = y5 * y4\ny7 = 5 * y6\n"
     },
     "metadata": {},
     "execution_count": 3
    }
   ],
   "cell_type": "code",
   "source": [
    "y = Wengert(:(5sin(log(x))))\n",
    "derive(y, :x)"
   ],
   "metadata": {},
   "execution_count": 3
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "We're now going to explicitly split our lists into two pieces: the original\n",
    "expression, and a new one which only calculates derivatives (but might refer\n",
    "back to values from the first). For example:"
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Wengert List\ny1 = log(x)\ny2 = sin(y1)\ny3 = 5 * y2\n"
     },
     "metadata": {},
     "execution_count": 4
    }
   ],
   "cell_type": "code",
   "source": [
    "y = Wengert(:(5sin(log(x))))"
   ],
   "metadata": {},
   "execution_count": 4
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Wengert List\ndy1 = 1 / x\ndy2 = cos(y1)\ndy3 = dy2 * dy1\ndy4 = 5 * dy3\n"
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "cell_type": "code",
   "source": [
    "dy = derive(y, :x, out = Wengert(variable = :dy))"
   ],
   "metadata": {},
   "execution_count": 5
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": ":(5 * (cos(y1) * (1 / x)))"
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "cell_type": "code",
   "source": [
    "Expr(dy)"
   ],
   "metadata": {},
   "execution_count": 6
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "If we want to distinguish them, we can call `y` the *primal code* and `dy`\n",
    "the *tangent code*. Nothing fundamental has changed here, but it's useful\n",
    "to organise things this way.\n",
    "\n",
    "Almost all of the subtlety in differentiating programs comes from a\n",
    "mathematically trivial question: in what order do we evaluate the statements\n",
    "of the Wengert list? We have discussed the\n",
    "[forward/reverse](./backandforth.ipynb) distinction, but even once that choice\n",
    "is made, we have plenty of flexibility, and those choices can affect efficiency.\n",
    "\n",
    "For example, imagine if we straightforwardly evaluate `y` followed by `dy`. If\n",
    "we only cared about the final output of `y`, this would be no problem at all,\n",
    "but in general `dy` also needs to re-use variables like `y1` (or possibly any\n",
    "$y_i$). If our primal Wengert list has, say, a billion instructions, we end up\n",
    "having to store a billion intermediate $y_i$ before we run our tangent code.\n",
    "\n",
    "Alternatively, one can imagine running each instruction of the tangent code as\n",
    "early as possible; as soon as we run `y1 = log(x)`, for example, we know we\n",
    "can run `dy2 = cos(y1)` also. Then our final, combined program would look\n",
    "something like this:"
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "```julia\n",
    "y0 = x\n",
    "dy = 1\n",
    "y1 = log(y0)\n",
    "dy = dy/y0\n",
    "y2 = cos(y1)\n",
    "dy = dy*sin(y1)\n",
    "  ...\n",
    "```"
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Now we can throw out `y1` soon after creating it, and we no longer have to\n",
    "store those billion intermediate results.\n",
    "\n",
    "The ability to do this is a very general property of forward differentiation;\n",
    "once we run $a = f(b)$, we can then run $\\frac{da}{dx} = \\frac{da}{db}\n",
    "\\frac{db}{dx}$ using only `a` and `b`. It's really just a case of replacing\n",
    "basic instructions like `cos` with versions that calculate both the primal and\n",
    "tangent at once."
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Dual Numbers\n",
    "------------\n",
    "\n",
    "Finally, the trick that we've been building up to: making our programming\n",
    "language do this all for us! Almost all common languages – with the notable\n",
    "exception of C – provide good support for *operator overloading*, which allows\n",
    "us to do exactly this replacement.\n",
    "\n",
    "To start with, we'll make a container that holds both a $y$ and a\n",
    "$\\frac{dy}{dx}$, called a *dual number*."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Main.##365.Dual{Int64}(1, 2)"
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "cell_type": "code",
   "source": [
    "struct Dual{T<:Real} <: Real\n",
    "  x::T\n",
    "  ϵ::T\n",
    "end\n",
    "\n",
    "Dual(1, 2)"
   ],
   "metadata": {},
   "execution_count": 7
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Main.##365.Dual{Float64}(1.0, 2.0)"
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "cell_type": "code",
   "source": [
    "Dual(1.0,2.0)"
   ],
   "metadata": {},
   "execution_count": 8
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Let's print it nicely."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "1 + 2ϵ"
     },
     "metadata": {},
     "execution_count": 9
    }
   ],
   "cell_type": "code",
   "source": [
    "Base.show(io::IO, d::Dual) = print(io, d.x, \" + \", d.ϵ, \"ϵ\")\n",
    "\n",
    "Dual(1, 2)"
   ],
   "metadata": {},
   "execution_count": 9
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "And add some of our rules for differentiation. The rules have the same basic\n",
    "pattern-matching structure as the ones we originally applied to our Wengert\n",
    "list, just with different notation."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "6 + 14ϵ"
     },
     "metadata": {},
     "execution_count": 10
    }
   ],
   "cell_type": "code",
   "source": [
    "import Base: +, -, *, /\n",
    "a::Dual + b::Dual = Dual(a.x + b.x, a.ϵ + b.ϵ)\n",
    "a::Dual - b::Dual = Dual(a.x - b.x, a.ϵ - b.ϵ)\n",
    "a::Dual * b::Dual = Dual(a.x * b.x, b.x * a.ϵ + a.x * b.ϵ)\n",
    "a::Dual / b::Dual = Dual(a.x * b.x, b.x * a.ϵ - a.x * b.ϵ)\n",
    "\n",
    "Base.sin(d::Dual) = Dual(sin(d.x), d.ϵ * cos(d.x))\n",
    "Base.cos(d::Dual) = Dual(cos(d.x), - d.ϵ * sin(d.x))\n",
    "\n",
    "Dual(2, 2) * Dual(3, 4)"
   ],
   "metadata": {},
   "execution_count": 10
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Finally, we'll hook into Julia's number promotion system; this isn't essential\n",
    "to understand, but just makes it easier to work with Duals since we can now\n",
    "freely mix them with other number types."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "3 + 6ϵ"
     },
     "metadata": {},
     "execution_count": 11
    }
   ],
   "cell_type": "code",
   "source": [
    "Base.convert(::Type{Dual{T}}, x::Dual) where T = Dual(convert(T, x.x), convert(T, x.ϵ))\n",
    "Base.convert(::Type{Dual{T}}, x::Real) where T = Dual(convert(T, x), zero(T))\n",
    "Base.promote_rule(::Type{Dual{T}}, ::Type{R}) where {T,R} = Dual{promote_type(T,R)}\n",
    "\n",
    "Dual(1, 2) * 3"
   ],
   "metadata": {},
   "execution_count": 11
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "We already have enough to start taking derivatives of some simple functions.\n",
    "If we pass a dual number into a function, the $\\epsilon$ component represents\n",
    "the derivative."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "130.0 + -24.0ϵ"
     },
     "metadata": {},
     "execution_count": 12
    }
   ],
   "cell_type": "code",
   "source": [
    "f(x) = x / (1 + x*x)\n",
    "\n",
    "f(Dual(5., 1.))"
   ],
   "metadata": {},
   "execution_count": 12
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "We can make a utility which allows us to differentiate any function."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "-24.0"
     },
     "metadata": {},
     "execution_count": 13
    }
   ],
   "cell_type": "code",
   "source": [
    "D(f, x) = f(Dual(x, one(x))).ϵ\n",
    "\n",
    "D(f, 5.)"
   ],
   "metadata": {},
   "execution_count": 13
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Dual numbers seem pretty scarcely related to all the Wengert list stuff we\n",
    "were talking about earlier. But we need take a closer look at how this is\n",
    "working. To start with, look at Julia's internal representation of `f`."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "CodeInfo(\n\u001b[90m1 ─\u001b[39m %1 = (Base.mul_float)(x, x)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %2 = (Base.add_float)(1.0, %1)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %3 = (Base.div_float)(x, %2)\u001b[36m::Float64\u001b[39m\n\u001b[90m└──\u001b[39m      return %3\n) => Float64"
     },
     "metadata": {},
     "execution_count": 14
    }
   ],
   "cell_type": "code",
   "source": [
    "@code_typed f(1.0)"
   ],
   "metadata": {},
   "execution_count": 14
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "This is just a Wengert list! Though the naming is a little different – `mul_float`\n",
    "rather than the more general `*` and so on – it's still essentially the same\n",
    "data structure we were working with earlier. Moreover, you'll recognise\n",
    "the code for the derivative, too!"
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "CodeInfo(\n\u001b[90m1 ─\u001b[39m %1 = (Base.mul_float)(x, x)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %2 = (Base.mul_float)(x, 1.0)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %3 = (Base.mul_float)(x, 1.0)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %4 = (Base.add_float)(%2, %3)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %5 = (Base.add_float)(1.0, %1)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %6 = (Base.add_float)(0.0, %4)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %7 = (Base.mul_float)(%5, 1.0)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %8 = (Base.mul_float)(x, %6)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %9 = (Base.sub_float)(%7, %8)\u001b[36m::Float64\u001b[39m\n\u001b[90m└──\u001b[39m      return %9\n) => Float64"
     },
     "metadata": {},
     "execution_count": 15
    }
   ],
   "cell_type": "code",
   "source": [
    "@code_typed D(f, 1.0)"
   ],
   "metadata": {},
   "execution_count": 15
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "This code is again the same as the Wengert list derivative we worked out at\n",
    "the very beginning of this handbook. The order of operations is just a little\n",
    "different, and there's the odd missing or new instruction due to the different\n",
    "set of optimisations that Julia applies. Still, we have not escaped our fundamental\n",
    "symbolic differentiation algorithm, just tricked the compiler into doing most\n",
    "of the work for us."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Wengert List\ny1 = cos(x)\ny2 = sin(y1)\ny3 = sin(x)\ny4 = -y3\ny5 = cos(y1)\ny6 = y5 * y4\n"
     },
     "metadata": {},
     "execution_count": 16
    }
   ],
   "cell_type": "code",
   "source": [
    "derive(Wengert(:(sin(cos(x)))), :x)"
   ],
   "metadata": {},
   "execution_count": 16
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "CodeInfo(\n\u001b[90m1 ─\u001b[39m %1 = invoke Main.##365.cos(_3::Float64)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %2 = (Base.neg_float)(1.0)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %3 = invoke Main.##365.sin(_3::Float64)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %4 = (Base.mul_float)(%2, %3)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m      invoke Main.##365.sin(%1::Float64)\u001b[90m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %6 = invoke Main.##365.cos(%1::Float64)\u001b[36m::Float64\u001b[39m\n\u001b[90m│  \u001b[39m %7 = (Base.mul_float)(%4, %6)\u001b[36m::Float64\u001b[39m\n\u001b[90m└──\u001b[39m      return %7\n) => Float64"
     },
     "metadata": {},
     "execution_count": 17
    }
   ],
   "cell_type": "code",
   "source": [
    "@code_typed D(x -> sin(cos(x)), 0.5)"
   ],
   "metadata": {},
   "execution_count": 17
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "What of data structures, control flow, function calls? Although these things\n",
    "are all present in Julia's internal \"Wengert list\", they end up being the same\n",
    "in the tangent program as in the primal; so an operator overloading approach\n",
    "need not deal with them explicitly to do the right thing. This won't be true\n",
    "when we come to talk more about reverse mode, which demands a more complex\n",
    "approach."
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Perturbation Confusion\n",
    "----------------------\n",
    "\n",
    "Actually, that's not quite true. Operator-overloading-based forward mode\n",
    "*almost always* does the right thing, but it is not flawless. This more\n",
    "advanced section will talk about nested differentiation and the nasty bug that\n",
    "can come with it.\n",
    "\n",
    "We can differentiate any function we want, as long as we have the right\n",
    "primitive definitions for it. For example, the derivative of $\\sin(x)$ is\n",
    "$\\cos(x)$."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(0.8775825618903728, 0.8775825618903728)"
     },
     "metadata": {},
     "execution_count": 18
    }
   ],
   "cell_type": "code",
   "source": [
    "D(sin, 0.5), cos(0.5)"
   ],
   "metadata": {},
   "execution_count": 18
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "We can also differentiate the differentiation operator itself. We'll find that\n",
    "the second derivative of $\\sin(x)$ is $-\\sin(x)$."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(-0.479425538604203, -0.479425538604203)"
     },
     "metadata": {},
     "execution_count": 19
    }
   ],
   "cell_type": "code",
   "source": [
    "D(x -> D(sin, x), 0.5), -sin(0.5)"
   ],
   "metadata": {},
   "execution_count": 19
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "This worked because we ended up nesting dual numbers. If we create a dual number\n",
    "whose $\\epsilon$ component is another dual number, then we end up tracking the\n",
    "derivative of the derivative."
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "The issue comes about when we close over a variable that *is itself* being\n",
    "differentiated."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "2"
     },
     "metadata": {},
     "execution_count": 20
    }
   ],
   "cell_type": "code",
   "source": [
    "D(x -> x*D(y -> x+y, 1), 1) # == 1"
   ],
   "metadata": {},
   "execution_count": 20
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "The derivative $\\frac{d}{dy} (x + y) = 1$, so this is equivalent to\n",
    "$\\frac{d}{dx}x$, which should also be $1$. So where did this go wrong? The\n",
    "problem is that when we closed over $x$, we didn't just get a numeric value\n",
    "but a dual number with $\\epsilon = 1$. When we then calculated $x + y$, both\n",
    "epsilons were added as if $\\frac{dx}{dy} = 1$ (effectively $x = y$). If we had\n",
    "written this down, the answer would be correct."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "2"
     },
     "metadata": {},
     "execution_count": 21
    }
   ],
   "cell_type": "code",
   "source": [
    "D(x -> x*D(y -> y+y, 1), 1)"
   ],
   "metadata": {},
   "execution_count": 21
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "I leave this second example as an excercise to the reader. Needless to say,\n",
    "this has caught out many an AD implementor."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "5"
     },
     "metadata": {},
     "execution_count": 22
    }
   ],
   "cell_type": "code",
   "source": [
    "D(x -> x*D(y -> x*y, 1), 4) # == 8"
   ],
   "metadata": {},
   "execution_count": 22
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "More on Dual Numbers\n",
    "--------------------\n",
    "\n",
    "The above discussion presented dual numbers as essentially being a trick for\n",
    "applying the chain rule. I wanted to take the opportunity to present an\n",
    "alternative viewpoint, which might be appealing if, like me, you have any\n",
    "training in physics.\n",
    "\n",
    "Complex arithmetic involves a new number, $i$, which behaves like no other:\n",
    "specifically, because $i^2 = -1$. We'll introduce a number called $\\epsilon$,\n",
    "which is a bit like $i$ except that $\\epsilon^2 = 0$; this is effectively a\n",
    "way of saying the $\\epsilon$ is a very small number. The relevance of this\n",
    "comes from the original definition of differentiation, which also requires\n",
    "$\\epsilon$ to be very small.\n",
    "\n",
    "$$\n",
    "\\frac{d}{dx} f(x) = \\lim_{\\epsilon \\to 0} \\frac{f(x+\\epsilon)-f(x)}{\\epsilon}\n",
    "$$\n",
    "\n",
    "We can see how our definition of $\\epsilon$ works out by applying it to\n",
    "$f(x+\\epsilon)$; let's say that $f(x) = sin(x^2)$.\n",
    "\n",
    "\\begin{align}\n",
    "f(x + \\epsilon) &= \\sin((x + \\epsilon)^2) \\\\\n",
    "                &= \\sin(x^2 + 2x\\epsilon + \\epsilon^2) \\\\\n",
    "                &= \\sin(x^2 + 2x\\epsilon) \\\\\n",
    "                &= \\sin(x^2)\\cos(2x\\epsilon) + \\cos(x^2)\\sin(2x\\epsilon) \\\\\n",
    "                &= \\sin(x^2) + 2x\\cos(x^2)\\epsilon \\\\\n",
    "\\end{align}\n",
    "\n",
    "A few things have happened here. Firstly, we directly expand $(x+\\epsilon)^2$\n",
    "and remove the $\\epsilon^2$ term. We expand $sin(a+b)$ and then apply a *small\n",
    "angle approximation*: for small $\\theta$, $\\sin(\\theta) \\approx \\theta$ and\n",
    "$\\cos(\\theta) \\approx 1$. (This sounds pretty hand-wavy, but does follow from\n",
    "our original definition of $\\epsilon$ if we look at the Taylor expansion of\n",
    "both functions). Finally we can plug this into our derivative rule.\n",
    "\n",
    "\\begin{align}\n",
    "\\frac{d}{dx} f(x) &= \\frac{f(x+\\epsilon)-f(x)}{\\epsilon} \\\\\n",
    "                  &= 2x\\cos(x^2)\n",
    "\\end{align}\n",
    "\n",
    "This is, in my opinion, a rather nice way to derive functions by hand.\n",
    "\n",
    "This also leads to another nice trick, and a third way to look at forward-mode\n",
    "AD; if we replace $x + \\epsilon$ with $x + \\epsilon i$ then we still have\n",
    "$(\\epsilon i)^2 = 0$. If $\\epsilon$ is a small real number (say\n",
    "$1\\times10^{-10}$), this is still true within floating point error, so our\n",
    "derivative still works out."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "0.9689124217106447 - 0.0im"
     },
     "metadata": {},
     "execution_count": 23
    }
   ],
   "cell_type": "code",
   "source": [
    "ϵ = 1e-10im\n",
    "x = 0.5\n",
    "\n",
    "f(x) = sin(x^2)\n",
    "\n",
    "(f(x+ϵ) - f(x)) / ϵ"
   ],
   "metadata": {},
   "execution_count": 23
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "0.9689124217106447"
     },
     "metadata": {},
     "execution_count": 24
    }
   ],
   "cell_type": "code",
   "source": [
    "2x*cos(x^2)"
   ],
   "metadata": {},
   "execution_count": 24
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "So complex numbers can be used to get exact derivatives! This is very efficient\n",
    "and can be written using only one call to `f`."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "0.9689124217106447"
     },
     "metadata": {},
     "execution_count": 25
    }
   ],
   "cell_type": "code",
   "source": [
    "imag(f(x+ϵ)) / imag(ϵ)"
   ],
   "metadata": {},
   "execution_count": 25
  },
  {
   "outputs": [],
   "cell_type": "markdown",
   "source": [
    "Another way of looking at this is that we are doing bog-standard numerical\n",
    "differentiation, but the use of complex numbers avoids the typical problem\n",
    "with that technique (i.e. that a small perturbation ends up being overwhelmed\n",
    "by floating point error). The dual number is then a slight variation which\n",
    "makes the limit $\\epsilon \\rightarrow 0$ exact, rather than approximate.\n",
    "Forward mode AD can be described as \"just\" a clever implementation of\n",
    "numerical differentiation. Both numerical and forward derivatives propagate\n",
    "a perturbation $\\epsilon$ using the same basic rules, and they have the\n",
    "same algorithmic properties."
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.2.0-DEV.177"
  },
  "kernelspec": {
   "name": "julia-1.2",
   "display_name": "Julia 1.2.0-DEV.177",
   "language": "julia"
  }
 },
 "nbformat": 4
}