Multiply.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multiplication\n",
    "\n",
    "In this notebook, we will program a few different multiplication algorithms and test their efficiency. Of course, we could use the built-in Python multiplication to multiply numbers but for this lesson, we will be programming all of the arithmetic. So, firstly we will be inputting our data using strings of bits. And for two binary strings, we will need to add them. The first function here is binary addition on strings.\n",
    "\n",
    "## Addition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_addition(v,u):\n",
    "    \"\"\"given two binary strings v and u, return their sum as a binary string\"\"\"\n",
    "    if len(v) > len(u):             #if v is longer than u, then we will pad u with 0's on the left to make the strings the same size.\n",
    "        j = u\n",
    "        while len(v) > len(j):\n",
    "            j = \"0\" + j\n",
    "        return binary_string_addition(v,j)\n",
    "    if len(v) < len(u):             #if u is longer than v, then just run the inputs in the opposite order.\n",
    "        return binary_string_addition(u,v)\n",
    "    output = \"\"\n",
    "    carry = 0                       #this function works like gradeschool arithmetic with a carry.\n",
    "    for i in range(1,len(v)+1):     #now that we are guaranteed both strings are the same length, loop through each entry starting from the right-most\n",
    "        s = carry + int(u[-i]) + int(v[-i])   #u[-i] is python's way of saying to take the ith entry from the right.\n",
    "                                    #this operation uses python's internal arithmetic but it will only be adding 1's and 0's.\n",
    "        if s < 2:                   #if the sum is less than 2, then you don't need a carry (because we are working in binary)\n",
    "            output = str(s) + output   \n",
    "            carry = 0\n",
    "        else:                       #if the sum is greater than or equal to 2, then we will set carry to be 1\n",
    "            s = s-2\n",
    "            output = str(s) + output\n",
    "            carry = 1\n",
    "    if carry == 1:                  #then if carry is 1 after adding the left-most column, then we need 1 more column to the left\n",
    "        output = \"1\" + output\n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to test it out on some inputs so let's use Python's arithmetic to test it out. To sum two binary numbers in python, you have to use `int` and add the two numbers then use `bin` to convert them back to binary. For example, to add 100110 and 11101, you would write:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin(int(\"100110\",2)+int(\"11101\",2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The '0b' at the beginning of the string is there to indicate that the string is in binary. The actual answer is 1000011. We can use Python to understand that we just added 38 + 29 = 67"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(int(\"100110\",2))\n",
    "print(int(\"11101\",2))\n",
    "print(int(\"1000011\",2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try the same addition with our code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string_addition(\"100110\",\"11101\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great!!! You can try it out on some more examples. I hard-coded the addition because I don't exactly know how python adds binary numbers (probably more efficiently than my code) but I don't want that to get in the way of the runtime analysis. Since we have our own code, we can analyze its runtime without having to guess at how the programming language does it.\n",
    "\n",
    "### Adding more than two binary strings:\n",
    "\n",
    "For some of these algorithms, it will be nice to have a function that can add together a list of two or more binary strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_addition_list(list_of_strings):\n",
    "    \"\"\"Takes a list of binary strings and sums them all\"\"\"\n",
    "    lenls = len(list_of_strings)\n",
    "    if lenls == 1:\n",
    "        return list_of_strings[0]\n",
    "    else:\n",
    "        m = int(lenls/2)\n",
    "        b1 = binary_string_addition_list(list_of_strings[:m])\n",
    "        b2 = binary_string_addition_list(list_of_strings[m:])\n",
    "        return binary_string_addition(b1,b2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try it out!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string_addition_list([\"100110\",\"11101\",\"10000\",\"1010111\",\"110\",\"11\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Subtraction\n",
    "\n",
    "We will also be using subtraction. Subtraction is a bit trickier than addition. We really only want to be using positive integers, so what do you do when you subtract a smaller positive integer by a larger positive integer? We will just assume this never happens!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_subtraction(v,u):\n",
    "    \"\"\"Input two binary strings with the first string greater than the second string and return the difference.\"\"\"\n",
    "    if len(v) > len(u):\n",
    "        j = u\n",
    "        while len(v) > len(j):\n",
    "            j = \"0\" + j\n",
    "        return binary_string_subtraction(v,j)\n",
    "    output = \"\"\n",
    "    carry = 0\n",
    "    for i in range(1,len(v)+1):\n",
    "        if carry == 0:\n",
    "            if int(v[-i]) >= int(u[-i]):\n",
    "                s = int(v[-i]) - int(u[-i])\n",
    "                output = str(s) + output\n",
    "                carry = 0\n",
    "            else:\n",
    "                output = \"1\" + output\n",
    "                carry = 1\n",
    "        else:\n",
    "            if (int(v[-i]) == 1) & (int(u[-i]) == 0):\n",
    "                output = \"0\" + output\n",
    "                carry = 0\n",
    "            if (int(v[-i]) == 1) & (int(u[-i]) == 1):\n",
    "                output = \"1\" + output\n",
    "                carry = 1\n",
    "            if (int(v[-i]) == 0) & (int(u[-i]) == 0):\n",
    "                output = \"1\" + output\n",
    "                carry = 1\n",
    "            if (int(v[-i]) == 0) & (int(u[-i]) == 1):\n",
    "                output = \"0\" + output\n",
    "                carry = 1\n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string_subtraction(\"100110\",\"11101\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin(int(\"100110\",2)-int(\"11101\",2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that it doesn't work well if you input a smaller number minus a larger number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string_subtraction(\"11101\",\"100110\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin(int(\"11101\",2)-int(\"100110\",2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Can you figure out what is happening when you try to subtract a smaller number minus a bigger number?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multiplication:\n",
    "\n",
    "We will first consider the gradeschool method (learned in elementary school). Here is an implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradeschool(x,y):\n",
    "    \"\"\"Takes two binary strings x,y and returns their product\"\"\"\n",
    "    lenx = len(x)\n",
    "    leny = len(y)\n",
    "    if lenx > leny:                      #if x has more bits than y, then pad the left of y with 0's until they are the same length     \n",
    "        j = y\n",
    "        while lenx > len(j):\n",
    "            j = \"0\" + j\n",
    "        return gradeschool(x,j)\n",
    "    if leny > lenx:                      #if y has more bits than x, then swap their order.\n",
    "        return gradeschool(y,x)\n",
    "    step = [\"\"]*lenx                     #this initializes the list of summands that result from the single bit multiplications.\n",
    "    for xi in range(1,lenx+1):\n",
    "            if x[-xi] == \"1\":              #for each bit in x, if the bit is a 1, then copy y into the step array with the corresponding number of zeros padding the right.\n",
    "                step[-xi] = y + \"0\"*(xi-1)\n",
    "            else:\n",
    "                step[-xi] = \"0\"          #if the bit is 0, then copy down \"0\" in the corresponding entry in step\n",
    "    return binary_string_addition_list(step)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test it out!!!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gradeschool(\"11101\",\"100110\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin(int(\"100110\",2)*int(\"11101\",2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Runtime Analysis of gradeschool:\n",
    "\n",
    "Let's plot gradeschool on a log-linear plot. The slope of the plot will correspond to the degree of the polynomial associated with the runtime. In order to test it out on many different inputs, we will choose random inputs each time. `random_binary_string(n)` will return a random binary string of length n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "import time\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_binary_string(N):\n",
    "    output = \"\"\n",
    "    for i in range(N):\n",
    "        r = random.randint(0,1)\n",
    "        output = output + str(r)\n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_binary_string(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to run gradeschool on inputs of sizes $2^{7},2^{8},\\dots,2^{13}$ and plot the *logs of the* times against the values $7,\\dots,13$ (this code may take a few minutes to run.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#WARNING: this code will take up to around 3 minutes to run. So hit start and go get yourself a treat!\n",
    "\n",
    "x_valuesGS = []\n",
    "y_valuesGS = []  #this initializes two arrays that we will use to store the points that we want to plot.\n",
    "for i in range(7,14): #if you want to iterate from 7 to 13 (inclusive)......\n",
    "    x_valuesGS = x_valuesGS + [i] # this appends i to the end of the x_values array\n",
    "    r1 = random_binary_string(2**i)\n",
    "    r2 = random_binary_string(2**i)\n",
    "    t0 = time.process_time()\n",
    "    x = gradeschool(r1,r2)          \n",
    "    t1 = (time.process_time() - t0)\n",
    "    y_valuesGS = y_valuesGS + [np.log2(t1)] #this appends the log of the amount of time to the end of the y_values array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(x_valuesGS,y_valuesGS, label = \"GS\")\n",
    "plt.xlabel('log_2 of the size of the input')\n",
    "plt.ylabel(\"log_2 of the time taken\")\n",
    "plt.title(\"Gradeschool Time analysis (log-log plot)\")\n",
    "print(x_valuesGS,y_valuesGS)\n",
    "plt.legend(bbox_to_anchor=(0., 1.02, 1., .102), loc=3,\n",
    "           ncol=2, mode=\"expand\", borderaxespad=0.)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your plot should be a straight line. (if its a little crooked at the beginning, that's okay. This plot is called a log-log plot and if you plot the runtime of a polynomial time algorithm on a log-log plot then the the result will be a straight line and the slope of the line will correspond to the degree of the polynomial. In class we saw that gradeschool multiplication should run in $O(n^2)$ time and as you can see from the plot, the slope of the line is roughly 2. Let's do the same analysis on Multiply Karatsuba."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def MultiplyKS(x,y):\n",
    "    lenx = len(x)                  #just like the other arithmetic algorithm, we make sure that the two inputs are of the same length\n",
    "    leny = len(y)\n",
    "    if lenx > leny:\n",
    "        j = y\n",
    "        while lenx > len(j):\n",
    "            j = \"0\" + j\n",
    "        return MultiplyKS(x,j)\n",
    "    if leny > lenx:\n",
    "        return MultiplyKS(y,x)\n",
    "    if lenx == 1:               #here is the base case, if x=0 then return 0. if x=1 then return y.\n",
    "        if x[0] == \"0\":\n",
    "            return \"0\"\n",
    "        if x[0] == \"1\":\n",
    "            return y\n",
    "    if lenx%2 == 1:             #if the length is odd, then we pad it to the left with a 0 to make it even so that it divides in half evenly\n",
    "        x_new = \"0\" + x\n",
    "        y_new = \"0\" + y\n",
    "        return MultiplyKS(x_new,y_new)\n",
    "    mid = int((lenx+1)/2)          #this will take the floor of the length of the inputs.\n",
    "    xL = x[:mid]                #these 4 lines assign the left and right parts of x and y\n",
    "    xR = x[mid:]\n",
    "    yL = y[:mid]\n",
    "    yR = y[mid:]\n",
    "    sum_x = binary_string_addition(xL,xR)       #recall that for Karatsuba, we need to add xL and xR before we multilply\n",
    "    sum_y = binary_string_addition(yL,yR)       #recall that for Karatsuba, we need to add yL and yR before we multilply\n",
    "    R1 = MultiplyKS(xL,yL)                      #here are the recursive calls...\n",
    "    R2 = MultiplyKS(xR,yR)\n",
    "    R3 = MultiplyKS(sum_x,sum_y)\n",
    "    T1 = R1 + \"0\"*lenx                          #this line is equivalent to muliplying R1 times 2^(lenx)\n",
    "    T2 = R2\n",
    "    T3 = binary_string_subtraction(R3,R1)       #these next 3 lines subtract the results from R1,R2,R3 to get the middle term then \"multiply\" it by 2^(mid)\n",
    "    T3 = binary_string_subtraction(T3,R2)\n",
    "    T3 = T3 + \"0\"*mid\n",
    "    result = binary_string_addition_list([T1,T2,T3])    \n",
    "    if len(result)>0:\n",
    "        if int(result) == 0:\n",
    "            return \"0\"\n",
    "        while result[0] == \"0\":\n",
    "            result = result[1:]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test it out!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MultiplyKS(\"11101\",\"100110\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin(int(\"100110\",2)*int(\"11101\",2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's do the same analysis as we did with gradeschool and plot the runtime of MultiplyKS on a log log plot to estimate the degree of the polynomial using the slope. We will plot both MultiplyKS and gradeschool on the same plot so that we can compare them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#WARNING: this code will take up to around 3 minutes to run. So hit start and go get yourself a treat!\n",
    "\n",
    "x_valuesKS = []\n",
    "y_valuesKS = []  #this initializes two arrays that we will use to store the points that we want to plot.\n",
    "for i in range(7,14): #if you want to iterate from 7 to 13 (inclusive)\n",
    "    x_valuesKS = x_valuesKS + [i] # this appends i to the end of the x_values array\n",
    "    r1 = random_binary_string(2**i)\n",
    "    r2 = random_binary_string(2**i)\n",
    "    t0 = time.process_time()\n",
    "    x = MultiplyKS(r1,r2)\n",
    "    t1 = (time.process_time() - t0)\n",
    "    y_valuesKS = y_valuesKS + [np.log2(t1)] #this appends the log of the amount of time to the end of the y_values array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(x_valuesGS,y_valuesGS,label = \"GS\")\n",
    "plt.plot(x_valuesKS,y_valuesKS,label = \"KS\")\n",
    "plt.xlabel('log_2 of the size of the input')\n",
    "plt.ylabel(\"log_2 of the time taken\")\n",
    "plt.title(\"gradeschool and MultiplyKS Time analysis (log-log plot)\")\n",
    "print(\"GS values: \",x_valuesGS,y_valuesGS)\n",
    "print(\"KS values: \",x_valuesKS,y_valuesKS)\n",
    "plt.legend(bbox_to_anchor=(0., 1.02, 1., .102), loc=3,\n",
    "           ncol=2, mode=\"expand\", borderaxespad=0.)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that they intersect around 2^12 or around 4000. This means that the overhead required for karatsuba is not worth it until your input is bigger than around 4000.\n",
    "\n",
    "## Thresholding\n",
    "\n",
    "There is a technique called \"thresholding\" that we can use. We can combine the two algorithms by initially calling Karatsuba on large inputs and recurse until the recursive calls are smaller than a particular threshold value `T`, then compute using gradescope.\n",
    "\n",
    "Here is an implementation of thresholding:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Threshold_KS_GS(x,y,T):\n",
    "    \"\"\"This will multiply x and y using KS until the size is less than T, in which case it will use GS.\"\"\"\n",
    "    lenx = len(x)                  #just like the other arithmetic algorithm, we make sure that the two inputs are of the same length\n",
    "    leny = len(y)\n",
    "    if lenx > leny:\n",
    "        j = y\n",
    "        while lenx > len(j):\n",
    "            j = \"0\" + j\n",
    "        return Threshold_KS_GS(x,j,T)\n",
    "    if leny > lenx:\n",
    "        return Threshold_KS_GS(y,x,T)\n",
    "    if lenx < T:                #if the lenght is less than T, then use gradeschool (this is just a very large base case.)\n",
    "        return gradeschool(x,y)\n",
    "    if lenx%2 == 1:             #if the length is odd, then we pad it to the left with a 0 to make it even so that it divides in half evenly\n",
    "        x_new = \"0\" + x\n",
    "        y_new = \"0\" + y\n",
    "        return Threshold_KS_GS(x_new,y_new,T)\n",
    "    mid = int((lenx)/2)          #this will divide the input size by 2.\n",
    "    xL = x[:mid]                #these 4 lines assign the left and right parts of x and y\n",
    "    xR = x[mid:]\n",
    "    yL = y[:mid]\n",
    "    yR = y[mid:]\n",
    "    sum_x = binary_string_addition(xL,xR)       #recall that for Karatsuba, we need to add xL and xR before we multilply\n",
    "    sum_y = binary_string_addition(yL,yR)       #recall that for Karatsuba, we need to add yL and yR before we multilply\n",
    "    R1 = Threshold_KS_GS(xL,yL,T)                      #here are the recursive calls...\n",
    "    R2 = Threshold_KS_GS(xR,yR,T)\n",
    "    R3 = Threshold_KS_GS(sum_x,sum_y,T)\n",
    "    T1 = R1 + \"0\"*lenx                          #this line is equivalent to muliplying R1 times 2^(lenx)\n",
    "    T2 = R2\n",
    "    T3 = binary_string_subtraction(R3,R1)       #these next 3 lines subtract the results from R1,R2,R3 to get the middle term then \"multiply\" it by 2^(mid)\n",
    "    T3 = binary_string_subtraction(T3,R2)\n",
    "    T3 = T3 + \"0\"*mid\n",
    "    result = binary_string_addition_list([T1,T2,T3])    \n",
    "    if len(result)>0:\n",
    "        if int(result) == 0:\n",
    "            return \"0\"\n",
    "        while result[0] == \"0\":\n",
    "            result = result[1:]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's set the Threshold to be 4000 and see if it improves the runtime:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#WARNING: this code will take up to around 3 minutes to run. So hit start and go get yourself a treat!\n",
    "\n",
    "x_valuesTH4000 = []\n",
    "y_valuesTH4000 = []  #this initializes two arrays that we will use to store the points that we want to plot.\n",
    "for i in range(7,14): #if you want to iterate from 7 to 13 (inclusive)\n",
    "    x_valuesTH4000 = x_valuesTH4000 + [i] # this appends i to the end of the x_values array\n",
    "    r1 = random_binary_string(2**i)\n",
    "    r2 = random_binary_string(2**i)\n",
    "    t0 = time.process_time()\n",
    "    x = Threshold_KS_GS(r1,r2,4000)\n",
    "    t1 = (time.process_time() - t0)\n",
    "    y_valuesTH4000 = y_valuesTH4000 + [np.log2(t1)] #this appends the log of the amount of time to the end of the y_values array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(x_valuesGS,y_valuesGS,label = \"GS\")\n",
    "plt.plot(x_valuesKS,y_valuesKS,label = \"KS\")\n",
    "plt.plot(x_valuesTH4000,y_valuesTH4000,label = \"TH5000\")\n",
    "plt.xlabel('log_2 of the size of the input')\n",
    "plt.ylabel(\"log_2 of the time taken\")\n",
    "plt.title(\"Threshold 4000 Time analysis (log-log plot)\")\n",
    "plt.legend(bbox_to_anchor=(0., 1.02, 1., .102), loc=3,\n",
    "           ncol=2, mode=\"expand\", borderaxespad=0.)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It makes sense that the threshold plot is even with the gradescope plot until it breaks off at around 4000 to be parallel with the KS plot."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $\\color{red}{\\text{Exercise 1}}$\n",
    "\n",
    "Find the threshold T that gives you the best efficiency. (Your answer should be an integer and we are not looking for an exact answer but you should get close.)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cook-Toom-3\n",
    "\n",
    "Karatsuba Multiplication is another name for Cook-Toom-2. Recall that the Cook-Toom-k algorithm splits the input into parts of size n/k and performs 2k-1 recursive calls. When k=2, we get Karatsuba. When k=3,  we get Cook-Toom-3.\n",
    "\n",
    "Now, the naive way to multiply two trinomials: $(ax^2 + bx + c)(dx^2 + ex + f)$ requires 9 multiplications:\n",
    "$$x^4(ad) + x^3(ae+bd) + x^2(af+be+cd) + x(bf+ce) + (cf)$$\n",
    "\n",
    "But by using some matrix algebra, we can reduce the 9 multiplications down to 5.\n",
    "The way to do this is to start with the equation:\n",
    "\n",
    "$$(ax^2 + bx + c)(dx^2 + ex + f) = C_4x^4 + C_3x^3 + C_2x^2 + C_1x + C_0$$\n",
    "\n",
    "And plug in simple values for x to get 5 simple equations. With this system of equations we can construct a matrix that represents the products on the left side in terms of the $C_i$ values and if we invert the matrix, then we get the $C_i$ values in terms of the products.\n",
    "\n",
    "### getting 5 equations.\n",
    "The easiest value to plug in for x is $x=0$. This results in the equation:\n",
    "$$cf = C_0$$\n",
    "\n",
    "It may seem illegal, but the next easiest value to plug in is $x=\\infty$. This results in the equation:\n",
    "$$ad = C_4$$\n",
    "\n",
    "After that, we will plug in $x=1$ which results in:\n",
    "$$(a+b+c)(d+e+f) = C_4+C_3+C_2+C_1+C_0$$\n",
    "\n",
    "Then $x=2$ results in:\n",
    "$$(4a+2b+c)(4d+2e+f) = 16C_4+8C_3 +4C_2 + 2C_1+C_0$$\n",
    "\n",
    "The last value we will use is $x=3$. This results in:\n",
    "$$(9a+3b+c)(9d+3e+f) =81C_4+27C_3 +9C_2 + 3C_1+C_0$$\n",
    "\n",
    "Now we have 5 equations with a product on the left side and a linear combination of $C_i$'s on the right. Let's name the products:\n",
    "\n",
    "* $P_1=cf$\n",
    "* $P_2=ad$\n",
    "* $P_3=(a+b+c)(d+e+f)$\n",
    "* $P_4=(4a+2b+c)(4d+2e+f)$\n",
    "* $P_5=(9a+3b+c)(9d+3e+f)$\n",
    "\n",
    "Then we have the matrix equation:\n",
    "\n",
    "$$\n",
    "\\left(\\begin{array}\n",
    "~P_1     \\\\\n",
    "P_2     \\\\\n",
    "P_3  \\\\\n",
    "P_4     \\\\\n",
    "P_5\n",
    "\\end{array}\\right) = \n",
    "\\left(\\begin{array}\n",
    "   ~ 1     &   0       & 0     &   0  &0       \\\\\n",
    "0       &   0       & 0     &   0 & 1       \\\\\n",
    "1       &   1       & 1     &   1 & 1       \\\\\n",
    "1       &   2       &4     &   8 & 16       \\\\\n",
    "1       &   3       & 9     &   27 & 81       \\\\\n",
    "\\end{array}\\right)  \n",
    "\\left(\\begin{array}\n",
    "~C_0     \\\\\n",
    "C_1    \\\\\n",
    "C_2  \\\\\n",
    "C_3     \\\\\n",
    "C_4\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "\n",
    "\n",
    "Now, we can take the inverse to get the $C$'s in terms of the $P$'s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sympy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = sympy.Matrix([[1, 0,0,0,0],\n",
    "              [0,0,0,0,1],\n",
    "             [1,1,1,1,1],\n",
    "             [1,2,4,8,16],\n",
    "             [1,3,9,27,81]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = M.inv()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means that:\n",
    "$$\n",
    "\\left(\\begin{array}\n",
    "~C_0     \\\\\n",
    "C_1     \\\\\n",
    "C_2  \\\\\n",
    "C_3     \\\\\n",
    "C_4\n",
    "\\end{array}\\right) = \n",
    "\\left(\\begin{array}\n",
    "   ~ 1     &   0       & 0     &   0  &0       \\\\\n",
    "-11/6       &  -6       & 3     &   -3/2 & 1/3       \\\\\n",
    "1       &   11       & -5/2     &   2 & -1/2       \\\\\n",
    "-1/6       &   -6      &1/2     &   -1/2 & 1/6       \\\\\n",
    "0       &  1       & 0    &   0 &0      \\\\\n",
    "\\end{array}\\right)  \n",
    "\\left(\\begin{array}\n",
    "~P_1     \\\\\n",
    "P_2     \\\\\n",
    "P_3  \\\\\n",
    "P_4     \\\\\n",
    "P_5\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "\n",
    "Or in other words:\n",
    "* $C_0 = P_1$\n",
    "* $C_1 = (-11/6)P_1-6P_2+3P_3-(3/2)P_4 + (1/3)P_5$\n",
    "* $C_2 = P_1 + 11P_2 -(5/2)P_3 +2P_4 - (1/2)P_5$\n",
    "* $C_3 = -(1/6)P_1 -6P_2 + (1/2)P_3 -(1/2)P_4 + (1/6)P_5$\n",
    "* $C_4 = P_2$\n",
    "\n",
    "This looks a bit messy. And it is. But let's try to get around doing a lot of dividing. We will multiply each equation above by the minimum value to make it an integer coefficient equation:\n",
    "\n",
    "* $C_0 = P_1$\n",
    "* $6C_1 = -11P_1-36P_2+18P_3-9P_4 + 2P_5$\n",
    "* $2C_2 = 2P_1 +22P_2 -5P_3 +4P_4-P_5$\n",
    "* $6C_3 = -P_1 -36P_2+3P_3 -3P_4 + P_5$\n",
    "* $C_4 = P_2$\n",
    "\n",
    "So, now the only numbers we need to divide by are by 2 and by 6 but we can get away with dividing by 2 and then by 3 to get 6. One worry would be fractional parts, but by the way we set it up, whenever we divide by 2 or 6, we will be guaranteed to perform the division on a multiple of 2 or 6 so that they will divide evenly and result in an integer.\n",
    "\n",
    "Also, we will need a quick way to multiply by 2, 3, 5 and 11. Multiplying by 2 is easy, just add some 0's to the right. Multiplying by 3,5 and 11 will need a little more work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_divide_2(x):\n",
    "    \"\"\"Input is an even binary string, result is that integer divided by 2\"\"\"\n",
    "    return x[:-1]                 #dividing an even binary string by 2 is the same as just deleting the rightmost \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string_divide_2(\"110001010\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_divide_3(x):\n",
    "    \"\"\"Input is a binary string that is a multiple of 3, result is that integer divided by 3\"\"\"\n",
    "    if x == \"\":                                      #don't worry so much about how this implementation works, but it is based on long division.\n",
    "        return \"\"\n",
    "    if x[0] == \"0\":\n",
    "        return \"0\" + binary_string_divide_3(x[1:])\n",
    "    if x[0:2] == \"11\":\n",
    "        return \"01\" + binary_string_divide_3(x[2:])\n",
    "    if x[0:3] == \"100\":\n",
    "        return \"001\" + binary_string_divide_3(\"1\" + x[3:])[1:]\n",
    "    if x[0:3] == \"101\":\n",
    "        return \"001\" + binary_string_divide_3(\"10\" + x[3:])[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_divide_6(x):\n",
    "    \"\"\"Input is a binary string that is a multiple of 6, result is that integer divided by 6\"\"\"\n",
    "    result = binary_string_divide_2(x)\n",
    "    result = binary_string_divide_3(result)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_2(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 2\"\"\"\n",
    "    return x + \"0\"                 #multiplying by 2 is the same as just adding a \"0\" to the right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_3(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 3\"\"\"\n",
    "    return binary_string_addition(x + \"0\",x) #since 3 is 11 in binary, just add x to 10*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_4(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 2\"\"\"\n",
    "    return x + \"00\"                 #multiplying by 4 is the same as just adding a \"00\" to the right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_5(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 5\"\"\"\n",
    "    return binary_string_addition(x + \"00\",x) #since 5 is 101 in binary, just add x to 100*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_6(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 6\"\"\"\n",
    "    return binary_string_multiply_3(x + \"0\") #this is essentially multiplying by 2 then by 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_9(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 9\"\"\"\n",
    "    return binary_string_multiply_3(binary_string_multiply_3(x)) #this is essentially multiplying by 3 then 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_11(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 11\"\"\"\n",
    "    return binary_string_addition_list([x + \"000\",x +\"0\",x]) #since 11 is 1011 in binary, just add x to 10*x to 1000*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_12(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 12\"\"\"\n",
    "    return binary_string_multiply_3(x + \"00\") #this is essentially multiplying by 4 then by 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_18(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 12\"\"\"\n",
    "    return binary_string_multiply_9(x + \"0\") #this is essentially multiplying by 2 then by 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_22(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 12\"\"\"\n",
    "    return binary_string_multiply_11(x + \"0\") #this is essentially multiplying by 2 then by 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_string_multiply_36(x):\n",
    "    \"\"\"Input is a binary string, result is that integer multiplied by 12\"\"\"\n",
    "    return binary_string_multiply_9(x + \"00\") #this is essentially multiplying by 4 then by 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CookToom3(x,y):\n",
    "    lenx = len(x)                  #just like the other arithmetic algorithm, we make sure that the two inputs are of the same length\n",
    "    leny = len(y)\n",
    "    if lenx > leny:\n",
    "        j = y\n",
    "        while lenx > len(j):\n",
    "            j = \"0\" + j\n",
    "        return CookToom3(x,j)\n",
    "    if leny > lenx:\n",
    "        return CookToom3(y,x)\n",
    "    if lenx < 5:               #here is the base case, if x and y are both small then gradeshool them\n",
    "        return gradeschool(x,y) # the reason that we need the base case less than or equal to 4 is because the sum5 and sum6 will increase to a 4bit number even for single bit parts.\n",
    "    if lenx%3 == 1:             #if the length is not a multiple of 3, then we pad it to the left with 0's to make it a multiple of three so that it divides in thirds evenly\n",
    "        x_new = \"00\" + x\n",
    "        y_new = \"00\" + y\n",
    "        return CookToom3(x_new,y_new)\n",
    "    if lenx%3 == 2:             #if the length is not a multiple of 3, then we pad it to the left with a 0 to make it a multiple of three so that it divides in thirds evenly\n",
    "        x_new = \"0\" + x\n",
    "        y_new = \"0\" + y\n",
    "        return CookToom3(x_new,y_new)\n",
    "    thd = int((lenx)/3)          #this will divide the input size by 3\n",
    "    xL = x[:thd]                #these 6 lines assign the left, middle, and right parts of x and y\n",
    "    xM = x[thd:2*thd]\n",
    "    xR = x[2*thd:]\n",
    "    yL = y[:thd]    \n",
    "    yM = y[thd:2*thd]\n",
    "    yR = y[2*thd:]\n",
    "    sum_1 = binary_string_addition_list([xL,xM,xR])    #sum 1 is a+b+c\n",
    "    sum_2 = binary_string_addition_list([yL,yM,yR])    #sum 2 is d+e+f\n",
    "    sum_3 = binary_string_addition_list([xL+\"00\",xM+\"0\",xR])    #sum 3 is 4a+2b+c\n",
    "    sum_4 = binary_string_addition_list([yL + \"00\",yM + \"0\",yR])    #sum 4 is 4d+2e+f\n",
    "    sum_5 = binary_string_addition_list([binary_string_multiply_9(xL),binary_string_multiply_3(xM),xR])    #sum 5 is 9a +3b+c\n",
    "    sum_6 = binary_string_addition_list([binary_string_multiply_9(yL),binary_string_multiply_3(yM),yR])    #sum 6 is 9d +3e+f\n",
    "    \n",
    "    P1 = CookToom3(xR,yR)                      #here are the recursive calls...\n",
    "    P2 = CookToom3(xL,yL)\n",
    "    P3 = CookToom3(sum_1,sum_2)\n",
    "    P4 = CookToom3(sum_3,sum_4)\n",
    "    P5 = CookToom3(sum_5,sum_6)\n",
    "    P1t2 = binary_string_multiply_2(P1)                         #this is P1 times 2\n",
    "    P1t11 = binary_string_multiply_11(P1)                         #this is P1 times 11\n",
    "    P2t36 = binary_string_multiply_36(P2)                         #this is P2 times 36\n",
    "    P2t22 = binary_string_multiply_22(P2)                         #this is P2 times 22\n",
    "    P3t18 = binary_string_multiply_18(P3)                         #this is P3 times 18\n",
    "    P3t5 = binary_string_multiply_5(P3)                         #this is P3 times 5\n",
    "    P3t3 = binary_string_multiply_3(P3)                         #this is P3 times 3\n",
    "    P4t9 = binary_string_multiply_9(P4)                         #this is P4 times 9\n",
    "    P4t4 = binary_string_multiply_4(P4)                         #this is P4 times 4\n",
    "    P4t3 = binary_string_multiply_3(P4)                         #this is P4 times 3\n",
    "    P5t2 = binary_string_multiply_2(P5)                         #this is P5 times 2\n",
    "    C0 = P1\n",
    "    pos = binary_string_addition_list([P3t18,P5t2])               \n",
    "    neg = binary_string_addition_list([P1t11,P2t36,P4t9])\n",
    "    C1t6 = binary_string_subtraction(pos,neg)                     #this sets 6C1 = -11P1-36P2+18P3-9P4+2P5\n",
    "    pos = binary_string_addition_list([P1t2,P2t22,P4t4])               \n",
    "    neg = binary_string_addition_list([P3t5,P5])\n",
    "    C2t2 = binary_string_subtraction(pos,neg)                     #this sets 2C2 = 2P1+22P2-5P3+4P4-P5\n",
    "    pos = binary_string_addition_list([P3t3,P5])               \n",
    "    neg = binary_string_addition_list([P1,P2t36,P4t3])\n",
    "    C3t6 = binary_string_subtraction(pos,neg)                     #this sets 6C3 = -P1-36P2+3P3-3P4+P5\n",
    "    C4 = P2\n",
    "    C1 = binary_string_divide_6(C1t6)\n",
    "    C2 = binary_string_divide_2(C2t2)\n",
    "    C3 = binary_string_divide_6(C3t6)\n",
    "    T0 = C0\n",
    "    T1 = C1 + \"0\"*thd\n",
    "    T2 = C2 + \"0\"*(2*thd)\n",
    "    T3 = C3 + \"0\"*(3*thd)\n",
    "    T4 = C4 + \"0\"*(4*thd)\n",
    "    result = binary_string_addition_list([T0,T1,T2,T3,T4])     #add them all together and you are done!\n",
    "    if len(result)>0:\n",
    "        if int(result) == 0:\n",
    "            return \"0\"\n",
    "        while result[0] == \"0\":\n",
    "            result = result[1:]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CookToom3(\"111010011\",\"100110001100\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin(int(\"111010011\",2)*int(\"100110001100\",2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.setrecursionlimit(10000)\n",
    "#We have to increase the recursion limit for Cook-Toom-3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#WARNING: this code will take up to around 3 minutes to run. So hit start and go get yourself a treat!\n",
    "\n",
    "x_valuesCT = []\n",
    "y_valuesCT = []  #this initializes two arrays that we will use to store the points that we want to plot.\n",
    "for i in range(7,14): #if you want to iterate from 7 to 13 inclusive\n",
    "    x_valuesCT = x_valuesCT + [i] # this appends i to the end of the x_values array\n",
    "    r1 = random_binary_string(2**i)\n",
    "    r2 = random_binary_string(2**i)\n",
    "    t0 = time.process_time()\n",
    "    x = CookToom3(r1,r2)\n",
    "    t1 = (time.process_time() - t0)\n",
    "    y_valuesCT = y_valuesCT + [np.log2(t1)] #this appends the log of the amount of time to the end of the y_values array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(x_valuesGS,y_valuesGS,label = \"GS\")\n",
    "plt.plot(x_valuesKS,y_valuesKS,label = \"KS\")\n",
    "plt.plot(x_valuesTH4000,y_valuesTH4000,label = \"TH5000\")\n",
    "plt.plot(x_valuesCT,y_valuesCT,label = \"CT\")\n",
    "plt.xlabel('log_2 of the size of the input')\n",
    "plt.ylabel(\"log_2 of the time taken\")\n",
    "plt.title(\"Cook-Toom-3 Time analysis (log-log plot)\")\n",
    "plt.legend(bbox_to_anchor=(0., 1.02, 1., .102), loc=3,\n",
    "           ncol=2, mode=\"expand\", borderaxespad=0.)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the Cook-Toom-3 algorithm has a slightly lower slope than Karatsuba. Theoretically, these slopes should be around 1.585 and 1.465, respectively. Is it worth it to use Cook-Toom-3? Would thresholding help?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cook-Toom-4\n",
    "\n",
    "As you can imagine, Cook-Toom-4 is even more complicated. We will not implement it here but you will calculate the expected runtime and the transformation matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $\\color{red}{\\text{Exercise 2}}$\n",
    "\n",
    "Cook-Toom-4 will run in $O(n^r)$ time for what approximate value of $r$? (you only need to round $r$ to 2 decimal places.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cook-Toom-4 matrix\n",
    "\n",
    "Cook-Toom-4 splits the input into 4 equal parts, then it does some recursive calls and combines them back to get the answer. If you were to do the recursive calls naively, then you would have to do 16 recursive calls:\n",
    "\n",
    "Now, the naive way to multiply two polynomials each with 4 terms: $(ax^3 + bx^2 + cx+d)(ex^3 + fx^2 + gx+h)$ requires 16 multiplications:\n",
    "$$x^6(ae) + x^5(af+be) + x^4(ag + bf +ce) + x^3(ah + bg + cf + de) + x^2(bh + cg + df) + x(ch + dg) + dh$$\n",
    "\n",
    "But by using some matrix algebra, we can reduce the 16 multiplications down to 7.\n",
    "The way to do this is to start with the equation:\n",
    "\n",
    "$$(ax^3 + bx^2 + cx+d)(ex^3 + fx^2 + gx+h) = C_6 x^6 + C_5 x^5 + C_4x^4 + C_3x^3 + C_2x^2 + C_1x + C_0$$\n",
    "\n",
    "And plug in simple values for x to get 7 simple equations. With this system of equations we can construct a matrix that represents the products on the left side in terms of the $C_i$ values and if we invert the matrix, then we get the $C_i$ values in terms of the products.\n",
    "\n",
    "\n",
    "### getting 7 equations.\n",
    "The easiest value to plug in for x is $x=0$. This results in the equation:\n",
    "$$dh = C_0$$\n",
    "\n",
    "It may seem illegal, but the next easiest value to plug in is $x=\\infty$. This results in the equation:\n",
    "$$ae = C_4$$\n",
    "\n",
    "After that, we will plug in $x=1$ which results in:\n",
    "$$(a + b + c+d)(e + f + g+h) = C_6 + C_5 + C_4+C_3+C_2+C_1+C_0$$\n",
    "\n",
    "Then $x=2$ results in:\n",
    "$$(8a + 4b + 2c+d)(8e + 4f + 2g+h) = 64C_6 + 32C_5 + 16C_4+8C_3 +4C_2 + 2C_1+C_0$$\n",
    "\n",
    "Then $x=3$ results in:\n",
    "$$(27a + 9b + 3c+d)(27e + 9f + 3g+h) = 729C_6 + 243C_5 + 81C_4+27C_3 +9C_2 + 3C_1+C_0$$\n",
    "\n",
    "Then $x=4$ results in:\n",
    "$$(64a + 16b + 4c+d)(64e + 16f + 4g+h) = 4096C_6 + 1024C_5 + 256C_4+64C_3 +16C_2 + 4C_1+C_0$$\n",
    "\n",
    "Then $x=5$ results in:\n",
    "$$(125a + 25b + 5c+d)(125e + 25f + 5g+h) = 15625C_6 + 3125C_5 + 625C_4+125C_3 +25C_2 + 5C_1+C_0$$\n",
    "\n",
    "Now we have 7 equations with a product on the left side and a linear combination of $C_i$'s on the right. Let's name the products:\n",
    "\n",
    "* $P_1=dh$\n",
    "* $P_2=ae$\n",
    "* $P_3=(a + b + c+d)(e + f + g+h)$\n",
    "* $P_4=(8a + 4b + 2c+d)(8e + 4f + 2g+h)$\n",
    "* $P_5=(27a + 9b + 3c+d)(27e + 9f + 3g+h) $\n",
    "* $P_6=(64a + 16b + 4c+d)(64e + 16f + 4g+h)$\n",
    "* $P_7=(125a + 25b + 5c+d)(125e + 25f + 5g+h)$\n",
    "\n",
    "Then we have the matrix equation:\n",
    "\n",
    "$$\n",
    "\\left(\\begin{array}\n",
    "~P_1     \\\\\n",
    "P_2     \\\\\n",
    "P_3  \\\\\n",
    "P_4     \\\\\n",
    "P_5 \\\\\n",
    "P_6 \\\\\n",
    "P_7\n",
    "\\end{array}\\right) = \n",
    "\\left(\\begin{array}\n",
    "   ~ 1     &   0       & 0     &   0  &0     &0&0  \\\\\n",
    "0       &   0       & 0     & 0&0&  0 & 1       \\\\\n",
    "1       &   1       & 1     &   1 &1&1& 1       \\\\\n",
    "1       &   2       &4     &   8 & 16  &32&64     \\\\\n",
    "1       &   3       & 9     &   27 & 81    &243&729   \\\\\n",
    "1 & 4 & 16&64& 256 & 1024 & 4096\\\\\n",
    "1   &    5   &  25   &   125   &   625    &   3125   &   15625\n",
    "\\end{array}\\right)  \n",
    "\\left(\\begin{array}\n",
    "~C_0     \\\\\n",
    "C_1    \\\\\n",
    "C_2  \\\\\n",
    "C_3     \\\\\n",
    "C_4      \\\\\n",
    "C_5     \\\\\n",
    "C_6\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $\\color{red}{\\text{Exercise 3}}$\n",
    "\n",
    "Compute the inverse matrix of the matrix given below and enter the second column of the inverse matrix into the canvas quiz prompt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = sympy.Matrix([[1, 0,0,0,0,0,0],\n",
    "             [0,0,0,0,0,0,1],\n",
    "             [1,1,1,1,1,1,1],\n",
    "             [1,2,4,8,16,32,64],\n",
    "             [1,3,9,27,81,243,729],\n",
    "             [1,4,16,64,256,1024,4096],\n",
    "             [1,5,25,125,625,3125,15625]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}