# coding: utf-8

# # CSC338. Homework 2
# 
# Due Date: January 21, 8:59pm
# 
# Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html
# 
# ### What to Hand In
# 
# Please hand in 2 files:
# 
# - Python File containing all your code, named `csc338_hw2.py`.
# - PDF file named `csc338_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[ ]:


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[ ]:


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


# ### 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[ ]:


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[ ]:


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


# ### 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[ ]:


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[ ]:


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.
    
    >>> float_val(example_float)
    3.111111111111111
    """
    (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[ ]:


def add_float(float1, float2):
    """Return a floating-point representation of the form (mantissa, exponent, sign)
    that is the sum of `float1` and `float2`.
    
    >>> add_float(example_float, example_float)
    ([1, 0, 0, 1, 0], 2, 1])
    """
    (mantissa1, exponent1, sign1) = float_value1
    (mantissa2, exponent2, sign2) = float_value2

    # You may assume that sign1 and sign2 are positive
    assert (sign1 > 0) and (sign2 > 0)

    # 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[ ]:


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[ ]:


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[ ]:


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[ ]:


nonzero_zn = []


# ### Part (b) -- 4pt
# 
# Using the 4 rounding rules described in Section 1.3.4 of Heath, 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.