{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# CSC338. Homework 2\n", "\n", "Due Date: Wendesday January 21, 9pm\n", "\n", "Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html\n", "\n", "### What to Hand In\n", "\n", "Please hand in 2 files:\n", "\n", "- Python File containing all your code, named `hw2.py`.\n", "- PDF file named `hw2_written.pdf` containing your solutions to the written parts of the assignment. Your solution can be hand-written, but must be legible. Graders may deduct marks for illegible or poorly presented solutions.\n", "\n", "If you are using Jupyter Notebook to complete the work, your notebook can be exported as a .py file (File -> Download As -> Python). Your code will be auto-graded using Python 3.6, so please make sure that your code runs. There will be a 20% penalty if you need a remark due to small issues that renders your code untestable.\n", "\n", "**Make sure to remove or comment out all matplotlib or other expensive code before submitting your code!**\n", "\n", "Submit the assignment on **MarkUs** by 9pm on the due date. See the syllabus for the course policy regarding late assignments. All assignments must be done individually." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import math\n", "import numpy as np" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1\n", "\n", "We'll be implementing a floating point system.\n", "For most of this question, assume that we are working with:\n", "\n", "* base $\\beta$ = 3, \n", "* precision $p$ = 5, and \n", "* exponent range [$L$, $U$] = [-3, 3]\n", "\n", "Our floating point system will be normalized." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# These are the constants we'll use in our code\n", "BASE = 3\n", "PRECISION = 5\n", "L = -3\n", "U = +3\n", "\n", "# We will represent a floating number as a tuple (mantissa, exponent, sign)\n", "# With: mantissa -- a list of integers of length PRECISION\n", "# exponent -- an integer between L and U (inclusive)\n", "# sign -- either 1 or -1\n", "example_float = ([1, 0, 0, 1, 0], 1, 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a) -- 1pt\n", "\n", "How many normalized-point numbers are in our system? Use a formula in terms of `BASE`, \n", "`PRECISION`, `L` and `U` to compute the count, and save the result in the value `total_num_floats`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "total_num_floats = None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b) -- 3pt\n", "\n", "Write a function `is_valid_float` that checks whether a tuple of the form `(mantissa, exponent, sign)`\n", "represents a valid, normalized float in our floating point system." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def is_valid_float(float_value):\n", " \"\"\"Returns a boolean representing whether the float_value is a valid,\n", " normalized float in our floating point system.\n", "\n", " >>> is_valid_float(example_float)\n", " True\n", " \"\"\"\n", "\n", " (mantissa, exponent, sign) = float_value\n", " return None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (c) -- 3pt\n", "\n", "Construct a floating-point representation tuple of the form `(mantissa, exponent, sign)` of \n", "each of the following:\n", "\n", "1. The largest negative number representable in our floating point system. Store it in the variable `largest_negative`.\n", "2. The smallest positive number (greater than 0) in our floating point system. Store it in the variable `smallest_positive`\n", "3. The value of `32` represented in our floating system. Assume chopping is used for rounding. Store it in the variable `float_32`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "largest_negative = ([], None, None)\n", "smallest_positive = ([], None, None)\n", "float_32 = ([], None, None)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (d) -- 5pt\n", "\n", "Write a function `to_num` that converts a tuple of the form `(mantissa, exponent, sign)`\n", "to a Python numerical value." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def to_num(float_value):\n", " \"\"\"Return a Python floating point representation of `float_val`\n", " These examples are for your understanding, and your actual output\n", " might vary slightly.\n", " \n", " >>> to_num(example_float)\n", " 3.111111111111111\n", " \"\"\"\n", " (mantissa, exponent, sign) = float_value\n", " return None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (e) -- 5pt\n", "\n", "Write a function `add` that takes two tuples of the form `(mantissa, exponent, sign)`,\n", "and performs floating-point addition to obtain a third floating-point number in our\n", "representation `(mantissa, exponent, sign)`.\n", "\n", "You may assume that the signs of both addends are positive." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def add_float(float1, float2):\n", " \"\"\"Return a valid floating-point representation of the form (mantissa, exponent, sign)\n", " that is the sum of `float1` and `float2`. Raises a ValueError if the result of\n", " the addition is not a valid float.\n", " \n", " >>> add_float(example_float, example_float)\n", " ([2, 0, 0, 2, 0], 1, 1])\n", " \"\"\"\n", " (mantissa1, exponent1, sign1) = float1\n", " (mantissa2, exponent2, sign2) = float2\n", "\n", " # You may assume that sign1 and sign2 are positive\n", " assert (sign1 == 1) and (sign2 == 1)\n", "\n", " # Add your code here\n", " return (None, None, None)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (f) -- 2pt\n", "\n", "Show that `add_float(x,y)` is not associative. Include this part of your work in your PDF file.\n", "\n", "## Question 2\n", "\n", "We are going to show catestrophic cancellation by computing $\\frac{1}{1-x}$ and $e^x$ using their taylor series expansion. Recall that:\n", "\n", "$\\frac{1}{1-x} = 1 + x + x^2 + x^3 + ... = \\sum_{n=0}^\\infty x^n$ for $x \\in (-1, 1)$, and\n", "\n", "$e^x = 1 + x + \\frac{x^2}{2!} + \\frac{x^3}{3!} + ... = \\sum_{n=0}^\\infty \\frac{x^n}{n!}$\n", "\n", "The functions `h1` and `h2` returns a list of the first $n$ elements of the Taylor series expansions of\n", "$\\frac{1}{1-x}$ and $e^x$, respectively." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def h1(x, n):\n", " \"\"\"Returns a list of the first n terms of the Taylor Series expansion of 1/(1-x).\"\"\"\n", " return [pow(x,i) for i in range(n)]\n", "\n", "def h2(x, n):\n", " \"\"\"Returns a list of the first n terms of the Taylor Series expansion of e^x.\"\"\"\n", " return [pow(x,i)/math.factorial(i) for i in range(n)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a) -- 3pt\n", "\n", "Does computing $\\frac{1}{1-x}$ using `sum(h1(x,n))` suffer from catestrophic cancellation? \n", "If so, show an example: choose an $x$ where catestrophic cancellation occurs and \n", "show the list $h1(x,n)$. If not, briefly explain why not.\n", "\n", "Include your solution in the PDF writeup.\n", "\n", "### Part (b) -- 1pt\n", "\n", "We already showed in class that computing $e^x$ in this way gives \n", "disasterous results for x < 0. For the rest of this part of the assignment,\n", "set $x = -30$.\n", "\n", "First, compute $e^x$ using `math.exp`.\n", "\n", "Now, compute the estimate: `h2(-30, n)` for `n = 20, 40, 60, 80, 100, 120, 140, 160`.\n", "\n", "Save the result as a list, in order of ascending values of $n$, \n", "in the variable `exp_estimates`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ns = [20, 40, 60, 80, 100, 120, 140, 160]\n", "exp_estimates = []" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (c) -- 2pt\n", "\n", "Describe the values of `exp_estimates`. What does the first 4 values look like, and why?\n", "Do the estimates eventually converge? Why or why not? \n", "\n", "Include your solution in the PDF writeup.\n", "\n", "## Question 3\n", "\n", "Consider the function $z(n)$ below:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def z(n):\n", " a = pow(2.0, n) + 10.0\n", " b = (pow(2.0, n) + 5.0) + 5.0\n", " return a - b" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a) -- 1pt\n", "\n", "Using Python, find all positive integers `n` for which the value of `z(n)` is nonzero.\n", "Save the result in a list called `nonzero_zn`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nonzero_zn = []" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b) -- 4pt\n", "\n", "\n", "Using what we learned about floating-point addition and the rounding rules, explain why\n", "the `z(n)` takes on these particular non-zero values. Why is the expression zero\n", "for all other values of n? You may assume that Python uses IEEE Double Precision\n", "for floating-point arithmetic (i.e., round to even in base 2 with a mantissa of 53 bits).\n", "Hint: look at the rounding error produced by each of the three additions." ] } ], "metadata": {}, "nbformat": 4, "nbformat_minor": 2 }