chap_01_introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# Chapter 0: Introduction\n",
    "\n",
    "Code related to [Chapter 0: Introduction](https://introtcs.org/public/lec_01_introduction.html) of the book __Introduction to Theoretical Computer Science__ by Boaz Barak. [![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/boazbk/tcscode/blob/master/chap_01_introduction.ipynb)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "source": [
    "### Grade-school multiplication algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def gradeschool_mult(x,y):\n",
    "    '''Multiply two integers via gradeschool algorithm.'''\n",
    "    x = str(x);\n",
    "    z = 0\n",
    "    for i in range(len(x)):\n",
    "        z += 10**i*int(x[len(x)-1-i])*y\n",
    "\n",
    "    return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def gradeschool_mult(x,y):\n",
    "    \"\"\"Multiply two integers via gradeschool algorithm: recursive implementation\"\"\"\n",
    "    if x<10 or y<10: return x*y\n",
    "    x = str(x); y = str(y);\n",
    "    # convert to string of 0/1's, MSB first\n",
    "    n = max(len(x),len(y))\n",
    "    x = \"0\"*(n-len(x))+x; y = \"0\"*(n-len(y))+y # add leading zeroes if needed\n",
    "    m = n//2\n",
    "    xtop = int(x[:-m]); xbot = int(x[-m:])\n",
    "    ytop = int(y[:-m]); ybot = int(y[-m:])\n",
    "    return 10**(2*m)*gradeschool_mult(xtop,ytop)+10**m*(gradeschool_mult(xtop,ybot)+gradeschool_mult(xbot,ytop))+gradeschool_mult(xbot,ybot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42189"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gradeschool_mult(123,343)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Karatsuba multiplication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def karatsuba_mult(x,y):\n",
    "    '''Multiply two simlar length integers via karatsuba algorithm.'''\n",
    "    if x<100 or y<100: return x*y\n",
    "    x = str(x); y = str(y);\n",
    "    # convert to string of 0/1's, MSB first\n",
    "    n = max(len(x),len(y))\n",
    "    x = \"0\"*(n-len(x))+x; y = \"0\"*(n-len(y))+y # add leading zeroes if needed\n",
    "    m = n//2\n",
    "    xtop = int(x[:-m]); xbot = int(x[-m:])\n",
    "    ytop = int(y[:-m]); ybot = int(y[-m:])\n",
    "    return (10**(2*m)-10**m)*karatsuba_mult(xtop,ytop)+(10**m)*karatsuba_mult(xtop+xbot,ytop+ybot) +(1-10**m)*karatsuba_mult(xbot,ybot)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "karatsuba_mult(12342323,3464565463)==12342323* 3464565463"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42760785998990549"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "12342323* 3464565463"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time both algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "input_lengths  = [2**i for i in range(4,15,2)]\n",
    "gradeschool_times = {}\n",
    "karatsuba_times = {}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gradeschool n = 16\n",
      "448 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Karatsuba n = 16\n",
      "331 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Gradeschool n = 64\n",
      "8.91 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Karatsuba n = 64\n",
      "2.49 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Gradeschool n = 256\n",
      "232 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Karatsuba n = 256\n",
      "21.3 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Gradeschool n = 1024\n",
      "2.63 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Karatsuba n = 1024\n",
      "147 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Gradeschool n = 4096\n",
      "37.4 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Karatsuba n = 4096\n",
      "1.34 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Gradeschool n = 16384\n",
      "10min 23s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n",
      "Karatsuba n = 16384\n",
      "5.9 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "# this can take a while\n",
    "import random\n",
    "for n in input_lengths:\n",
    "    x = random.randrange(10**n)\n",
    "    y = random.randrange(10**n)\n",
    "    r = x*y\n",
    "    #print(r)\n",
    "    print(f\"Gradeschool n = {n}\")\n",
    "    foo =  %timeit -o -r1 -n1 gradeschool_mult(x,y)\n",
    "    print(f\"Karatsuba n = {n}\")\n",
    "    bar = %timeit -o -r1 -n1 karatsuba_mult(x,y)\n",
    "    gradeschool_times[n] = foo\n",
    "    karatsuba_times[n] = bar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "pycharm": {
     "is_executing": true,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEJCAYAAACKWmBmAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deXhU9fX48fch7MgeQMsWkEWRnQhIhaIoopVFrQpaRUWoAq5Vi7Qq1t26/NSifHEpWFHrioC7IgJVWUUEkS2CBCkQlACyJCTn98fnDjMJyWSSmcksOa/nmSczd+bee2YY7pnPLqqKMcYYU5xKsQ7AGGNMfLNEYYwxJihLFMYYY4KyRGGMMSYoSxTGGGOCskRhjDEmKEsUxhhjgrJEYYwxJqjKsQ6gJCJyInADkAp8qqrPlLRPamqqpqWlRTs0Y4xJKsuWLctS1UaFt8ckUYjIC8C5wA5V7RiwfRDwBJACPKeqD6rqGuAaEakEPBvK8dPS0li6dGkUIjfGmOQlIpuL2h6rqqdpwKDADSKSAkwGzgY6ACNEpIP33BBgIfBp+YZpjDEmJolCVecDPxfa3BPYoKoZqpoDvAoM9V4/S1X7AJeWb6TGGGPiqY2iKbAl4HEm0EtE+gPnA9WA94rbWUTGAGMAWrRoEb0ojTGmgomnRCFFbFNVnQfMK2lnVZ0qItuAwVWrVu1R+Pnc3FwyMzM5ePBg2IGasqlevTrNmjWjSpUqsQ7FGFMK8ZQoMoHmAY+bAT+V5gCqOhuYnZ6ePvqog2dmUrt2bdLS0hApKieZaFJVdu3aRWZmJq1atYp1OMaYUoincRRLgLYi0kpEqgLDgVmlOYCIDBaRqdnZ2Uc9d/DgQRo2bGhJIkZEhIYNG1qJzpgEFJNEISKvAF8C7UUkU0RGqephYDzwIbAGeE1VV5fmuKo6W1XH1K1bt7jzhhm5CYd9/sYkpphUPanqiGK2v0eQBuuSiMhgYHCbNm3KeghjjEksv/4KNWtCFH+IxVPVU9hKKlHE2vbt27nkkkto3bo1PXr04JRTTuHtt98u8/EmTZrEI488ErH40tLSyMrKCvs406ZNY/z48RGIyBhTwNat8NJLcPvtMHgwtG4NtWvDjz9G9bTx1JgdtnguUagqw4YNY+TIkbz88ssAbN68mVmzCjbDHD58mMqVk+qfxRhTGocOwfffw+rV/ttdd0G3brBgAVx2GVSuDO3bw8knwxVXQLVqUQ3JShTlZO7cuVStWpVrrrnmyLaWLVty3XXXMW3aNC688EIGDx7MwIED2bdvHwMGDKB79+506tSJd95558g+9913H+3bt+eMM85g7dq1R7Zv3LiRQYMG0aNHD/r27cv3338PwOuvv07Hjh3p0qUL/fr1AyAvL49bbrmFTp060blzZ5566qkjx3nqqaeOnNd3jJ9//plhw4bRuXNnevfuzcqVK4NuN8aEICcHVq2C//zH/QVYsgRq1YKuXeHSS+Ghh2DtWvCV9M86yyWO/fv9+955Jxx7bFRDTaqfrqUqUfTvf/S2iy6CsWPdP8I55xz9/BVXuFtWFvzhDwWfmzcv6OlWr15N9+7di33+yy+/ZOXKlTRo0IDDhw/z9ttvU6dOHbKysujduzdDhgxh+fLlvPrqq3z99dccPnyY7t2706OHGzIyZswYpkyZQtu2bVm0aBFjx45l7ty5/P3vf+fDDz+kadOm7N69G4CpU6fyww8/8PXXX1O5cmV+/tk/SD41NZXly5fz9NNP88gjj/Dcc89x11130a1bN2bOnMncuXO5/PLLWbFiRbHbjTEBcnNdO0K9erBnD1x9tbvIr18Phw+719x1F3TsCG3bumqlk05yt3btCpYW6td3t3KWVIki2DiKeDNu3DgWLlxI1apVGTduHGeeeSYNGjQAXDXVxIkTmT9/PpUqVWLr1q1s376dBQsWcN5551GzZk0AhgwZAsC+ffv44osvuPDCC48c/9ChQwD89re/5YorruCiiy7i/PPPB+CTTz7hmmuuOVLF5TsvcOQ1PXr04K233gJg4cKFvPnmmwCcfvrp7Nq1i+zs7GK3G1OhvfMOrFzprzZauxZGjoRnn4VjjoE1a1xCGDbMnxBOOMHtW68e3HNPbOMvQlIlilIJVgKoWTP486mpJZYgCjvppJOOXFQBJk+eTFZWFunp6QDUqlXryHMzZsxg586dLFu2jCpVqpCWlnZk/EFRXUzz8/OpV69ekb/mp0yZwqJFi3j33Xfp2rUrK1asQFWL7apazfv1kpKSwmHv146qHvU6ESl2uzFJLS8PfvihYBtCgwbgq8K95RbYsAHS0lwSOOccOO0091ylSvDttzELvaySqo0i2IC7WDv99NM5ePAgzzzjX05j//79Rb42Ozubxo0bU6VKFT777DM2b3Yz//br14+3336bAwcOsHfvXmbPng1AnTp1aNWqFa+//jrgLuzffPMN4NouevXqxd///ndSU1PZsmULAwcOZMqUKUcSQWDVU1H69evHjBkzAJg3bx6pqanUqVOn2O3GJIX8fJcQ5syB557zbz/7bH+J4K9/dQ3M+/b5n3//fdi717/vQw/BoEFHHz+BJFWJIp6rnkSEmTNnctNNN/Hwww/TqFEjatWqxUMPPcSBAwcKvPbSSy9l8ODBpKen07VrV07wiqXdu3fn4osvpmvXrrRs2ZK+ffse2WfGjBlce+213HvvveTm5jJ8+HC6dOnCrbfeyvr161FVBgwYQJcuXejYsSPr1q2jc+fOVKlShdGjRwftzjpp0iSuvPJKOnfuTM2aNZk+fXrQ7cYkFFXYsgWaN3djEaZOddVEa9a4tgWAqlVd+2TlyvCnP8HFF7vSQocOUPjHURz2ugyXFFV9kOjS09O18MJFa9as4cQTT4xRRMbH/h1MzK1dC+++6682+u47VwLYts31Hnr6aXjrLX/7QceOLiHUqxfryKNORJapanrh7UlVojDGGFThf/8r2IawerVLAF26wKJF8Oc/Q6NGLgmMHOkSQvXqbv+xY93NHJFUiSKeB9wZY6Jgxw6XBFatgn79XCKYNw9OP93/moYNXSLwTUh53nmunaHRUUtDm2IkVaKI5zYKY0wYsrLceITjjoOdO+HCC12CCJxy5uGHXaLo0gWeeMJfbdS4ccF5kGrXdjcTsqRKFMaYJKDqGpNXrfKXFnbscNVBkye7AWd5eQXHIZx0kksi4LqqXn99bN9DkrFEYYwpf9nZrhHZlwhWr3bjDp591v36v/de+OUX14j8+9+7RODr5Ve5suuSasqNJQpjTPTs3etPCLt3w803u+1nnw1ffunu16jhEkJ6QGebZctc20KlpBrqlbDsX6EcHXPMMUfuv/fee7Rt25YfIzA98KZNm47MSFsW/fv3p3B3YmNK5ddf4euv/Y8ffNCVEOrUgd69YdQouP9+V60EcMcdMGsWbNzoBqstXQoPPODfv1EjSxJxJKlKFInS6+nTTz/luuuu46OPPqJFixYh7RNs+nFforjkkksiGaYxxVu6FN58019ttGmTSwK7drk2ggYNoE8fGD3a34bQurW/Ufnss2MavimdpErZ8TzNuM+CBQsYPXo07777LscffzwAs2fPplevXnTr1o0zzjiD7du3A27k85gxYxg4cCCXX345mzZtom/fvnTv3p3u3bvzxRdfADBhwgQWLFhA165defzxx1m9ejU9e/aka9eudO7cmfXr17Np0yY6dux4JI5HHnmESZMmHXn80ksv0adPHzp27MjixYsBWLx4MX369KFbt2706dOnwLTmJskdOgTffAMvv+ymqRg2zE1b4Zun6Ouv4dFH3TQVJ58MkybBG2/4xyKMGXP0vikpMXs7JjxJVaIojXKeZRxwM7oOHTqUefPmHZmWA+DUU0/lq6++QkR47rnnePjhh3n00UcBWLZsGQsXLqRGjRrs37+fjz/+mOrVq7N+/XpGjBjB0qVLefDBB3nkkUeYM2cOANdddx033HADl156KTk5OeTl5R1JPsX59ddf+eKLL5g/fz5XXXUVq1at4oQTTmD+/PlUrlyZTz75hIkTJxaY2NAkgZwcWLfOPyht2DDo3h3mzvX/J0hJcRf6Ll38+112mfvPUKVKTMI25avCJopYqFKlCn369OH555/niSeeOLI9MzOTiy++mG3btpGTk0OrVq2OPDdkyBBq1KgBQG5uLuPHj2fFihWkpKSwbt26Is9zyimncN9995GZmcn5559P27ZtS4xtxAi3jHm/fv3Ys2cPu3fvZu/evYwcOZL169cjIuTm5obz9k0s5ea6GU1r1HBtB1u2uEVwAtdEqFTJzXfUvTv07AmvvFL0mgjgLzmYCqHCJopynmUcgEqVKvHaa69xxhlncP/99zNx4kTAlQBuvvlmhgwZwrx58wpUCQVOP/7444/TpEkTvvnmG/Lz86lezH/WSy65hF69evHuu+9y1lln8dxzz9GuXTvy8/OPvMY3bblP4enBRYQ77riD0047jbfffptNmzbRv6himIlPeXmu8ThwTYTcXLjxRnj8cTcIrV27o9dE8H2nGjaE4cNj+x5M3KiwiSJWatasyZw5c+jbty9NmjRh1KhRZGdn07RpU4CgM7BmZ2fTrFkzKlWqxPTp08nLywOgdu3a7N2798jrMjIyaN26Nddffz0ZGRmsXLmSvn37smPHDnbt2sUxxxzDnDlzGBQw9fF//vMfTjvtNBYuXEjdunWpW7dugbimTZsWhU/DhCUjw7UZBM5n1LkzvPiiqy565hl34T/pJP9YhF693L7VqsHMmbGN3ySMuE8UIjIM+D3QGJisqh/FOKSwNWjQgA8++IB+/fqRmprKpEmTuPDCC2natCm9e/fmhx9+KHK/sWPHcsEFF/D6669z2mmnHSltdO7cmcqVK9OlSxeuuOIKDh48yEsvvUSVKlU49thjufPOO6lSpQp33nknvXr1olWrVgXaSADq169Pnz592LNnDy+88AIAt912GyNHjuSxxx7j9MC5c0z5yc+HzZv9ieDQIbdGMrhGtWXL3P0WLVwi6NrVv++mTW56bGPCFJNpxkXkBeBcYIeqdgzYPgh4AkgBnlPVBwOeqw88oqqjSjq+TTMev+zfoRiq8OOPrh1hwAC37ZZbYMoU/5oI4JLBqlXu/vz5rmTQoYPNXWQiIt6mGZ8G/BN40bdBRFKAycCZQCawRERmqep33kv+5j1vTOLy/TATcT2LZswouCYCwJ497sLfsSNcfXXBNRECu37361f+8ZsKKSaJQlXni0haoc09gQ2qmgEgIq8CQ0VkDfAg8L6qLi/umCIyBhgDhDyIzZioys6GJUv81UarVrmEsGgRtG/vVlCbM8clgSuu8Dcq+xqUr7giltEbc0Q8tVE0BbYEPM4EegHXAWcAdUWkjapOKWpnVZ0KTAVX9VTMa47q3WPKTzKupgi4mU19I5RXr3ajkXv0cF3jhg1zr0lNdUng0kv9Yw+uvRbGjYtZ2MaEKp4SRVFXcFXVJ4EnQzpAkCk8qlevzq5du2jYsKElixhQVXbt2lVsl96EkJXlEsGxx7oSwdq1cOqpBddEqF/ftTH06OFmO5071yWIxo2PPp7NZWQSRDwlikygecDjZsBPkTp4s2bNyMzMZOfOnZE6pCml6tWr06xZs1iHUbLDh91U1ocOwa23+ksLO3a45//yFzfpXbNmbrW0wDURjj3WP59RgwZw2mmxex/GREhMej0BeG0Uc3y9nkSkMrAOGABsBZYAl6jq6tIeu6heT8YUafFiN6dR4FiE00+Hl15yDc+tWrmLf2Ay6NoVmjSJdeTGRFxc9XoSkVeA/kCqiGQCd6nq8yIyHvgQ1z32hdImiUSZPdaUs8A1EVavdqWFhx5yz40a5UoMNWu6XkUDB/q7p4q4Se+sqtJUcDErUUSTlSgqqF9/dT2JNm+GCy5w2y6/HP79b/9rqld3bQcfeeM2ly937QotW1qbganw4qpEES1WoqggDhxwF3wReOst+Ne/Cq6JUKmSSxrVq8OgQW4OI1+1UatWBae77t49Zm/DmESRVIlCVWcDs9PT00fHOhYTIT/9BJ99VrANISPD3dLSYNs2lyB69oQrr/QPTvNNXWGLORkTtqRKFCZBHTpUcE2E776DiRNdF9OFC+GPf3TtCm3buhLAZZf5p70eN87GIhgTZUmVKKzqKc7l5rr1D1avdtVBnTq5Se169XLTYoOrFmrTxi2pCa5x+dtv3ZTYNsGdMTGRVInCqp7ixOHDro2gbl3Yt8/1LFq92pUafIsf3XGHSxRt2rhxCb4qo/btCy6SU6+euxljYiapEoWJkdmzYeVKf9XR99+7qSpeeAFq1XJVSa1bw+DBBRfJAZdM7rsvtvEbY4JKqkRhVU/laOtW8BY14pZbXGmhZUuXBM46y78ouYirOjLGJCwbR2FKZ+dOuOkmeOcdV1Jo3tytodCkia2JYEyCqxDjKEwUqbolNm++2Y10vv12/0R3VoIzJqlZojAly811ay5//DH06QPPPuumuzDGVAhJlSisjSLCVF0bQ5UqrkfSeefBn/5kU10YU8Ek1f94VZ2tqmPqBi4Xacpm6VI4+WQ3zgHgscfcQjuWJIypcOx/vSlo3z7XDtGrl5s+Y/fuWEdkjIkxSxTG74MPXBXT44+7KqY1a/xTbhtjKqykaqMwYVqyxK3LsHAh/Pa3sY7GGBMnQhpHISL1gd8AB4BNqpof7cDKIqAxe/T69etjHU78U4Xp010313POgZwcty1wCg1jTIVR3DiKYqueRKSuiEwUkW+Br4D/A14DNovI6yISd4sBW2N2KWzYAGec4abmnj7dbata1ZKEMeYowaqe3gBeBPqqaoEWTRHpAVwmIq1V9floBmgiLDcXHn0U7r7bJYYpU2C0zaFojClesYlCVc8M8twyYFlUIjLRNXu2G1V9/vnw1FPwm9/EOiJjTJwrsdeTOH8UkTu9xy1EpGf0QzMRs28fzJ/v7p93Hnz+Obz5piUJY0xIQuke+zRwCjDCe7wXmBy1iExkvfeem9H13HMhO9uNtO7XL9ZRGWMSSCiJopeqjgMOAqjqL0C5LTUmIq1F5HkReaO8zpkUtm+HESPcHE3HHAPvv+/WfjDGmFIKJVHkikgKoAAi0ggIq3usiLwgIjtEZFWh7YNEZK2IbBCRCQCqmqGqo8I5X4Wza5ebtO+tt1yj9fLlNi7CGFNmoSSKJ4G3gcYich+wELg/zPNOAwYFbvCS0WTgbKADMEJEbIrS0vjlF/e3YUP429/gm2/gzjuty6sxJiwlJgpVnQHcBjwAbAOGqerr4ZxUVecDPxfa3BPY4JUgcoBXgaHhnKfCyM2FBx5wiwj5Fmy66Sb/cqPGGBOGYAPuGvhuwA7gFeBlYLu3LdKaAlsCHmcCTUWkoYhMAbqJyO1B4h0jIktFZOnOnTujEF6cWrwY0tNh4kQYNMi/PKkxxkRIsAF3y3DtEhKwzfdYgdYRjkWK2Kaqugu4pqSdVXWqiGwDBletWrVHhGOLTxMmwMMPu26uM2fCUCuAGWMiL9iAu1blGQiuBNE84HEz4KfSHEBVZwOz09PTK8ZQ49q1YexYuP9+qFMn1tEYY5JUSLPHepMCtgWq+7Z57QyRtARoKyKtgK3AcOCS0hwg6Ve4274dbrgBhg+HYcNcdZMUVRAzxpjICWVk9tXAfOBD4G7v76RwTioirwBfAu1FJFNERqnqYWC8d/w1wGuquro0x03aSQFV4fnnXeP022/D1q1uuyUJY0w5CKVEcQNwMvCVqp4mIifgEkaZqeqIYra/B7xX1uMmZYli/XoYMwbmzYO+fWHqVOvNZIwpV6EkioOqelBEEJFqqvq9iLSPemRlkJRtFF99BV9/7RLEqFG2ZrUxFVhODvz4o6uF3rHD/d2+HS64wC1OGS2hJIpMEakHzAQ+FpFfKGUjc3lJmhLFokWQkeGm4PjjH12310aNYh2VMSbCVN042UqVoF49Nx3b9OkFk8COHW5Y1MUXw7ffut7whbVpE91EEdIKd0deLPI7oC7wgTcoLi6lp6frUt/As0Sydy/89a/wz39C+/buW1HZVqs1JpEcPgxZWQUv9GlpcOqpcOCAm+E/8LnDh90ECnff7bYdeyykpLjfhk2auAUox41zvd+zs11P+CZN/M81auSWlomE4la4K/EqJCK9gdWquldVPxeR2kA3YFFkQouchC5RzJnjurpmZrpvxX33WZIwJk7k5bmLN8BHH7n/pr6L/fbt0K0b3HabKyHUrQv79xfc/6qrXKKoXh1273ZDn7p181/w+/Rxr2vUyCWPhg2LrmWuWxdGjozuey1KiSUKEfka6K7eC0WkErBUVbuXQ3xlknAliu++c1OBn3QSPPssnHJKrCMyJqmpumVafBf6vDz/7Pv33gsrVhRMBCefDJ984p5v0wY2bnT3a9d2v+qHDnULR4L7W6OGPwk0aeJKCbVrl//7LK0ylyhwyeRINlHVfBGxn7rhUnXTb/Tq5WZ6nT0bBg6MXBnSmApq82b44YeC1Tt5eW46NHDNfm++CQcP+vdp3x6+/97dX7oU1q1zF/ju3V0i6NTJ/9pZs6BmTbe9Zs2jz//nP0fvvcVKKBf8DBG5HnjGezwWyIheSGWXMFVP69a5Lq8LFsDKlf6FhYwxBQTW93fq5KpjPvoIPv7Y3+C7Y4erztm40Q0tuusu1yDsk5ICrVr5E8Wpp7pf+L46/iZNCk6RNnNm8Jg6VMA5rUOpemqMm2r8dNwcT58CN6rqjuiHVzZxW/WUkwP/+Afcc48rm/7jH67y0rq8mgokJwf+97+CVTs7dsC117qeP9Onu/8a27e7pVV8l6isLP8M+o88UrBBt0kTeOYZVyBfsQJ+/tn/fIMG9l8sVGWuevISwvCoRFWR5OW5xYOWLoWLLoInnnA/a4xJcKquw17Vqq6x9scf3Qq8hRPBM8+4Lpwvvgijixjp9Pvfu0RRty60a+fGlwYmgxo13Ovuusv91ipuYoKuXaP3XiuqUHo9PQzcCxwAPgC64EoUL0U5tuRw4ID7hqekuNLDnXfC4MGxjsqYoPLzXf/+wIt9jx7Qti2sWeN6+AT29T940M0uM2yY65tx7bXuOA0b+n/x5+a6bb/7neuzEdjYG5gIhg1zt+JUqRLd926OFkobxUBVvU1EzsPN8Hoh8BkQd4ki7tooZs92XV6fesp9833/e4yJAVX3KzwnBz77rGAd//btcN557mu6fr2rhz98uOD+//ynSxQisGWLu7i3a+e/2Pvq7n/3OzcdWaNGRV/U27Z1N5M4QkkUvn/qc4BXVPVnidPJ6OJmCg9VV3qYNs2VtX/zm5iGY5LXwYP+C32tWu5inZ/vRvIWHt171VXw0ENw6JAb7O9TrZq70Pfs6R4feyzcemvB+v8mTaBFC/f8CSe4doDi1KjhLx2Y5BBKopgtIt/jqp7Gikgj4GAJ+1Rs//2vSxI33uj+Z1qXV1NKmza5X+WBF/rf/MZft3/KKa6KZ88e/z7Dh8Mrr7iG27fecu0FTZq4rp/9+kHv3u51xxzjOtz5EkDt2gXr+2vXdkucGOMT0hQe3noUe1Q1T0RqAbVV9X9Rj66MYt7r6aKL3OicLVvczzxToeXnu144e/ZAa29dyP/8x/WMDmwDaN7c9e8H6NLFPR/onHPg3Xfd/VtucXX+gXX8bdrAiSeW3/syySecAXeo6i8B938Ffo1gbMnn8svhrLMsSSSx3NyC8/ls3+56/owb556/+27XH3/7dti509X3N2vmfjuA6/nz4Yf+qp3Gjf1JBFz3z/z8gvP5BNb3P/JI+b1XY2yEdTTY4LmEdPCgqyWsVAlWrXKT+AZW/ezYAR984C7YN94ITz9dcP9KlVx/hUqVXL1/s2ZuZK/vV3/goK7XXnP1+MX17z/zzOi9T2NKK6kSRcx7PR044EYKjRljYyTigK9/f2DPntNPd331P/nE9esPfG7PHtc20LKl67A2caI7Tu3a/ov9vn1Qv76rXezYsWBjb5Mm/rr+CROCx2aFTZNIQhmZXdTkf9nAZm/50rgTszaKF15wiwt99hn071/+569AsrNh+fKCv/h9S4p36gTvvOMadw8W6nbx3/+6mTpffx0mTTp6dO+YMZCa6qqVfv21YP9+Y5JdcW0UoSSKr4DuwEpAgI7e/YbANar6UeTDDU9MEoWqmzc4Px+++cbWsy6F3FxXj799u7swN20K27bBY48dPbr3scdcAliwwD/bJ7jxjI0bw7/+5ZqHvvvO3S+cCNq1K3oiN2NMeI3Zm4BRqrraO1AH4FbgHuAtIO4SRUwsWOASxLPPWpLA5cstW47+xX/yya7+fedOV+jyzefj89BDbtTvgQNugJfvQt+8uVvZq1kz97rOnWHuXH8SKDyfT4cOrhbQGBO+UBLFCb4kAaCq34lIN1XNiNeBdzHx5JPuanXJJbGOpFyourWWli0rmAjOPNPNxZOf72bsLFxgveUW95o6ddzArX79Ctbx++bpadXKLf5S3Fesbl047bTovkdjjBNKolgrIs8Ar3qPLwbWiUg1IDdqkSWS/HxX93HNNRWmXuPQIf+CfKmp/qqdOnXc85Uru1lA69cv2AXUV99frZp/zEBR7DeIMfEjlDaKGrg1KE7FtVEsBJ7Gjc6uqar7ohqgG+D3NJADzFPVGSXtE7PGbN9kOknqq69cddDzz7sL/YYNroeQTdJmTHIoro2ixFnaVfUA8BRwJ/A34AlV3a+q+WVNEiLygojsEJFVhbYPEpG1IrJBRHwdDM8H3lDV0cCQspwvqg4cgLVr3f0kTRKrV7vJ4k45xS0Y41sJrE0bSxLGVAQlJgoR6Q+sB/6J+2W/TkT6Bd2pZNOAQYEbRCQFmAycDXQARngN580AbzwreWGeN/JmzHCV7YXnW0gC+/a5hdw7dXI9fu+5x60i1qVLrCMzxpSnUNooHsVNNb4WQETaAa8APcp6UlWdLyJphTb3BDaoaoZ3nleBobipzZsBKwiS2ERkDDAGoIVvmstoU3WN2F26FFxUN8Hl5LgRyrVqubWHb7kF/vIXt7aAMabiCWWBwCq+JAGgquvwTz0eSU3xlxzAJYimuC64F4G3ABcAABjwSURBVHgN6rOL21lVp6pquqqmN2rUKArhFeHzz+Hbb+H665Oi2ik72y0zmZbmBpyJwLx58PDDliSMqchCKVEsFZHngX97jy8FlkUhlqKutOpNQnhlSAco7yk8nnzSXUFHjCif80WJb8zCAw+4Vc0uvtj1agJba9gYE1qiuBYYB1yPu5jPx7VVRFom0DzgcTPgpyicJzJ273Ytu9ddl9BzPOze7eYs2roVzj4b7rvPDTA3xhifkNajiMqJXRvFHFXt6D2uDKwDBgBbgSXAJYGD/UJVbt1jfUOKE6xeJj8fli71r2g2aZKbLK9fuF0UjDEJrdRTeIjIt0CxWURVO4cRzCtAfyBVRDKBu1T1eREZD3wIpAAvlDZJlFvVU36+q5NJsASh6qbJnjjRddL6/nu3dvGkSbGOzBgTz4otUYhIy2A7qurmqEQUAVEvUUyd6kadvf++m7YjAfz3v3D77W5KqlatXFfX4cPdgHJjjIEylCjiOREUp1xKFL4usVWruvkpEkBWFgwY4NZhmDwZrr7alvE2xoQuqfq0qOpsVR1Tt27d6J1k7lw3VDnOu8Ru3Aj33+/up6a6tZY3bnTzM1mSMMaURlIlinLx5JPuyjt8eKwjKdK2bS4ZnHAC3HsvZGS47QMG2KpqxpiySapEISKDRWRqdnZ2dE6QkeHWyPzTn6B69eico4z27nXLbx5/vFsSY/RoV4Jo3TrWkRljEl2pE4WITBeRZ0SkYzQCCkfUq56OPRamTIFrr43O8cM0bRqcd57rzfT003DccbGOyBiTDEIZcFfYP4EWwGXAXyIbTpyrWdMtqhwHcnJcyeGNN9y4v9q13SS20WyeMcZUTKUqUYhIJWCtqr6pqnGXJKJa9fTGG26ei7zYTmCblwcvveTaIMaPd4937nTPWZIwxkRDKNOMvywidbwFhL7DrXh3a/RDK72oVT2pwp13uiXbYjj5UWamm17jssvcSnLvvefmJbQqJmNMNIVy1eugqnuAYcB7+KudKo5PP4U1a2LWJfZ//3N/jzvONU6/8gosX+7mZorjHrrGmCQR0jTjIlIFlyjeUdVcgkztkZSefNIt+HzRReV62q+/dsngpJPcFOApKTBzpuuZa7O6GmPKSyiXm/8DNgG1gPne1B57ohlUWUWljWLjRpgzB665xi0UXQ7Wr3fJoHt3WLTIdXu1QXLGmFgp9eyxIiJAiqoejk5I4YvoXE9ffw033QQvvwy/+U1kjhnEhg2uobpaNXfaW25xU28YY0y0FTfXUyiN2feLSOClqh4wKYKxxbdu3dwyb1FMErt2wTvvuPtt2riarowMN7LakoQxJtZCqXo6W1V3+x6o6i/AOdELKY7s3eu6GkWpS+y+fS4ZtG7tqpp8y1uMHQtNmkTllMYYU2qhJIoUETlSOS8iNYDyqayPtVmzoHlz104RQYcOwVNPuek27rjDLRq0dGnCLW9hjKkgQhmZ/RLwqYj8C9fb6SpgelSjKqOITzPuG8mWmhqZ43kyM+Hmm+HUU12VU+/eET28McZEVIklClV9GLgXOBE4CbjH2xZ3Ij7gLivL9UkNs6FA1XVr/fOf3ePjj3crzM2da0nCGBP/Qu2Nvwb4QFX/DCwQkdpRjCl+7Nzp6oPCGLTw2Wdwyilusr5333XjIQBOPNEGyxljEkMovZ5GA2/gxlMANAVmRjOouJGVVeZqp02bYOBA1/6wdSs89xysWmXzMRljEk8obRTjgJ7AIgBVXS8ijaMaVby4+mrYvbvk1xWhbl344Qd47DE3K3mcLV9hjDEhCyVRHFLVHPHqSUSkMhVlCo+zzy7zrvXru2m/baoNY0yiC+Uy9rmITARqiMiZwOvA7OiG5ScirUXkeRF5o7zOecSyZbBjR6l2+e47OP982LLFkoQxJjmEcimbAOwEvgX+hJtB9m+hHFxEXhCRHSKyqtD2QSKyVkQ2iMiEYMdQ1QxVHRXK+SIqLw969nQDHkrh9tvdZLM1a0YpLmOMKWclVj2paj7wLPCsiDQAmmnoE0RNw62I96Jvg4ikAJOBM4FMYImIzAJSgAcK7X+VqpbuJ32k7N4N+fnQqFHIuyxc6Mbo3X+/DZ4zxiSPEhOFiMwDhnivXQHsFJHPVfXmkvZV1fkiklZoc09gg6pmeMd/FRiqqg8A55Yq+mgq5WA7VfjLX9yaETfcEMW4jDGmnIVS9VTXW7jofOBfqtoDOCOMczYFtgQ8zvS2FUlEGorIFKCbiNwe5HVjRGSpiCzd6bvIhyMry/0NsUQxaxZ88QXcfbdVOxljkksovZ4qi8hxwEXAXyNwzqKGmRVblaWqu4BrSjqoqk4VkW3A4KpVq/YIIz7Hl2xCTBR9+7oqpyuvDPvMxhgTV0IpUfwd+BBXXbRERFoD68M4ZybQPOBxM+CnMI53RESn8Dj5ZHjpJTe1awgaNHAN2ZVDSb3GGJNAQpnr6XVV7ayqY73HGap6QRjnXAK0FZFWIlIVGA7MCuN4R0R0hbtmzeDSS6FOnaAv278ffv97+PLL8E9pjDHxqNhEISJ/83o5Fff86SIStPFZRF4BvgTai0imiIzyVsYbjyulrAFeU9XVZQu/oIiWKL79NqSr/5NPwnvvQW5u+Kc0xph4VOxSqCIyFLgNOAgsx42lqA60BboCnwD3q2oEWo4jI2Ca8dHr14dTOwZcdhn8979uqbli7NrlZoLt2xdml9sQRGOMiY5SL4Wqqu+o6m9xDcmrceMc9uDWp+ipqjfFU5KACJcoQpgQ8IEH3CJ4DxQe/WGMMUkklAF36wmv8brcRHThop07oXHxcx/++KMbtD1yJHTsGP7pjDEmXiXVbEQRLVHs3Bm0a+yxx8Ljj7txE8YYk8ySqjNnREsUJVQ9Va0KY8eGfxpjjIl3VqIo+kBuObrRo4t8+uqr3RALY4ypCEJZ4a6diHzqmwFWRDqLSEizxyYsEejfH0444ain5s2D55+HbdvKPSpjjImJUEoUzwK3A7kAqroSN0gu7kRswN327fDqq/5pPDy+if+aNYPx48M7hTHGJIpQEkVNVV1caNvhaAQTrohVPa1YASNGwLp1BTa/9RYsXuwasGvUCO8UxhiTKEJJFFkicjzexH0i8gcguSteipg59vBhmDgROnSAyy+PUVzGGBMDofR6GgdMBU4Qka3AD8AfoxpVrBWxFkVKiusOW6OGTfxnjKlYQhlwlwGcISK1gEqqujf6YZVNxLrHZmW5zFCvXsCx4ZxzwjusMcYkolBWuKsHXA6k4damAEBVr49qZGWgqrOB2enp6UX3aw3Vzp1uLdNKrmbu0UfdvE733ntkkzHGVBihVKK8B3wFfAvkRzecOHHnnXCNWytp507XeD1ggCUJY0zFFEqiqB7K+thJpWlTdwPuuw9+/dWtXmeMMRVRKL+R/y0io0XkOBFp4LtFPbJY+te/4PPP2bIFnn4arroKTjwx1kEZY0xshJIocoB/4BYgWubdlkYzqJi77TZ49VUWL3YLEl1T4ordxhiTvEKperoZaKOqWdEOJlwR6fWUlwc//wypqbRvD3fcAW3bRixEY4xJOKEkitXA/mgHEgkR6fX0yy+Qnw+NGtGxo601YYwxoSSKPGCFiHwGHPJtjMfusRHhG2zXqBEZGW4oRYPkbpExxpigQkkUM71bxeCbviM1lQsucJ2f5syJbUjGGBNLoYzMnl4egcSN3r1h0yZo1IhNm6BPn1gHZIwxsVVsohCR11T1IhH5Fm9CwECq2jmqkcVKlSrQsiV79sDu3dCyZawDMsaY2ApWorjB+3tueQRSHBEZBvweaAxMVtWPonrCTz6BJUvY/PsJgJCWFtWzGWNM3Ct2HIWq+qYSH6uqmwNvQEirRYvICyKyw7c6XsD2QSKyVkQ2iMiEYMdQ1ZmqOhq4Arg4lPOG5d134f772fyjm9PKShTGmIoulAF3Zxax7ewQjz8NGBS4QURSgMneMToAI0Skg4h0EpE5hW6NA3b9m7dfdGVlQaNGdO4MU6cWuRqqMcZUKMHaKK7FlRxai8jKgKdqA/8N5eCqOl9E0gpt7gls8KYvR0ReBYaq6gMUUc0lbrraB4H3VXV5kHjHAGMAWrRoEUp4Rdu5E1JTadECRoc3B60xxiSFYG0ULwPvAw8AgdVDe1X15zDO2RTYEvA4E+gV5PXXAWcAdUWkjapOKepFqjoVt8AS6enpRzW+hywrCxo3ZskSOOYYm+PJGGOKTRSqmg1kAyMifE4p6nRB4ngSeDKkA0diCo/9++GYYxg/HurUgY8/LvuhjDEmGcRiUc9MoHnA42bATzGIo2jLloEqm1vD4MGxDsYYY2IvFkvxLAHaikgrEakKDAdmReLAqjpbVcfUrVu37AepUYODlWqyfbv1eDLGGIhyohCRV3DTk7cXkUwRGaWqh4HxwIfAGuA1VV0dofMNFpGp2dnZZT/IHXfw47MfApYojDEGolz1pKpFtm+o6nu4JVYjfb7wZ4+dPJlNfY8FzrJEYYwxxKbqKWoiUqLIzSW96Tbefx+6dIlcbMYYk6iSKlFEpI0iN5cGdQ4zaBCEcxhjjEkWSZUoIiInh48zT+TTT2MdiDHGxIdYdI+NmrDHUeTlAXDPwv7IFhgwIHKxGWNMokqqEkXYVU8pKZCfz2ZtYQ3ZxhjjSapEEQm5uZCZKZYojDHGk1SJIuxeT3v2sPXS28jPtzEUxhjjk1SJIuyqp3372Pz6IsAShTHG+CRVoghbTg69+YpV97xN796xDsYYY+JDUvV6CltuLtXI4aRW+92qG8YYY5KrRBF2G0VODm9wAS9+EcY05cYYk2SSKlGE3UaRn8//pYzl6U/aRjYwY4xJYFb1FKhTJ7adAO3axToQY4yJH0lVooiEAwegVq1YR2GMMfHDEkWgVas48NPPVD/4S6wjMcaYuJFUiSLsxuyffuLgQaiuByMbmDHGJLCkShRhN2bn5LCR47lvXPws4W2MMbFmjdmBcnOpz25oYB+LMcb4JFWJIly5+3OZwAMsWGkrFhljjI8ligAHqMFDTGDpWhuWbYwxPpYoAhw4YzAA1Zs2jHEkxhgTP+I+UYjIiSIyRUTeEJFro3mug15np+rVo3kWY4xJLFFNFCLygojsEJFVhbYPEpG1IrJBRCYEO4aqrlHVa4CLgPRoxntwzicA1OBANE9jjDEJJdolimnAoMANIpICTAbOBjoAI0Skg4h0EpE5hW6NvX2GAAuBT6MZ7MGNWwErURhjTKCo9gNV1fkiklZoc09gg6pmAIjIq8BQVX0AOLeY48wCZonIu8DL0Yq3c+pPHKIqlYbsjdYpjDEm4cRiwEBTYEvA40ygV3EvFpH+wPlANeC9IK8bA4wBaNGiRZkCk9wcqpILNaqUaX9jjElGsUgUUsQ2Le7FqjoPmFfSQVV1qohsAwZXrVq1R1kCW7W1PlPkn9y6pZIthWqMMZ5Y9HrKBJoHPG4GRGTOjHCn8Fifm8ZkHccvNiegMcYcEYtEsQRoKyKtRKQqMByYFYkDhzsp4MGBQwBrzDbGmEDR7h77CvAl0F5EMkVklKoeBsYDHwJrgNdUdXUkzhduicI3jqJGjUhEY4wxySHavZ5GFLP9PYI0TJeViAwGBrdpU7Y1rw/M/BA4y0oUxhgTIO5HZpdGuCWK/P/toAo5liiMMSZAUiWKcNsoxrf5gJw2J1HW5SyMMSYZJVWiiMTCRVSxMRTGGBMoqRJFuCWKGRmn8Kftf49wVMYYk9iSKlGEW6L4Kv9k3tg3qOQXGmNMBWJrfgY40KMv1XfEOgpjjIkvSVWiCHvA3UEbbGeMMYUlVaKIxIA7SxTGGFNQUiWKcNWoAU2axDoKY4yJL9ZGEeDf/451BMYYE3+SqkQRbhuFMcaYoyVVogh7wJ0xxpijJFWiMMYYE3mWKIwxxgRlicIYY0xQliiMMcYElVSJwno9GWNM5CVVorBeT8YYE3lJlSiMMcZEnqhqrGOIOBHZCWwu4+6pQFYEwykviRo3JG7siRo3JG7siRo3JEbsLVW1UeGNSZkowiEiS1U1PdZxlFaixg2JG3uixg2JG3uixg2JHbtVPRljjAnKEoUxxpigLFEcbWqsAyijRI0bEjf2RI0bEjf2RI0bEjh2a6MwxhgTlJUojDHGBGWJwiMig0RkrYhsEJEJcRBPcxH5TETWiMhqEbnB2z5JRLaKyArvdk7APrd78a8VkbMCtpf7exORTSLyrRfjUm9bAxH5WETWe3/re9tFRJ704lspIt0DjjPSe/16ERkZ5ZjbB3yuK0Rkj4jcGK+fuYi8ICI7RGRVwLaIfcYi0sP7N9zg7StRjPsfIvK9F9vbIlLP254mIgcCPvspJcVX3GcQxdgj9v0QkVYissiL/T8iUjVSsYdFVSv8DUgBNgKtgarAN0CHGMd0HNDdu18bWAd0ACYBtxTx+g5e3NWAVt77SYnVewM2AamFtj0MTPDuTwAe8u6fA7wPCNAbWORtbwBkeH/re/frl+N34n9Ay3j9zIF+QHdgVTQ+Y2AxcIq3z/vA2VGMeyBQ2bv/UEDcaYGvK3ScIuMr7jOIYuwR+34ArwHDvftTgGvL4/te0s1KFE5PYIOqZqhqDvAqMDSWAanqNlVd7t3fC6wBmgbZZSjwqqoeUtUfgA249xVP720oMN27Px0YFrD9RXW+AuqJyHHAWcDHqvqzqv4CfAwMKqdYBwAbVTXYwM2YfuaqOh/4uYiYwv6MvefqqOqX6q5aLwYcK+Jxq+pHqnrYe/gV0CzYMUqIr7jPICqxB1Gq74dXIjodeCMasYfDEoXTFNgS8DiT4BflciUiaUA3YJG3abxXRH8hoFhd3HuI1XtT4CMRWSYiY7xtTVR1G7hECDT2tsdb7ADDgVcCHifCZw6R+4ybevcLby8PV+FKCD6tRORrEflcRPp624LFV9xnEE2R+H40BHYHJMy4uQ5ZonCKqnuNi+5gInIM8CZwo6ruAZ4Bjge6AtuAR30vLWJ3DbI92n6rqt2Bs4FxItIvyGvjKnavXngI8Lq3KVE+82BKG2usPvu/AoeBGd6mbUALVe0G3Ay8LCJ1YhVfMSL1/Yin91SAJQonE2ge8LgZ8FOMYjlCRKrgksQMVX0LQFW3q2qequYDz+KKsVD8e4jJe1PVn7y/O4C3vTi3e1UGvqqDHd7L4yp2XHJbrqrbIXE+c0+kPuNMClb/RP09eA3p5wKXetVJeNU2u7z7y3B1++1KiK+4zyAqIvj9yMJVCVYutD3mLFE4S4C2Xo+Dqrhqh1mxDMirr3weWKOqjwVsPy7gZecBvt4Xs4DhIlJNRFoBbXGNfeX+3kSklojU9t3HNVSu8s7r61UzEngnIPbLvZ45vYFsr8rgQ2CgiNT3ivMDvW3RNoKAaqdE+MwDROQz9p7bKyK9ve/i5QHHijgRGQT8BRiiqvsDtjcSkRTvfmvcZ5xRQnzFfQbRij0i3w8vOX4G/KG8Yg9ZrFvT4+WG6xWyDveL5a9xEM+puGLnSmCFdzsH+Dfwrbd9FnBcwD5/9eJfS0APlfJ+b7jeHN94t9W+c+LqYD8F1nt/G3jbBZjsxfctkB5wrKtwjYAbgCvLIfaawC6gbsC2uPzMcclsG5CL+5U6KpKfMZCOu+htBP6JN0A3SnFvwNXb+77rU7zXXuB9h74BlgODS4qvuM8girFH7Pvh/d9Z7H0erwPVov2dD+VmI7ONMcYEZVVPxhhjgrJEYYwxJihLFMYYY4KyRGGMMSYoSxTGGGOCskRhKiwR+SIKx0wTkUuCPLeqqOfCPGd/EekT8HiaiPwh2D7GlIYlClNhqWqfkl9VamlAkYkiivoD0XgvxgCWKEwFJiL7vL/9RWSeiLwhbk2EGd5oX9+6Gg+JyGLv1sbbXuBXu+9YwINAX3HrEtwU5Nwp4tZgWOJNJvenEGI5x9u2UNz6C3O8CSOvAW7yzumbNK+fiHwhIhlWujDhskRhjNMNuBG3hkBr4LcBz+1R1Z640b//r4TjTAAWqGpXVX08yOtG4abROBk4GRjtTfNQZCwiUh34P9zo3lOBRgCqugm3bsHj3jkXeMc4Dje6/1xc8jKmzCxRGOMsVtVMdRO7rcBVIfm8EvD3lAidbyBu7qUVuOnjG+LmAioulhNwcxz9UCim4sxU1XxV/Q5oEqGYTQVVueSXGFMhHAq4n0fB/xtaxP3DeD+0vKqh0i5ZKcB1qlpgkkMR6V9MLKVdhjTwGBFZwtRUXFaiMKZkFwf8/dK7vwno4d0fClTx7u/FLV1bkg+Ba72p5BGRdt5Mu8X5HmjttUkExlSacxpTJlaiMKZk1URkEe6H1Qhv27PAOyKyGDdD6a/e9pXAYRH5BpgWpJ3iOVyV0nKvRLKTIMtequoBERkLfCAiWbgZRn1mA2+IyFDgurK8QWOCsdljjQlCRDbhpuTOioNYjlHVfV5imQysL6HB3JiIsKonYxLHaK/xezVQF9cLypiosxKFMcaYoKxEYYwxJihLFMYYY4KyRGGMMSYoSxTGGGOCskRhjDEmKEsUxhhjgvr/8VZnwJexmV0AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "gs_lengths, gs_times = zip(*sorted(gradeschool_times.items())) # unpack a list of pairs into two tuples\n",
    "\n",
    "ka_lengths, ka_times =  zip(*sorted(karatsuba_times.items()))\n",
    "\n",
    "gs_times = [t.best for t in gs_times]\n",
    "ka_times = [t.best for t in ka_times]\n",
    "\n",
    "line1, line2 = plt.plot(gs_lengths, gs_times, 'r--', ka_lengths, ka_times, 'b--')\n",
    "plt.xlabel('input length')\n",
    "plt.ylabel('time (secs, log scale)')\n",
    "plt.yscale('log')\n",
    "plt.legend([line1,line2],['Gradeschool','Karatsuba'])\n",
    "plt.show()"
   ]
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}