\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
    \makeatletter % undo the wrong changes made by mathspec
    \let\RequirePackage\original@RequirePackage
    \let\usepackage\RequirePackage
    \makeatother
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{hyperref}
\hypersetup{unicode=true,
            pdftitle={Homework 1},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

\title{Homework 1}

\input{preamble.tex}
\title{Homework}



\begin{document}
\maketitle

Please answer the following questions in complete sentences in a typed
manuscript and submit the solution on Gradescope by Feb 7 / Feb 8th
(5am).

\hypertarget{problem-0-homework-checklist}{%
\subsection{Problem 0: Homework
checklist}\label{problem-0-homework-checklist}}

\begin{itemize}
\item
  Please identify anyone, whether or not they are in the class, with
  whom you discussed your homework. This problem is worth 1 point, but
  on a multiplicative scale.
\item
  Make sure you have included your source-code and prepared your
  solution according to the most recent Piazza note on homework
  submissions.
\end{itemize}

\hypertarget{problem-1-gautschi-exercise-1.1}{%
\subsection{Problem 1: Gautschi Exercise
1.1}\label{problem-1-gautschi-exercise-1.1}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Enumerate all positive elements of \(\RR(3,2)\) that correspond to
  normalized floating point values. (Recall that \(\RR(3,2)\) is a
  floating point system that uses 2-bits for the exponent and 3-bits for
  the significand or mantissa.) List each number on one line as a
  decimal.
\item
  What is the distance \(d(x)\) of a positive normalized floating point
  number to its next larger floating-point number? (Do this for all
  values in \(\RR(3,2)\).)
\item
  Determine the relative distance \(r(x) = d(x)/x\) for all numbers and
  give upper and lower bounds.
\end{enumerate}

\hypertarget{problem-2-gautschi-exercise-1.11}{%
\subsection{Problem 2: Gautschi Exercise
1.11}\label{problem-2-gautschi-exercise-1.11}}

Let \(f(x) = \sqrt{1 + x^2} - 1\).

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Explain the difficulty of computing \(f(x)\) for a small value of
  \(|x|\) and show how it can be circumvented.
\item
  Determine an expression for the condition number of \(f(x)\) and
  discuss conditioning for small \(|x|\).
\item
  How can the answers to 1 and 2 be reconciled?
\end{enumerate}

\hypertarget{problem-3-gautschi-machine-exercise-1.4}{%
\subsection{Problem 3: Gautschi Machine Exercise
1.4}\label{problem-3-gautschi-machine-exercise-1.4}}

Euler's constant \(\gamma = 0.57721566490153286\ldots\) is defined as
the limit
\[ \gamma = \lim_{n\to\infty} \gamma_n \text{ where } \gamma_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} - \log(n). \]
Assuming that \(\gamma - \gamma_n \sim c n^{-d}\), try to determine
\(c\) and \(d\) on the computer.

\hypertarget{problem-4-gautschi-machine-exercise-1.6a.}{%
\subsection{Problem 4: Gautschi Machine Exercise
1.6a.}\label{problem-4-gautschi-machine-exercise-1.6a.}}

Write a program to compute
\[ S_N = \sum_{n=1}^N (\frac{1}{n} - \frac{1}{n+1}) = \sum_{n=1}^N \frac{1}{n(n+1)} \]
once using the first formula and once using the second formula. For
\(N = 10^k, k = 1, 2, \ldots, 7\), print the respective absolute errors.
Comment on the results.

\hypertarget{problem-5-the-hurwitz-zeta-function}{%
\subsection{Problem 5: The Hurwitz zeta
function}\label{problem-5-the-hurwitz-zeta-function}}

\textbf{This is a \emph{real} problem that I ran into!} I was using a
program written by someone else to compute a particular statistical
estimate. The details don't really matter, but at one step, the code
needed to compute the Hurwitz zeta function:
\[ H(s,q) = \sum_{n=0}^\infty  \frac{1}{(q+n)^s} \] where \(s\) ranged
from 1 to 7 and where \(q\) ranged from 1 to 500. They were using
Matlab, which doesn't provide a function for the Hurtwitz zeta function,
but does provide a function for the Riemann zeta function:
\[ R(s) = \sum_{n=1}^\infty \frac{1}{n^s}. \] Note that the only
difference between these two functions is that the first term in the
Riemann zeta function is \(1/(1^s)\) and the first term in the Hurwitz
zeta function is \(1/(q^s)\). To account for this difference, the code I
was using did the following:

\begin{verbatim}
 function h=hzeta(s,q)
 z = zeta(s)
 h = z - sum((1:(q-1)).^(-s));
\end{verbatim}

Was I happy when I realized this? You should use what you've learned
about floating point computations to answer this question.
\href{http://www.wolframalpha.com/input/?i=Hurwitz+Zeta\%282\%2C5\%29\%3E}{You
can evaluate the Hurwitz zeta function to arbitrary precision via
Wolfram Alpha}.

\hypertarget{problem-6}{%
\subsection{Problem 6}\label{problem-6}}

Suppose you want to evaluate \(a + b + c\) on a machine. Suppose that
\(a > b > c > 0\) and that \(a,b,c\) are all exact on the machine.
Empirically illustrate that
\[ \text{fl}(\text{fl}(a + b) + c)  \not= \text{fl}(a + \text{fl}(b + c)). \]
Now prove which of the three orders of evaluation result in the smallest
error. (The three are (a+b)+c, (a+c)+b, a+(b+c).)

\hypertarget{problem-7}{%
\subsection{Problem 7}\label{problem-7}}

The Intel Penitum FDIV bug was illustrated with the procedure:
\[ A - \frac{A}{B} B. \] Determine the accuracy of this computation
assuming that \(A\) and \(B\) can be exactly stored in floating point on
the computer.

\hypertarget{problem-8}{%
\subsection{Problem 8}\label{problem-8}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  We want to understand computer implementations of methods to compute
  the roots of the quadratic equation given the coefficients \(a,b,c\)
  in \[ ax^2 + bx + c = 0 \] using the high school formula
  \[ x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}. \] Show empirically that
  this formula can result in catastrophic errors in the computed roots
  and identify the cause.
\item
  Consider Gautschi's suggestion in problem 9. Suppose we take (without
  loss of generality) the quadratic \[ x^2 + px + q = 0 \] with roots
  \(x_1, x_2\). Suppose we compute the larger root first, and then use
  \(x_1 x_2 = q\) to determine the additional root. This results in the
  Julia program:

\begin{verbatim}
 x1=abs(p/2) + sqrt(p*p/4 - q)
 if p > 0
     x1 = -x1
 end
 x2 = q/x1
\end{verbatim}

  Find two serious flaws with this program as a ``general-purpose''
  quadratic equation solver. Support your arguments with specific
  examples, if necessary.
\item
  Consider reading Kahan's note on quadratics for more on how to
  accurately evaluate them.
  \url{https://www.cs.berkeley.edu/~wkahan/Qdrtcs.pdf}
\end{enumerate}

\end{document}
