Due Date: Wendesday January 21, 9pm

Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html

Please hand in 2 files:

- Python File containing all your code, named
`hw2.py`

. - 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
```

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
PRECISION = 5
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)
```

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
```

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)
True
"""
(mantissa, exponent, sign) = float_value
return None
```

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

of
each of the following:

- The largest negative number representable in our floating point system. Store it in the variable
`largest_negative`

. - The smallest positive number (greater than 0) in our floating point system. Store it in the variable
`smallest_positive`

- 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)
```

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)
3.111111111111111
"""
(mantissa, exponent, sign) = float_value
return None
```

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)
```

Show that `add_float(x,y)`

is not associative. Include this part of your work in your PDF file.

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)]
```

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.

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 = []
```

In [10]:

```
def z(n):
a = pow(2.0, n) + 10.0
b = (pow(2.0, n) + 5.0) + 5.0
return a - b
```

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 = []
```

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.