CSC338. Homework 2

Due Date: Wendesday January 21, 9pm

Please see the guidelines at

What to Hand In

Please hand in 2 files:

  • Python File containing all your code, named
  • 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.

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.

Make sure to remove or comment out all matplotlib or other expensive code before submitting your code!

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.

In [1]:
import math
import numpy as np

Question 1

We'll be implementing a floating point system. For most of this question, assume that we are working with:

  • base $\beta$ = 3,
  • precision $p$ = 5, and
  • exponent range [$L$, $U$] = [-3, 3]

Our floating point system will be normalized.

In [2]:
# These are the constants we'll use in our code
BASE = 3
L = -3
U = +3

# We will represent a floating number as a tuple (mantissa, exponent, sign)
# With: mantissa -- a list of integers of length PRECISION
#       exponent -- an integer between L and U (inclusive)
#       sign     -- either 1 or -1
example_float = ([1, 0, 0, 1, 0], 1, 1)

Part (a) -- 1pt

How many normalized-point numbers are in our system? Use a formula in terms of BASE, PRECISION, L and U to compute the count, and save the result in the value total_num_floats.

In [3]:
total_num_floats = None

Part (b) -- 3pt

Write a function is_valid_float that checks whether a tuple of the form (mantissa, exponent, sign) represents a valid, normalized float in our floating point system.

In [4]:
def is_valid_float(float_value):
    """Returns a boolean representing whether the float_value is a valid,
    normalized float in our floating point system.

    >>> is_valid_float(example_float)

    (mantissa, exponent, sign) = float_value
    return None

Part (c) -- 3pt

Construct a floating-point representation tuple of the form (mantissa, exponent, sign) of each of the following:

  1. The largest negative number representable in our floating point system. Store it in the variable largest_negative.
  2. The smallest positive number (greater than 0) in our floating point system. Store it in the variable smallest_positive
  3. The value of 32 represented in our floating system. Assume chopping is used for rounding. Store it in the variable float_32.
In [5]:
largest_negative = ([], None, None)
smallest_positive = ([], None, None)
float_32 = ([], None, None)

Part (d) -- 5pt

Write a function to_num that converts a tuple of the form (mantissa, exponent, sign) to a Python numerical value.

In [6]:
def to_num(float_value):
    """Return a Python floating point representation of `float_val`
    These examples are for your understanding, and your actual output
    might vary slightly.
    >>> to_num(example_float)
    (mantissa, exponent, sign) = float_value
    return None

Part (e) -- 5pt

Write a function add that takes two tuples of the form (mantissa, exponent, sign), and performs floating-point addition to obtain a third floating-point number in our representation (mantissa, exponent, sign).

You may assume that the signs of both addends are positive.

In [7]:
def add_float(float1, float2):
    """Return a valid floating-point representation of the form (mantissa, exponent, sign)
    that is the sum of `float1` and `float2`. Raises a ValueError if the result of
    the addition is not a valid float.
    >>> add_float(example_float, example_float)
    ([2, 0, 0, 2, 0], 1, 1])
    (mantissa1, exponent1, sign1) = float1
    (mantissa2, exponent2, sign2) = float2

    # You may assume that sign1 and sign2 are positive
    assert (sign1 == 1) and (sign2 == 1)

    # Add your code here
    return (None, None, None)

Part (f) -- 2pt

Show that add_float(x,y) is not associative. Include this part of your work in your PDF file.

Question 2

We are going to show catestrophic cancellation by computing $\frac{1}{1-x}$ and $e^x$ using their taylor series expansion. Recall that:

$\frac{1}{1-x} = 1 + x + x^2 + x^3 + ... = \sum_{n=0}^\infty x^n$ for $x \in (-1, 1)$, and

$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... = \sum_{n=0}^\infty \frac{x^n}{n!}$

The functions h1 and h2 returns a list of the first $n$ elements of the Taylor series expansions of $\frac{1}{1-x}$ and $e^x$, respectively.

In [8]:
def h1(x, n):
    """Returns a list of the first n terms of the Taylor Series expansion of 1/(1-x)."""
    return [pow(x,i) for i in range(n)]

def h2(x, n):
    """Returns a list of the first n terms of the Taylor Series expansion of e^x."""
    return [pow(x,i)/math.factorial(i) for i in range(n)]

Part (a) -- 3pt

Does computing $\frac{1}{1-x}$ using sum(h1(x,n)) suffer from catestrophic cancellation? If so, show an example: choose an $x$ where catestrophic cancellation occurs and show the list $h1(x,n)$. If not, briefly explain why not.

Include your solution in the PDF writeup.

Part (b) -- 1pt

We already showed in class that computing $e^x$ in this way gives disasterous results for x < 0. For the rest of this part of the assignment, set $x = -30$.

First, compute $e^x$ using math.exp.

Now, compute the estimate: h2(-30, n) for n = 20, 40, 60, 80, 100, 120, 140, 160.

Save the result as a list, in order of ascending values of $n$, in the variable exp_estimates.

In [9]:
ns = [20, 40, 60, 80, 100, 120, 140, 160]
exp_estimates = []

Part (c) -- 2pt

Describe the values of exp_estimates. What does the first 4 values look like, and why? Do the estimates eventually converge? Why or why not?

Include your solution in the PDF writeup.

Question 3

Consider the function $z(n)$ below:

In [10]:
def z(n):
    a = pow(2.0, n) + 10.0
    b = (pow(2.0, n) + 5.0) + 5.0
    return a - b

Part (a) -- 1pt

Using Python, find all positive integers n for which the value of z(n) is nonzero. Save the result in a list called nonzero_zn.

In [11]:
nonzero_zn = []

Part (b) -- 4pt

Using what we learned about floating-point addition and the rounding rules, explain why the z(n) takes on these particular non-zero values. Why is the expression zero for all other values of n? You may assume that Python uses IEEE Double Precision for floating-point arithmetic (i.e., round to even in base 2 with a mantissa of 53 bits). Hint: look at the rounding error produced by each of the three additions.