Spring 2018, CMPSC/MATH 451
Homework Assignment #1
Due 11.59 pm, February 8 on Canvas
Last updated February 7 with hints and corrections (problem 3 pseudocode).
1
Let x be a given nonzero oating-point number in a normalized system, and let y be an adjacent
oating-point number, also non-zero. What is the minimum possible spacing between x and y?
What is the maximum possible spacing between x and y? How are these results a ected by the
rounding rule used? Hint: Note that x and y are two adjacent positive numbers. For instance, in
a normalized oating-point system with base 10, precision 4, L = 3, and U = 10, 2.151 and 2.152
are adjacent numbers. You need to give a general expression for the minimum/maximum possible
spacing in terms of , p, L, and U.
(6 points)
2
Suppose a machine with a oating-point system ( ;p;L;U) = (10;6; 30;20) is used to calculate
the roots of the quadratic equation ax2 +bx+c = 0, where a, b, and c are given, real coe cients.
For each of the following cases, state the numerical di culties that arise if one uses the standard
formula for computing the roots. Explain how one can overcome these di culties (when possible):
a = 105;b = 1012;c = 106
a = 10;b = 104;c = 1
a = 2;b = 8;c = 8:00001
(9 points)
3
Prepare a MATLAB/Octave script. that sums n random, single-precision oating-point numbers xi,
uniformly distributed in the interval [0;1]. Sum the numbers in each of the following ways (using
single-precision variables unless speci cally indicated otherwise):
(a) Sum the numbers in the order in which they were generated, using a double-precision variable
to accumulate the sum. Use a loop to do the summation and not the builtin function.
(b) Sum the numbers in the order in which they were generated, this time using a single-precision
accumulator. Use a loop to do the summation and not the builtin function.
(c) Use the following compensated summation algorithm, again using only single precision, to sum
the numbers in the order in which they were generated:
s = 0
c = 0
for i = 1 to n do
1
y = xi c
t = s+y
c = (t s) y
s = t
end for
(d) Sum the numbers in order of increasing magnitude (using the builtin sort function). Use a
loop to do the summation (after sorting the numbers) and not the builtin function.
(e) Sum the numbers in decreasing magnitude (reversing the order obtained in the previous part).
Use a loop to do the summation and not the builtin function.
Once you check for correctness, extend the previous program to answer the following:
(i) Experiment with di erent values of n and chart your results. Note that you may need to use
fairly large values of n to see substantial di erences.
(ii) How do the methods rank in terms of accuracy, and why? You can use the result of the
builtin function sum as the true value. Do not use the builtin function for
(iii) How do the methods compare in cost? Time the routines for a large n and provide a com-
parison.
(iv) Brie y explain how/why the compensated summation algorithm works.
(25 points)
13 points for code + 12 points for responses to the four questions 4
Chapter 3, exercise 1 (pages 58 and 59).
(10 points)