sta410hw0.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e6ce86ac",
   "metadata": {},
   "source": [
    "# STA410 Programming Portfolio Assignment (25 points)\n",
    "\n",
    "Welcome.\n",
    "\n",
    "## Rules\n",
    "\n",
    "0. Point awards for assigning the correct values into variables are indicated along with each required variable assignment name.\n",
    "\n",
    "1. **Do not delete or replace cells**: this erases cell ids upon which automated scoring is based.\n",
    "    - Cell ids are supported by [notebook format 4.5](https://github.com/jupyterlab/jupyterlab/issues/9729) or greater, and [jupyterlab](https://jupyter.org/install) version\n",
    "[3.0.13 or greater](https://github.com/jupyterlab/jupyterlab/releases/tag/v3.0.13). If the environment you work in does not support cell ids you will not get any credit for your submitted homework.  [UofT JupyterHub](https://jupyter.utoronto.ca) and [Google Colab](https://colab.research.google.com) support cell ids.\n",
    "      > You may check if cell ids are present or changing at each save with `! grep '\"id\":' <path/to/notebook>.ipynb`\n",
    "\n",
    "    - *You may add cells for scratch work*, but if required answers are not submitted through the provided cells where the answers are requested your answers will not be graded.\n",
    "    - *If you accidentally delete a required cell you can redownload the notebook* (so it has the correct required cells ids) and repopulate it with your answers (assuming you don't overwrite them).\n",
    "    \n",
    "2. **No cells may have any runtime errors**: this causes subsequent tests to fail and you will not get credit for tests which fail because of previous runtime errors.\n",
    "    - The `try`-`except` block syntax \"catches\" runtime errors and transforms them into `exceptions` which are no longer runtime errors.  These `exceptions` will not cause subsequent tests to fail.\n",
    "\n",
    "3. **No jupyter shortcut commands, e.g.,** `! python script.py 10` **may be used**: they will cause subsequent tests to fail.\n",
    "\n",
    "4. Specific code solutions submitted for these assignments must be created either individually or in the context of a paired effort.\n",
    "  \n",
    "  - Students may work individually.  \n",
    "    - Students choosing to work individually must work in accordance with the [University Student Academic Integrity values](https://www.artsci.utoronto.ca/current/academic-advising-and-support/student-academic-integrity)  of \"honesty, trust, fairness, respect, responsibility and courage.\"\n",
    "  - Students may self-select pairs for each assignment.\n",
    "    - Paired students work together and may share work without restriction within their pair; but, must otherwise work in accordance with the [University Student Academic Integrity values](https://www.artsci.utoronto.ca/current/academic-advising-and-support/student-academic-integrity) noted above.\n",
    "    - Paired students each separately submit their (common) work, including (agreeing) contribution of work statements for each problem.\n",
    "    \n",
    "    *Please seek homework partners in person or on the course discussion board on Quercus. Groups of three or more are not allowed; however, students are welcome to amicably seek new partners for each new assignment.* \n",
    "\n",
    "  ***Getting and sharing \"hints\" from other classmates is allowed; but, the eventual code creation work and submission must be your own individual or paired creation.***\n",
    "\n",
    "5. The homework is open book, open notes, open internet, etc.\n",
    "\n",
    "6. You may use any functions available from all library imports below; otherwise, you are expected to create your own Python functionality based on the Python stdlib (standard libary)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11b08ac9",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# You may use any functions available from the following library imports\n",
    "import numpy as np\n",
    "from scipy import stats\n",
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42753104",
   "metadata": {},
   "source": [
    "# Problem 0 (required)\n",
    "\n",
    "Are you working with a partner to complete this assignment?  \n",
    "- If not, assign  the value of `None` into the variable `Partner`.\n",
    "- If so, assign the name of the person you worked with into the variable `Partner`.\n",
    "    - Format the name as `\"<First Name> <Last Name>\"` as a `str` type.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52c51729",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# Required\n",
    "Partner = #None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10f92126",
   "metadata": {},
   "source": [
    "What was your contribution in completing the code for this assignments problems? Assign one of the following into each of the `Problem_X` variables below.\n",
    "\n",
    "- `\"I worked alone\"`\n",
    "- `\"I contributed more than my partner\"`\n",
    "- `\"My partner and I contributed equally\"`\n",
    "- `\"I contributed less than my partner\"`\n",
    "- `\"I did not contribute\"`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe720578",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# Required\n",
    "Problem_1 = #\"I worked alone\"\n",
    "Problem_2 = #\"I worked alone\"\n",
    "Problem_3 = #\"I worked alone\"\n",
    "Problem_4 = #\"I worked alone\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27034598",
   "metadata": {},
   "source": [
    "# Problem 1 (5 points)\n",
    "\n",
    "Complete the function `binary_string(intput_integer, storage_bits=32)` which (when possible) returns a binary string representation of the supplied integer where the leftmost bit is the $\\pm$ sign bit and the rightmost bit is $2^0$.  \n",
    "  \n",
    "*This problem is inspired by Figure 2.1 of Chapter 2.1 **The Fixed-Point Number System** on page 86 of James E. Gentle's **Computational Statistics** textbook, and is additionally intended as a way to help folks get started with Python if they're not yet familiar with it.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ef49479d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Python code doesn't run if it's not consistently indented.\n",
    "\n",
    "# This syntax defines the function `binary_string` with a required and optional input.\n",
    "# Input values are accessed in the function as variables `integer_input`/`storage_bits`.\n",
    "# Unless specified upon calling the function, optional input values get default values.\n",
    "def binary_string(integer_input, storage_bits=16):\n",
    "    \n",
    "    # docstring syntax: run `binary_string?` (without ticks) in a cell to veiw this\n",
    "    \"\"\"integer_input: must be an integer which may be negative\n",
    "       storage_bits : representational storage limits\"\"\"\n",
    "\n",
    "    # The type of Python variables are automatically determined\n",
    "    #   e.g., the type of the variable `storage_bits=16` is `int`\n",
    "    #   e.g., these return `True` or `False` `bool` type values:\n",
    "    #     `type(integer_input)==int` or `integer_input is int`\n",
    "    if type(integer_input) is not int: # if type(integer_input) != int:\n",
    "        return \"Error: this function takes integers only.\"\n",
    "    # We used the \"stronger version\" of the check here; but,\n",
    "    # other than that, this is standard `if` statement usage \n",
    "\n",
    "    # The functions `type` above and `abs` below are part of the Python \"standard libary\"\n",
    "    # and are thus automatically available within any Python programming envirionment\n",
    "    \n",
    "    maximum_representable_integer = 2**(storage_bits) # FIX THIS: it's not correct!!!\n",
    "    # Here's another standard `if` statement usage example\n",
    "    if abs(integer_input) > maximum_representable_integer:\n",
    "        return \"Error: `integer_input` exceeds the representational capability of `storage_bits`.\"\n",
    "    # Interestingly, Python(3) itself does not impose integer representational limitations\n",
    "    # https://stackoverflow.com/questions/7604966/maximum-and-minimum-values-for-ints \n",
    "    # but your program here will have representational limits according to `storage_bits`\n",
    "    \n",
    "    # Python's `list` data type will keep track of the bit representation of `integer_input`\n",
    "    bits = storage_bits*[0]\n",
    "    # Python overloads operators, e.g., `*`, in sensible ways for different data types\n",
    "    # E.g., `k*<a list>` replicates the list `k` times and makes a new list from that\n",
    "    \n",
    "    if integer_input < 0:\n",
    "        # set the sign bit\n",
    "        bits[0] = 1 # the \"zero bit\" is our sign bit: don't change this!\n",
    "        integer_input = abs(integer_input)\n",
    "\n",
    "    # This is Python's for loop syntax which, if `storage_bits == 16` is `True`,\n",
    "    # iterates variable `i` from 1 to 15 (and not 16) which at first seems weird); but,\n",
    "    # this is because Python is 0-indexed, so `range(16)` starts from 0 and goes to 15 \n",
    "    # (iterating 16 times) but `range(1, storage_bits)` starts from 1 and then goes to 15.\n",
    "    for i in range(1, storage_bits):\n",
    "\n",
    "        # Check if each power of two is present in the bit representation of `integer_input`\n",
    "        # and, depending on the \"endianness\" or your encoding, set the appropriate bits to `1`.\n",
    "        # If list position `i` corresponds to `2**(i-1)`, the encoding is \"little-endian\".\n",
    "        # If list position `i` corresponds to `2**(storage_bits-i)`, the encoding is \"big-endian\".\n",
    "        # https://en.wikipedia.org/wiki/Endianness#Etymology\n",
    "        \n",
    "        pass # and then remove this \"pass\" placeholder\n",
    "\n",
    "    # The `[str(i) for i in bits]` construction below is a \"list comprehension\"\n",
    "    #   and is a commonly found tool in the introductory Python contexts.\n",
    "    # The list comprehension here iterates over the elements of list `bits`,\n",
    "    #     assigning each in turn to `bit`, converting `bit` into the `str` type\n",
    "    #     and then returning the transformed versions `bit` as a new list \n",
    "    #     in the same order as the original `bits` list.\n",
    "    return \"\".join([str(bit) for bit in bits])\n",
    "    # The Python object `\"\"` (i.e., an empty string) is a `str` type object.\n",
    "    # Objects in python have their own functions (called methods):\n",
    "    #   the `join` function of the `\"\"` object is called from the `\"\"` object \n",
    "    #   by accessing it with the `.` operator and it accepts a list of strings\n",
    "    #   the elements of which it then concatenates together using itself (`\"\"`).\n",
    "    # \n",
    "    # It is Python objects which may be assigned variable names and referenced \n",
    "    # with them; and, interestingly, a Python function is itself an object:\n",
    "    # `binary_string(<int>)` is shorthand for `binary_string.__call__(<int>)`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c31d58e8",
   "metadata": {},
   "source": [
    "## Hints\n",
    "\n",
    "The function above has the following problems:\n",
    "  - This code is wrong: `maximum_representable_integer = 2**(storage_bits)`\n",
    "  - This loop is empty: `for i in range(1, storage_bits):`\n",
    "\n",
    "\n",
    "The code below has some things to try if you need to figure out what the code is doing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e713a30",
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60341c7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "binary_string(.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7df57c58",
   "metadata": {},
   "outputs": [],
   "source": [
    "[0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27e65f32",
   "metadata": {},
   "outputs": [],
   "source": [
    "16*[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a239748e",
   "metadata": {},
   "outputs": [],
   "source": [
    "a_list = ['a','b','c']\n",
    "a_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "787aaa8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "a_list[0] = 'A'\n",
    "a_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5190847a",
   "metadata": {},
   "outputs": [],
   "source": [
    "a_list[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "152ab4ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "a_list[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "362c8d98",
   "metadata": {},
   "outputs": [],
   "source": [
    "# negative indexes, e.g., `-1` in Python index \"backwards\"\n",
    "# starting from the end of the list and working towards the front\n",
    "a_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "854486ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    a_list[3]\n",
    "except IndexError:\n",
    "    print(\"IndexError: list index out of range\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "057491b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "a_string = \"|\".join(['a','b','c'])\n",
    "a_string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b00a0a02",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "10a91f64",
   "metadata": {},
   "source": [
    "### Problem 1 Question 1 (1 point)\n",
    "\n",
    "What is the value of the sign bit (the first bit read left to right) of a 16-bit integer representation of the number `-7` created by the `binary_string` function?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b4dccb4",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p1q1 = #binary_string(-7, 16)[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b123c4e",
   "metadata": {},
   "source": [
    "### Problem 1 Question 2 (1 point)\n",
    "\n",
    "What is the value of the bit corresponding to `2**10` of a 16-bit integer representation of the number `21845` created by the `binary_string` function?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e601a30",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p1q2 = #binary_string(21845, 16)[5]  #if encoding is \"big-endian\"\n",
    "       #binary_string(21845, 16)[-5] #if encoding is \"little-endian\" \n",
    "                                     #since a negative integer indexes the list in reverse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c367985e",
   "metadata": {},
   "source": [
    "### Problem 1 Question 3 (1 point)\n",
    "\n",
    "What is the value of the bit corresponding to `2**9` of a 16-bit integer representation of the number `-10922` created by the `binary_string` function?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "084524a9",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p1q3 = #binary_string(-10922, 16)[<?>]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1273b83",
   "metadata": {},
   "source": [
    "### Problem 1 Question 4 (2 points)\n",
    "\n",
    "What is the value of the bit corresponding to `2**8` of a 16-bit integer representation of the number `32768` created by the `binary_string` function?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c814f5b",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 2 points\n",
    "p1q4 = #binary_string(32768, 16)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7a99050",
   "metadata": {},
   "source": [
    "### Optional\n",
    "- Here are some extra topics that may be of interest to advanced students."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db537126",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Isn't this too big for a 32-bit integer representation? Why does this work?\n",
    "2**300000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d59473a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    \n",
    "    # This could be converted into a python script. E.g.,\n",
    "\n",
    "    # 1.\n",
    "    # 1. copy the code below into `binary_string.py`\n",
    "    # 1. \n",
    "\n",
    "    # --- from below here\n",
    "    def binary_string(input):\n",
    "        return input\n",
    "    # --- to above here\n",
    "\n",
    "    # 2.\n",
    "    # 2. copy the code below into `script.py`\n",
    "    # 2.\n",
    "\n",
    "    # --- from below here\n",
    "    # Example usage: `python script.py 10`                                                                                                        \n",
    "\n",
    "    import sys\n",
    "    # This is how you load modules (i.e., packages) into your python session                                                                             \n",
    "    # Python is probably the most active community language community around                                                                             \n",
    "    # Whatever you're doing, odds are there's a python package to help you do it                                                                         \n",
    "    import binary_string\n",
    "    # That's because it's very easy to package up code and use it as a module \n",
    "\n",
    "    # The `sys` module let's us grab command line arguments as a list of strings                                                                         \n",
    "    i = int(sys.argv[1])\n",
    "    # Python is \"0\"-indexed, so the first element, `sys.argv[0]`, is not used:                                                                           \n",
    "    # the first command line argument is the python script name, here \"script.py\"                                                                          \n",
    "    # Arguments will initially be strings, so their type may need to be converted \n",
    "    print(binary_string.binary_string(i))\n",
    "    # Just as the `argv` function (i.e., method) is called                                                                                               \n",
    "    #   from the imported `sys` module object as `sys.argv`                                                                                              \n",
    "    # so too do is the `binary_string` function (i.e., method) called from                                                                               \n",
    "    #   the imported `binary_string` module object as `binary_string.binary_string`                                                                      \n",
    "    # --- to above here\n",
    "\n",
    "    # 3.\n",
    "    # 3. Try out the next cell!\n",
    "    # 3.\n",
    "    \n",
    "except ModuleNotFoundError:\n",
    "    \n",
    "    print(\"ModuleNotFoundError: Either module 'sys' or 'binary_string' are not found\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b4cb74f0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "python: can't open file '/Users/schwarls37/UofT/sta410hw0/scriptt.py': [Errno 2] No such file or directory\r\n"
     ]
    }
   ],
   "source": [
    "try: \n",
    "    # Python scripts would be run from the command line, e.g., `python script.py 10`\n",
    "    # This can be run inside of Python code with the following.\n",
    "    import os\n",
    "    return_status = os.system('python script.py 10') \n",
    "    # where return_status indicates if the command line command worked\n",
    "    #\n",
    "    # In a live jupyter notebook this could be run as `! python script.py 10`.\n",
    "    # `!` tells jupyterhub to run this code as an executable command line script\n",
    "    # *************************************************************\n",
    "    # * DO NOT SUBMIT A CELL RUNNING `! python script.py 10` HERE *\n",
    "    # *************************************************************\n",
    "except ModuleNotFoundError:\n",
    "    print(\"ModuleNotFoundError: No module named 'oss'\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea1e9895",
   "metadata": {},
   "source": [
    "# Problem 2 (7 points)\n",
    "\n",
    "Convert the *recursive* function `pseudorandom_integer_sample` called with integers seed `s` and sample size `n` returned by the function `create_integer_sampler` called with integers multiplier `a` and modulus `m` into an *iterative implementation*, i.e., a sequential \"for loop\" based implementation, of the first order sequential congruential method defined by the recursive function\n",
    "\n",
    "  $$u_k = au_{k-1} \\text{ mod } m$$\n",
    "\n",
    "*This problem is inspired by **Generation of Pseudorandom Numbers from a Uniform Distribution** on page 306 in Chapter 7.1 and **Recursion** on page 119-121 in Chapter 3.3 **Efficiency** (and in particular the third and second to last paragraphs on page 120) of James E. Gentle's **Computational Statistics** textbook.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "bdc59f4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# Python code doesn't run if it's not consistently indented\n",
    "def create_integer_sampler(a, m):\n",
    "    \n",
    "    \"\"\"                                                                                                                                              \n",
    "    This function returns a recursive function which will perform\n",
    "    pseudorandom number generation using the first order sequential\n",
    "    congruential method u_k = au_{k-1} mod m defined by arguments\n",
    "\n",
    "    a (integer): multiplier\n",
    "    m (integer): modulus\n",
    "    \"\"\"\n",
    "    # Docstrings (above) are text displayed with the `help` function\n",
    "    # or with a question mark following the name of the function, e.g.,\n",
    "    # `help(create_recursive_function)` or `create_recursive_function?`\n",
    "    # Docstrings should contain helpful information for using a function.\n",
    "    # Write your docstrings so that they facilitate use of your function.\n",
    "                    \n",
    "    def pseudorandom_integer_sample(n, pseudorandom_sample):\n",
    "            \n",
    "        '''This is the docstring: you'll edit this function'''\n",
    "        \n",
    "        # code debugging printouts\n",
    "        # print(a, m, n, pseudorandom_sample)\n",
    "        \n",
    "        if n<=1:\n",
    "            # Infinite recursion avoided.\n",
    "            return pseudorandom_sample\n",
    "\n",
    "        else:\n",
    "            next_pseudorandom_sample = 0 # FIX THIS \n",
    "            if next_pseudorandom_sample in pseudorandom_sample:\n",
    "                print(\"Warning: sampling period reached -- psuedorandom samples are being repeated\")\n",
    "                return pseudorandom_sample\n",
    "                \n",
    "            # Here `pseudorandom_sample` is expected to be a list data type and\n",
    "            # Python overloads the `+` operator in `list_a + list_b` as list concatenation\n",
    "            # i.e., `pseudorandom_sample = pseudorandom_sample + [next_pseudorandom_sample]`\n",
    "            pseudorandom_sample += [next_pseudorandom_sample] # `a = a+b` shorthands `a += b`\n",
    "\n",
    "            return pseudorandom_integer_sample(n-1, pseudorandom_sample)\n",
    "                    \n",
    "    # Functions are \"first class objects\" in Python\n",
    "    return pseudorandom_integer_sample\n",
    "    # so function objects themselves (and not just their results)\n",
    "    # can be returned as the output of a functions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1613c146",
   "metadata": {},
   "source": [
    "## Hints\n",
    "\n",
    "The code above has the following issues:\n",
    "\n",
    "- The code `next_pseudorandom_sample = 0` is wrong in function `pseudorandom_integer_sample`\n",
    "\n",
    "- You will get the following error if you have not yet converted to an interative implementation, which you must do.\n",
    "\n",
    "    > `RecursionError: maximum recursion depth exceeded in comparison`\n",
    "\n",
    "    Do not [increase the maximum recursion stack depth](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) to get around this: *doing so does not address the issue of unnecessarily wasted computational resources*.\n",
    "    \n",
    "    - While recursive functions can be very powerful when used appropriately\n",
    "    \n",
    "    > e.g. see the subsections \"Recursion\", \"Improving Efficiency\", and \"Divide and Conquer\", and Algorithms 3.1 \"Merge\" and 3.2 \"MergeSort\" on pages 119-124 James E. Gentle's Computational Statistics textbook, which build on \n",
    "    > the ubiquitous \"Big O\" and \"little o\" notation prerequesites discussed Section 3.3 \"Efficiency\"\n",
    "\n",
    "    as with all recursive implementations, a recursive implementation of $u_k = au_{k-1} \\text{ mod } m$, e.g.,\n",
    "\n",
    "    ```\n",
    "    def f(a, m, n, s):\n",
    "        if n is 0:\n",
    "            return []\n",
    "        else:\n",
    "            x = a*s % m\n",
    "            return [x] + f(a, m, n-1, x)\n",
    "    ```\n",
    "\n",
    "    entails the overhead of retaining the state of function calls in the \"stack\" until they complete.\n",
    "  \n",
    "    I.e., `f(a, m, n, x)` may not be \"popped\" from the \"stack\" until `[x] + f(a, m, n-1, x)` completes, which means `f(a, m, n, x)` can't be removed from memory until `f(a, m, n-1, x)` is removed from memory.  Thus, despite the natural recusive specification of this problem, the recursive implementation unnecessarily requries more computational resources without providing any recursive divide and conquer benefit compared to an alternative iterative \"for loop\" implementation.\n",
    "\n",
    "- The following code might be helpful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20b094e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10\n",
    "my_list = [0]*n\n",
    "for i in range(n):\n",
    "    my_list[i] = i\n",
    "my_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "94b1e89b",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_psuedor_sampler = create_integer_sampler(a=811, m=7919)\n",
    "seed = 10\n",
    "len(my_psuedor_sampler(n=4000, pseudorandom_sample=[seed]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "001cea60",
   "metadata": {},
   "source": [
    "### Problem 2 Questions 1-4 (4 points)\n",
    "\n",
    "What are the *periods*, i.e., the number of unique pseudorandom integers generated by the first order sequential congruential method defined by the following specifications before the numbers begin cycling?\n",
    "\n",
    "- `create_integer_sampler(a=811, m=7919)`\n",
    "- `create_integer_sampler(a=7907, m=7919)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30b0fc1b",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "my_psuedor_sampler = create_integer_sampler(a=811, m=7919)\n",
    "seed = #"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58687895",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p2q1 = #len(my_psuedor_sampler(n= , pseudorandom_sample=[seed]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40083ed3",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p2q2 = #len(create_integer_sampler(a=7907, m=7919)(n= , pseudorandom_sample=[ ]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a38f105e",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p2q3 = #len(create_integer_sampler(a=3967, m=7919)(n= , pseudorandom_sample=[ ]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fba1969a",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p2q4 = #len(create_integer_sampler(a=7883, m=7919)(n= , pseudorandom_sample=[ ]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a95ddf3",
   "metadata": {},
   "source": [
    "### Problem 2 Question 5 (1 point)\n",
    "\n",
    "Does it appear (\"Yes\" or \"No\") that the *seed* affects the *period* of the first order sequential congruential method?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0ef4a86",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p2q5 = #<\"Yes\"|\"No\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c784d2ab",
   "metadata": {},
   "source": [
    "### Problem 2 Question 6 (1 point)\n",
    "\n",
    "Is the first order sequential congruential method (\"Yes\" or \"No\") designed to produce $0$ or $m$ (as in $u_k = au_{k-1} \\text{ mod } m$)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aac1ee14",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p2q6 = #<\"Yes\"|\"No\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e428198",
   "metadata": {},
   "source": [
    "### Problem 2 Question 7 (1 point)\n",
    "\n",
    "Assuming none of the specifications from questions 1-4 above exhibit any systematic patterns in their pseudorandom number sequences that do not appear random, which $a$ specification is preferred for producing uniform random numbers between $0$ to $1$ $\\tilde u_k=u_k/m$ for $k=1,\\cdots n$ from $u_k = au_{k-1} \\text{ mod } m$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b2ea891",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "a = #\n",
    "p2q7 = a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ccce959",
   "metadata": {},
   "source": [
    "# Problem 3 (7 points)\n",
    "\n",
    "Define a python function with signature `summation(x, method=\"kahan\")` and docstring \n",
    "  ```\n",
    "    Sum x using the indicated method\n",
    "    \n",
    "    x     : a list of numbers [x1 x2 ... xn] of length n\n",
    "    method: one of <\"sorted\"|\"fan\"|\"kahan\"> with default \"kahan\"\n",
    "  ``` \n",
    "\n",
    "  which returns the sum of `x` according to the requested method as follows:\n",
    "\n",
    "  - `\"sorted\"` assumes the numbers are sorted by increasing magnitude and adds them sequentially\n",
    "  - `\"fan\"` assumes an even count of numbers of roughly equal magnitude and adds them in the following pairwise manner\n",
    "\n",
    "    ```\n",
    "    def fan(x, minimum_list_length_for_recursion=2):\n",
    "        \"\"\"\n",
    "        <replace this docstring with a good explanation of this function>\n",
    "        <add explanatory clarifying comments into the function as needed>\n",
    "        \"\"\"\n",
    "        if len(x)<minimum_list_length_for_recursion:\n",
    "            return sum(x)\n",
    "        new_x = []\n",
    "        for j in range(int(len(x)/2)):\n",
    "            new_x += [x[j*2]+x[j*2+1]]\n",
    "        return fan(new_x, minimum_list_length_for_recursion)\n",
    "    ```\n",
    "\n",
    "  - `\"kahan\"` uses the order of the numbers as supplied and sums them acording to [Kahan's improved summation algorithm](https://en.wikipedia.org/wiki/Kahan_summation_algorithm) designed to sequentially minimize computer errors $\\big|\\sum_{i=1}^k x_i - \\left[\\sum_{i=1}^k x_i\\right]_c\\big|$ for *computer representation* $[\\cdot]_c$: \n",
    "\n",
    "    > $\\begin{align*}\n",
    "& {} s = x_1 & {} & \\texttt{ # sum so far}\\\\\n",
    "& {} a = 0 & {} & \\texttt{ # adjustment needed}\\\\\n",
    "& {} \\text{for } i = 2, ..., n \\\\\n",
    "& {} \\{ \\\\\n",
    "& {} \\quad y = x_i - a & {} \\\\\n",
    "& {} \\quad t = s + y & {} & \\texttt{ # total}\\\\\n",
    "& {} \\quad a = (t - s) - y & {} & \\texttt{ # adjustment needed}\\\\\n",
    "& {} \\quad s = t & {} & \\texttt{ # sum so far}\\\\\n",
    "& {} \\}\n",
    "\\end{align*}$\n",
    "\n",
    "*This problem is inspired by the **Addition of Several Numbers** section in Chapter 2.3 **Computer Storage and Arithmatic: Errors** following Chapter 2.2 **The Floating-Point Number System** on page 99 of James E. Gentle's **Computational Statistics** textbook.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c2a4a78f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sorted_sum(x):\n",
    "    \"\"\"\n",
    "    <replace this docstring with a good explanation of this function>\n",
    "    <add explanatory clarifying comments into the function as needed>\n",
    "    \"\"\"\n",
    "    \n",
    "    pass\n",
    "\n",
    "\n",
    "def fan(x, minimum_list_length_for_recursion=2):    \n",
    "    \"\"\"\n",
    "    <replace this docstring with a good explanation of this function>\n",
    "    <add explanatory clarifying comments into the function as needed>\n",
    "    \"\"\"\n",
    "    \n",
    "    pass\n",
    "\n",
    "\n",
    "def fahan(x):\n",
    "\n",
    "    \"\"\"\n",
    "    <replace this docstring with a good explanation of this function>\n",
    "    <add explanatory clarifying comments into the function as needed>\n",
    "    \"\"\"\n",
    "    \n",
    "    pass\n",
    "    \n",
    "    \n",
    "def summation(x, method=\"kahan\"):\n",
    "    \"\"\"\n",
    "    <replace this docstring with a good explanation of this function>\n",
    "    <add explanatory clarifying comments into the function as needed>\n",
    "    \"\"\"\n",
    "    \n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "526cbaf9",
   "metadata": {},
   "source": [
    "## Hints:\n",
    "\n",
    "- Any time the magnitudes of the smallest significant digits for two floating-point numbers differ, their sum cannot include smallest significant digits of the smaller magnitude floating-point number so it is subject to *roundoff error*.\n",
    "- Different summation algorithms accumulate *roundoff error* at different rates; but, the [most numerically accurate summation](https://stackoverflow.com/questions/33004029/is-numpy-sum-implemented-in-such-a-way-that-numerical-errors-are-avoided) can be verified with\n",
    "\n",
    "  ```\n",
    "  import math\n",
    "  ... # create list of numbers x\n",
    "  math.fsum(x) # as opposed to `np.sum(x)`\n",
    "  ```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fadbbc6",
   "metadata": {},
   "source": [
    "### Problem 3 Questions 1-4 (2 points)\n",
    "\n",
    "What are the results of the following function calls?\n",
    "\n",
    "- `summation([1e16]+10*[1e0], method=\"sorted\")`\n",
    "- `summation(10*[1e0]+[1e16], method=\"sorted\")`\n",
    "- `summation([1e15]+10*[1e0], method=\"sorted\")`\n",
    "- `summation(10*[1e0]+[1e15], method=\"sorted\")`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7215d509",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 2 points\n",
    "p3q1 = #summation([1e16]+10*[1e0], method=\"sorted\")\n",
    "p3q2 = #summation(10*[1e0]+[1e16], method=\"sorted\")\n",
    "p3q3 = #summation([1e15]+10*[1e0], method=\"sorted\")\n",
    "p3q4 = #summation(10*[1e0]+[1e15], method=\"sorted\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7ed0c68",
   "metadata": {},
   "source": [
    "### Problem 3 Questions 5-7 (5 points)\n",
    "\n",
    "The function calls \n",
    "\n",
    "- `summation(list(sorted(x, key=lambda x: np.abs(x))), method=\"sorted\")` (1 point)\n",
    "- `summation(list(x), method=\"fan\")` (2 points)\n",
    "- `summation(x, method=\"fahan\")` (2 points)\n",
    "\n",
    "will be tested with\n",
    "\n",
    "```\n",
    "from scipy import stats\n",
    "np.random.seed(seed)\n",
    "n = 2**20\n",
    "x = stats.norm().rvs(size=n)\n",
    "```\n",
    "  \n",
    "for some choice of `seed`.\n",
    "\n",
    "***No variable assignments are required: the function and methods will be tested directly.***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4302889d",
   "metadata": {},
   "source": [
    "# Problem 4 (6 points)\n",
    "\n",
    "Define a function with signature `singlepassSS(x, formula)` and docstring \n",
    "  ```\n",
    "    Calculate the sum of squares of x \n",
    "    according to the specified formula\n",
    "    \n",
    "    x      : a numpy array of numbers of length n np.array([x1, x2, ... xn,]) \n",
    "    formula: one of <\"online\"|\"realtime\"|\"recursive\"> \n",
    "  ``` \n",
    "\n",
    "  which computes the *sum of squares* with the following $O(n)$ complexity algorithms:\n",
    "  \n",
    "  - `\"online\"` and `\"realtime\"` use *online* (multiple pass \"out of core\") and *real-time* (single pass) computations, respectively, i.e.,\n",
    "  \n",
    "  $$\\underset{\\text{first computes } \\bar x}{\\underbrace{\\sum_{i=1}^n(x_i-\\bar x)^2}_{\\text{two pass algorithm}}} = \\sum_{i=1}^n x_i^2 - n \\bar x^2 = \\underset{\\text{$\\sum_{i=1}^{k-1 \\rightarrow k} x_i^2$ and $\\sum_{i=1}^{k-1\\rightarrow k} x_i$ at step $k$}}{\\underbrace{\\sum_{i=1}^n x_i^2 - \\frac{1}{n} \\left(\\sum_{i=1}^n x_i\\right)^2}_{\\text{single pass algorithm increments}}}$$\n",
    "\n",
    "  - `\"recursive\"` computes the alternative (generally more accurate) algorithm\n",
    "\n",
    "    > \\begin{align*}\n",
    "& {} a = x_1 & {} & \\texttt{ # mean so far}\\\\\n",
    "& {} b = 0 & {} & \\texttt{ # variance so far}\\\\\n",
    "& {} \\text{for } i = 2, ..., n \\\\\n",
    "& {} \\{ \\\\\n",
    "& {} \\quad d = (x_i - a)/i & {} & \\texttt{ # new deviation from current mean per sample} \\\\\n",
    "& {} \\quad a = d + a & {} & \\texttt{ # weigted average mean update}\\\\\n",
    "& {} \\quad b = i(i - 1)d^2+ b & {} & \\texttt{ # cumulative variance update}\\\\\n",
    "& {} \\} \\end{align*}\n",
    "\n",
    "    where the $\\texttt{\"cumulative variance update\"}$ results from the `recursive` formula suggested by the first full paragraph on page 120 of James E. Gentle's **Computational Statistics** textbook (and derived [here](https://math.stackexchange.com/questions/374881/recursive-formula-for-variance)).\n",
    "\n",
    "*This problem is inspired by the discussion about **Reducing the Error in Numerical Computations** in Chapter 3.2 **Algorithms and Data** on pages 114-116, **Computations without Storing Data** in Chapter 3.5 **Programming** on page 135, and **Recursion** on page 119-121 in Chapter 3.3 **Efficiency** of James E. Gentle's **Computational Statistics** textbook.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a9b4709",
   "metadata": {},
   "source": [
    "## Hints\n",
    "\n",
    "Depending on the data, the different implementations will disagree to varying degrees.\n",
    "\n",
    "- Using \n",
    "\n",
    "  ```\n",
    "  # https://numpy.org/doc/stable/reference/generated/numpy.var.html\n",
    "  np.var(x, ddof=0)*n\n",
    "  ```\n",
    "\n",
    "  these differences can be benchmarked."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bfeff164",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Complete the `singlepassSS` function as specified in the problem prompt.\n",
    "def singlepassSS(x, formula):\n",
    "    \"\"\"\n",
    "    Calculate the sum of squares of x\n",
    "    according to the specified formula\n",
    "    \n",
    "    x      : a numpy array of numbers of length n np.array([x1, x2, ... xn,])\n",
    "    formula: one of <\"online_formula\"|\"realtime_formula\"|\"recursive\">\n",
    "    \"\"\"\n",
    "    \n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "828df001",
   "metadata": {},
   "source": [
    "### Problem 4 Questions 1-5 (5 points)\n",
    "\n",
    "The `singlepassSS` function will be run with data generated as \n",
    "\n",
    "```\n",
    "n = 100\n",
    "np.random.seed(seed)\n",
    "x = stats.norm(scale=std).rvs(size=n)\n",
    "\n",
    "```\n",
    "  \n",
    "for various choices of `seed` and `std`.\n",
    "\n",
    "***No variable assignments are required: the functions will be tested directly.***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6afc213",
   "metadata": {},
   "source": [
    "### Problem 4 Question 6 (1 point)\n",
    "\n",
    "Is `singlepassvar(x, formula=\"recursive\")` (\"Yes\" or \"No\") always closer to `np.var(x, ddof=0)*n` than the other `online` and `realtime` methods?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ebb40e0e",
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# 1 point\n",
    "p4q6 = #<\"Yes\"|\"No\">"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit Metadata",
  "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}