Numerical Analysis I, Fall 2020 (http://www.math.nthu.edu.tw/˜ wangwc/)

Brief Solution to Quiz 01

Sep 29, 2020.

1. How many bits does it take to store a binary floating point number of the form ±1.a_{1}a_{2} ⋯ a_{t} × 2^{e} with t = 10, a_{j} ∈ {0, 1}, −14 ≤ e ≤ 15? What is the distance from 1.0 to the the nearest (typo: should have been ’next larger’) floating number? Explain.

Ans:

There are total 30 different exponents (−14 ≤ e ≤ 15). It takes 5 bits to give 30 or more different exponents (2^{5} = 32). Total bits = 1 + 10 + 5 = 16 (10 pts).

The range of the 5-bit binary exponent c = (b_{1}b_{2}b_{3}b_{4}b_{5})_{2}, b_{i} = 0, 1, is 0 ≤ c ≤ 31. In order to cover the range −14 ≤ e ≤ 15, one should take e = c − 15, so that e = −15 and e = 16 can be reserved for underflow and overflow, respectively. With e = c − 15, the binary machine number of 1.0 is given by:

1.0 = +(1.0)_{2} × 2^{0} = 0 01111 0000000000

The next larger floating point number is 0 01111 0000000001. The difference from 1.0 is 2^{−10} (10 pts).

The next smaller floating point number is 0 01110 1111111111, or

(1.11 ⋯ 1)_{2} × 2^{−1} = 2^{−1} (1 + 2^{−1} + 2^{−2} + ⋯ + 2^{−10}) = 2^{−1} (2 − 2^{−10}) = 1 − 2^{−11}

The difference from 1.0 is 2^{−11}

The distance from 1.0 to nearest floating point number is min(2^{−10}, 2^{−11}) = 2^{−11} (Extra 10 pts).

2. Suppose that if fl(y) is a k-digit rounding approximation to y. Show that

|\frac{y − fl(y)}{y}| ≤ 5 × 10^{−k}

Remark: A k-digit rounding means, given y = ±0.d_{1}d_{2} ⋯ d_{k}d_{k+1} ⋯ × 10^{n}, 0 ≤ d_{i} ≤ 9, d_{1} > 0, then fl(y) is obtained by changing d_{k} to d̃_{k} according to the value of d_{k+1}.

Ans: If k-digit rounding arithmetic is used and

• If d_{k+1} ≤ 4, then fl(y) = ±0.d_{1}d_{2} ⋯ d_{k} × 10^{n}.

\frac{|y − fl(y)|}{|y|} = \frac{|0.00 ⋯ 0d_{k+1}d_{k+2} ⋯ |}{|0.d_{1}d_{2} ⋯ d_{k}d_{k+1}d_{k+2} ⋯ |}

≤ \frac{|0.00 ⋯ 04999 ⋯ |}{|0.10 ⋯ 04999 ⋯ |} = \frac{|4.999 ⋯ |}{|10 ⋯ 04.999 ⋯ |} ≤ \frac{|4.999 ⋯ |}{|10 ⋯ 00.000 ⋯ |} ≤ 5 × 10^{−k}.

• If d_{k+1} ≥ 5, then fl(y) = ±(0.d_{1}d_{2} ⋯ (d_{k} + 1)) × 10^{n}.

\frac{|y − fl(y)|}{|y|} = \frac{|0.00 ⋯ 100 ⋯ − 0.00 ⋯ 0d_{k+1}d_{k+2} ⋯ |}{|0.d_{1}d_{2} ⋯ d_{k}d_{k+1}d_{k+2} ⋯ |} = \frac{|1.00 ⋯ − 0.d_{k+1}d_{k+2} ⋯ |}{|0.d_{1}d_{2} ⋯ d_{k}d_{k+1}d_{k+2} ⋯ |}×10^{−k}

≤ \frac{|1.00 ⋯ − 0.500 ⋯ |}{|0.10 ⋯ 050 ⋯ |} × 10^{−k} ≤ \frac{|1.00 ⋯ − 0.500 ⋯ |}{|0.10 ⋯ 000 ⋯ |} × 10^{−k} = 5 × 10^{−k}

(20 pts)

3. We showed in class the estimate of relative error resulted from x × y in terms of ε_{M}. Derive the corresponding result for x ÷ y, y ≠ 0.

Ans:

\frac{|x ÷ y − fl(fl(x) ÷ fl(y))|}{|x ÷ y|} = |\frac{x ÷ y − (x(1 + δ_{1}) ÷ y(1 + δ_{2}))(1 + δ_{3})}{x ÷ y}|

= |\frac{x ÷ y − (x ÷ y)\frac{(1+δ_{1})}{(1+δ_{2})}(1 + δ_{3})}{x ÷ y}|
= |1 − (1 + δ_{1} − δ_{2} + δ_{3} + O(δ^{2}))|
≈ |1 − (1 + δ_{1} − δ_{2} + δ_{3}))|
≤ |δ_{1}| + |δ_{2}| + |δ_{3}| ≤ 3ϵ_{M} (20 pts)

4. Solve for x^{2} − 2100x + 1 = 0 to 15 correct digits using standard double precision arithmetic. Explain how you find your answer (No explanation, no points).

Ans: x_{1} = \frac{2100+\sqrt{2100^{2}−4}}{2} = 2.09999952380942e + 03 (6 pts) x_{2} = 1/x_{1} or \frac{2}{2100+\sqrt{2100^{2}−4}} = 4.76190584170225e − 04 (14 pts)

5. Let A = {(x − 100)^{2} + y^{2} < (40π)^{2}}, and B = {x + y > 50.1}. Find the number of grid points (i, j) (i, j are integers) in A ∩ B. Write down the answer and name your code by your student ID number.

Ans: The number of grid points in A ∩ B is 33475 (20 pts).