{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a63c47e6",
   "metadata": {},
   "source": [
    "# Solving a Cubic Equation\n",
    "\n",
    "Cardano's method begins by translating a monic cubic to the\n",
    "depressed form\n",
    "\n",
    "$$\n",
    "y^3+py+q=0.\n",
    "$$\n",
    "\n",
    "If $y=(s_1+s_2)/3$, then $s_1^3$ and $s_2^3$ are the roots of\n",
    "\n",
    "$$\n",
    "t^2+27qt-27p^3=0.\n",
    "$$\n",
    "\n",
    "The three choices are obtained with the cube root of unity\n",
    "$\\omega=(-1+i\\sqrt3)/2$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50a2b9c2",
   "metadata": {},
   "source": [
    "## Cardano's construction in Egison\n",
    "\n",
    "The first match clause handles the depressed cubic. The second\n",
    "performs the translation $x=y-b/3$, and the last divides by the\n",
    "leading coefficient. A small typed quadratic helper keeps the\n",
    "notebook self-contained.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1d39eec2",
   "metadata": {},
   "outputs": [],
   "source": [
    "declare symbol x, a, b, c, d, p, q: MathValue\n",
    "\n",
    "def quadraticRoots\n",
    "  (a : MathValue)\n",
    "  (b : MathValue)\n",
    "  (c : MathValue)\n",
    "  : (MathValue, MathValue) :=\n",
    "  ( ((- b) + sqrt (b ^ 2 - 4 * a * c)) / (2 * a)\n",
    "  , ((- b) - sqrt (b ^ 2 - 4 * a * c)) / (2 * a) )\n",
    "\n",
    "def omega : MathValue := ((-1) + i * sqrt 3) / 2\n",
    "\n",
    "def cubicFormula : MathValue -> MathValue -> (MathValue, MathValue, MathValue) := cF\n",
    "\n",
    "def cF (f : MathValue) (x : MathValue) : (MathValue, MathValue, MathValue) :=\n",
    "  match coefficients f x as list mathValue with\n",
    "    | [$a_0, $a_1, $a_2, $a_3] -> cF' a_3 a_2 a_1 a_0\n",
    "\n",
    "def cF'\n",
    "  (a : MathValue)\n",
    "  (b : MathValue)\n",
    "  (c : MathValue)\n",
    "  (d : MathValue)\n",
    "  : (MathValue, MathValue, MathValue) :=\n",
    "  match (a, b, c, d) as (mathValue, mathValue, mathValue, mathValue) with\n",
    "    | (#1, #0, $p, $q) ->\n",
    "      let (s1, s2) := (2)#(rt 3 $1, rt 3 $2)\n",
    "                         (quadraticRoots 1 (27 * q) ((-27) * p ^ 3))\n",
    "       in ( (s1 + s2) / 3\n",
    "          , (omega ^ 2 * s1 + omega * s2) / 3\n",
    "          , (omega * s1 + omega ^ 2 * s2) / 3 )\n",
    "    | (#1, _, _, _) ->\n",
    "      (3)#($1 - b / 3, $2 - b / 3, $3 - b / 3)\n",
    "        (withSymbols [x, y]\n",
    "          cF\n",
    "            (substitute\n",
    "              [(x, y - b / 3)]\n",
    "              (x ^ 3 + b * x ^ 2 + c * x + d))\n",
    "            y)\n",
    "    | (_, _, _, _) -> cF' 1 (b / a) (c / a) (d / a)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72b5302d",
   "metadata": {},
   "source": [
    "## The depressed cubic\n",
    "\n",
    "Keeping $p$ and $q$ symbolic makes Cardano's radicals visible in\n",
    "the output. The three tuple entries differ only by powers of\n",
    "$\\omega$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4a7f8b9c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(\\frac{1}{3} \\sqrt[3]{\\frac{3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q} + \\frac{1}{3} \\sqrt[3]{\\frac{-3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q}, \\frac{-1}{3} \\sqrt[3]{\\frac{3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q} w + \\frac{1}{3} \\sqrt[3]{\\frac{-3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q} w + \\frac{-1}{3} \\sqrt[3]{\\frac{3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q}, \\frac{1}{3} \\sqrt[3]{\\frac{3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q} w + \\frac{-1}{3} \\sqrt[3]{\\frac{-3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q} w + \\frac{-1}{3} \\sqrt[3]{\\frac{-3}{2} \\sqrt{4 p^{3} + 27 q^{2}} \\sqrt{3} + \\frac{-27}{2} q})$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cF (x ^ 3 + p * x + q) x\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "589dbd2e",
   "metadata": {},
   "source": [
    "## Translation in action\n",
    "\n",
    "The next polynomial is written in factored form so that its roots\n",
    "are known in advance. Egison expands it, extracts its coefficients,\n",
    "depresses it, and reconstructs all three roots.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4950d42b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(2, \\frac{2}{3} \\sqrt{3} i w + \\frac{1}{3} \\sqrt{3} i + 2, \\frac{-2}{3} \\sqrt{3} i w + \\frac{-1}{3} \\sqrt{3} i + 2)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cF ((x - 1) * (x - 2) * (x - 3)) x\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b283169",
   "metadata": {},
   "source": [
    "## General leading coefficient\n",
    "\n",
    "The same function accepts a fully symbolic non-monic cubic\n",
    "$ax^3+bx^2+cx+d$. Its first action is normalization by $a$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "cff92e77",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(\\frac{-1}{3} a^{-1} b + \\frac{1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1} + \\frac{1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{-3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1}, \\frac{-1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1} w + \\frac{1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{-3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1} w + \\frac{-1}{3} a^{-1} b + \\frac{-1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1}, \\frac{1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1} w + \\frac{-1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{-3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1} w + \\frac{-1}{3} a^{-1} b + \\frac{-1}{3} \\sqrt[3]{-b^{3} + \\frac{-27}{2} a^{2} d + \\frac{9}{2} a b c + \\frac{-3}{2} \\sqrt{4 b^{3} d - b^{2} c^{2} + 27 a^{2} d^{2} + 4 a c^{3} - 18 a b c d} \\sqrt{3} a} a^{-1})$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cF (a * x ^ 3 + b * x ^ 2 + c * x + d) x\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62238a8e",
   "metadata": {},
   "source": [
    "## Takeaway\n",
    "\n",
    "Cardano's formula becomes a short executable derivation when\n",
    "coefficient patterns, substitution, and root permutations are\n",
    "first-class operations. The three algebraic branches remain\n",
    "visible instead of being hidden behind a generic solver.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Egison",
   "language": "egison",
   "name": "egison"
  },
  "language_info": {
   "codemirror_mode": "egison",
   "file_extension": ".egi",
   "mimetype": "text/x-egison",
   "name": "egison"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}