MATH_242_secret_numbers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Ry_o-kLL_-wf"
   },
   "source": [
    "# Load the preliminary code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "dhOLtwrRRc9S"
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sympy import Poly\n",
    "import sympy as sym\n",
    "import numpy as np\n",
    "from numpy import c_\n",
    "\n",
    "# We'll specify that x and t are variables:\n",
    "x, t = sym.symbols('x, t')\n",
    "\n",
    "ll = \"loaded\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "AHRXKhal_Wcj",
    "outputId": "dbb20901-e961-46a7-a5f1-0290ba92be46"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ">> The page  loaded  correctly!\n"
     ]
    }
   ],
   "source": [
    "lll = \" correctly!\"\n",
    "\n",
    "def rref(matrix):\n",
    "    A = np.array(matrix, dtype=np.float64)\n",
    "    \n",
    "    r = 0 #row\n",
    "    c = 0 #column\n",
    "\n",
    "    (maxr, maxc) = A.shape\n",
    "\n",
    "    prev_row_pivot = -1   # The previous row with a leading term:\n",
    "    tmp_pivot_row = -1\n",
    "    this_pivot_row = -1\n",
    "\n",
    "    for c in range(maxc):  # go through each column\n",
    "      tmp_pivot_row = -1  # reset the tmp pivot row\n",
    "      this_pivot_row = -1  # reset this pivot row\n",
    "      for r in range(maxr):  # Find the leading term in this column below prev_row_pivot\n",
    "        if ((r > prev_row_pivot) and (A[r][c] != 0.0)):\n",
    "          tmp_pivot_row = r  # find the new pivot row\n",
    "      if (tmp_pivot_row > -1):  # we found a candidate for the leading term:\n",
    "        #swap row this_pivot_row with (prev_row_pivot + 1)\n",
    "        A[[tmp_pivot_row, prev_row_pivot+1]] = A[[prev_row_pivot + 1, tmp_pivot_row]]\n",
    "        #set this_pivot_row to prev_row_pivot+1\n",
    "        this_pivot_row = prev_row_pivot + 1\n",
    "        #Now, normalize the row based on the pivot value:\n",
    "        A[ this_pivot_row ] = A[ this_pivot_row ] / A[ this_pivot_row ][c]\n",
    "        #Then, use this row to force 0's above and below the pivot entry:\n",
    "        #subtract multiples of of the this_pivot_row row from the others\n",
    "        for r_ in range(len(A)):\n",
    "            if r_ != this_pivot_row:\n",
    "                A[r_] = A[r_] - A[this_pivot_row] * A[r_][c] / A[this_pivot_row][c]\n",
    "        prev_row_pivot = this_pivot_row\n",
    "    return A    \n",
    "    \n",
    "    \n",
    "\n",
    "print(\">> The page \", ll, lll)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "xVLAg1tp7aJX"
   },
   "source": [
    "# Set up the secret number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "2c12Csd440sV"
   },
   "source": [
    "You'll encode a secret number $s$ into a 4th or 5th degree polynomial as its vertical intercept.\n",
    "\n",
    "Once you've chosen $s$, then create a 4th or 5th degree polynomial $f$ such that the vertical intercept is $s$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 39
    },
    "id": "bSeZFmS4vQWk",
    "outputId": "2f0951d6-e119-41f5-8e03-673f0a987567"
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\operatorname{Poly}{\\left( 3.0 x^{18} + 2.0 x + 14.0, x, domain=\\mathbb{R} \\right)}$"
      ],
      "text/plain": [
       "Poly(3.0*x**18 + 2.0*x + 14.0, x, domain='RR')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the secret number is s:\n",
    "\n",
    "s = 14\n",
    "\n",
    "p = Poly(14+2*x + 3*x**18, x, domain='RR')\n",
    "\n",
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 37
    },
    "id": "buHLWqEJ5Hds",
    "outputId": "8cee7d60-5080-40c7-9c6c-31c375990c3c"
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 14.0$"
      ],
      "text/plain": [
       "14.0000000000000"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#  Change this to evaluate the polynomial at 0:\n",
    "p.eval(x, 0)\n",
    "\n",
    "# Check that this is your secret number:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ls3V1Lrnyr2P"
   },
   "source": [
    "# Generate your data points\n",
    "\n",
    "Use this code to generate the data points for your polynomial.  Write the data on the second page of your handout.  \n",
    "\n",
    "Writing \n",
    "\n",
    "```\n",
    "p.eval(x, 3)\n",
    "```\n",
    "\n",
    "will evaluate $p$ when $x = 3$.  Just change the $3$ to any value to evaluate $p$ at that input.\n",
    "\n",
    "Remember:  Keep your secret number and polynomial hidden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 37
    },
    "id": "5Ef1euoHynYu",
    "outputId": "d30f2a1f-7187-4c9b-c33e-5c1c8d936581"
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 1162261487.0$"
      ],
      "text/plain": [
       "1162261487.00000"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.eval(x, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "a6e9mXs-z3qV"
   },
   "source": [
    "#  Decode the polynomial from another group\n",
    "\n",
    "In this section, we set up a linear system to find the polynomial and the secret number which was given to us by another group.\n",
    "\n",
    "First, set up a linear algebra system to find the polynomial on the handout and then enter the matrix here.  You may have to adjust the size of the matrix below to accommodate your data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "aC4OSnZ20YDh",
    "outputId": "65696657-82c9-4bbf-8372-c23c98ae2c7a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[   -1     1    -1     1    -1     1     8]\n",
      " [    1     1     1     1     1     1    14]\n",
      " [   32    16     8     4     2     1    58]\n",
      " [ 1024   256    64    16     4     1   272]\n",
      " [  243    81    27     9     3     1   148]\n",
      " [16807  2401   343    49     7     1   368]]\n"
     ]
    }
   ],
   "source": [
    "# create the matrix:\n",
    "A = np.matrix([[(-1)**5, (-1)**4, (-1)**3, (-1)**2, -1, 1],\n",
    "               [ (1)**5,  (1)**4,  (1)**3,  (1)**2,  1, 1],\n",
    "               [ (2)**5,  (2)**4,  (2)**3,  (2)**2,  2, 1],\n",
    "               [ (4)**5,  (4)**4,  (4)**3,  (4)**2,  4, 1],\n",
    "               [ (3)**5,  (3)**4,  (3)**3,  (3)**2,  3, 1],\n",
    "               [ (7)**5,  (7)**4,  (7)**3,  (7)**2,  7, 1]])\n",
    " \n",
    "# create the vector for the right hand side:\n",
    "b = np.matrix([[8], [14], [58], [272], [148], [368]])\n",
    "\n",
    "#Make sure the system looks appropriate:\n",
    "\n",
    "print(np.c_[A,b])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "EDZT8emc5iGZ"
   },
   "source": [
    "##  Solve using Row Operations:\n",
    "\n",
    "We'll solve the augmented matrix  $\\left( A \\, | \\, \\vec{b} \\right)$ using the function\n",
    "\n",
    "```\n",
    "rref(np.c_[A,b])\n",
    "```\n",
    "\n",
    "to provide the reduced row echelon form of the matrix system $\\left(A \\, | \\, \\vec{b} \\right)$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "9Qhe2zZjYAVL"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 1.          0.          0.          0.          0.          0.\n",
      "  -0.01666667]\n",
      " [ 0.          1.          0.          0.          0.          0.\n",
      "  -0.71666667]\n",
      " [ 0.          0.          1.          0.          0.          0.\n",
      "   6.25      ]\n",
      " [-0.         -0.         -0.          1.          0.          0.\n",
      "   4.91666667]\n",
      " [ 0.          0.          0.          0.          1.          0.\n",
      "  -3.23333333]\n",
      " [ 0.          0.          0.          0.          0.          1.\n",
      "   6.8       ]]\n"
     ]
    }
   ],
   "source": [
    "print(rref(np.c_[A,b]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6xHgTqYr1fuP"
   },
   "source": [
    "## Solve the system using numerical methods:\n",
    "\n",
    "We can also generate a solution using some more advanced numerical linear algebra techniques contained inside Numpy.\n",
    "\n",
    "To solve it this way, use:\n",
    "\n",
    "\n",
    "\n",
    "```\n",
    "np.linalg.solve(A,b)\n",
    "```\n",
    "\n",
    "or\n",
    "\n",
    "```\n",
    "np.linalg.lstsq(A,b,rcond=None)\n",
    "```\n",
    "\n",
    "The first method requires the matrix $A$ to be square.  The second method is a bit more robust, and can work with any size matrix.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "769dXoztlBcx"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The solution using np.linalg.solve(A,b) is \n",
      "[[-0.01666667]\n",
      " [-0.71666667]\n",
      " [ 6.25      ]\n",
      " [ 4.91666667]\n",
      " [-3.23333333]\n",
      " [ 6.8       ]]\n"
     ]
    }
   ],
   "source": [
    "# Solve the system using a numerical linear algebra solution:\n",
    "solve_sol = np.linalg.solve(A,b)\n",
    "\n",
    "print(\"The solution using np.linalg.solve(A,b) is \")\n",
    "print(solve_sol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "id": "ZEjNcqQvQbYo"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The np.linalg.lstsq(A,b) can work with non-square matrices A\n",
      "It gives back multiple pieces of information:\n",
      "lstsq_sol = \n",
      "(matrix([[-0.01666667],\n",
      "        [-0.71666667],\n",
      "        [ 6.25      ],\n",
      "        [ 4.91666667],\n",
      "        [-3.23333333],\n",
      "        [ 6.8       ]]), matrix([], shape=(1, 0), dtype=float64), 6, array([1.70155760e+04, 1.28731256e+02, 5.91300489e+00, 2.13918002e+00,\n",
      "       9.53598477e-01, 1.56965136e-01]))\n",
      "\n",
      "The solution is first piece returned.  lstsq_sol[0] = \n",
      "[[-0.01666667]\n",
      " [-0.71666667]\n",
      " [ 6.25      ]\n",
      " [ 4.91666667]\n",
      " [-3.23333333]\n",
      " [ 6.8       ]]\n"
     ]
    }
   ],
   "source": [
    "# Solve the system using the numerical least squares method:\n",
    "lstsq_sol = np.linalg.lstsq(A,b,rcond=None)\n",
    "\n",
    "print(\"The np.linalg.lstsq(A,b) can work with non-square matrices A\")\n",
    "print(\"It gives back multiple pieces of information:\")\n",
    "print(\"lstsq_sol = \")\n",
    "print(lstsq_sol)\n",
    "\n",
    "print(\"\")\n",
    "print(\"The solution is first piece returned.  lstsq_sol[0] = \")\n",
    "print(lstsq_sol[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "g95XPHpwy_Re"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyOkho4WoBoeSvj2S/z8fL7K",
   "include_colab_link": true,
   "name": "Math_242_secret_number.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}