Fall Semester 2000
Some help directly related to this homework set is available in the form of example C++ programs. If you are first starting out, you may wish to take a few minutes to copy programs ~p5720/examples/*.cc to your home directory, compile them, then run them. Look at the source code, experiment with it if something is unclear.
Give yourself extra time on this one if you have had little programming experience. If you find yourself without any idea how to proceed, or if your code is broken and you can't fix it, please contact the instructor or the TA.
This exercise is intended to demonstrate the "imperfections" in digital representations of real numbers.
Write a C++ program called quadroots.cc which solves the quadratic equation ax^2 + bx + c = 0. Start off with the standard formula
x1 = (-b + q)/2a, with q = sqrt(b^2 - 4ac)
- and -
x2 = (-b - q)/2a.
Work with single-precision float variables x and q.
Note that when b^2>>4ac, the standard formula above is susceptible to round-off errors: For example if b is positive, calculation of one of the solutions, b-sqrt(b^2-4ac), will involve subtracting off a good fraction of significant bits (its almost b-sqrt(b^2)) leaving a poor digital representation of the difference. On hosts darkstar and blackstar, for example, floats can carry only 7 or 8 decimal digits of precision. Thus if b^2/4ac>>10^7 then the noise in representing b^2 is much bigger than 4ac; the difference, q=b^2-4ac, is thus simply b^2. The quadratic formula will then yield a completely incorrect root when you take the difference -b+sqrt(q) (when b is positive). The other root, -b-sqrt(q) is Ok, since the result is minus-one times the sum of two numbers; the roundoff error in the sum will be at the same level as for any number defined to machine precision.
To help this situation, a second formula is needed. Specifically, set x=1/q, rewrite the quadratic polynomial in terms of q, and multiply by q^2. When you apply the quadratic formula for q, and set it to 1 over itelf to get the roots of x, you find the formula
x1' = 2c/(-b - q)
- and -
x2' = 2c/(-b + q)
The key here is to note that when b is positive, x1 and x2' are
both susceptible to subtractive roundoff, but x2 and x1' are not.
When b is negative, the opposite is true.
The good thing is that in the absence of roundoff errors,
x1=x1' and x2=x2', so in any case, you can choose a pair
of roots which is *not* susceptible to roundoff.
Write your code so that it calculates both the standard roots and the alternatives just mentioned. Also, choose a pair of roots which is not susceptible to subtractive roundoff; which pair depends on the sign of b.
To compile your code, use the Gnu C++ compiler,
g++ -Wall -o quadroots quadroots.ccThe -Wall option tells the compiler to display all warnings -- that is, to maximally whine at you about anything that looks even remotely suspicious. This can be helpful when you are debugging your code. The -o option tells the name of the executable file that the compiler should create. (The default executable filename is "a.out".)
Your final program should work exactly like this:
darkstar> quadrootswhere the green is the user's (standard) input, std-roots are the pair of roots calculated by the standard way, alt-roots are the pair from the alternative formula, and best-roots are the combination which are not susceptible to subtractive round-off error. In the last line you should replace XXX with an estimate of the numerical value of |b|/sqrt(|4ac|) above which the standard formula causes errors of 1 percent or more. (Obtain this value once and for all, e.g., by analytical means, don't have your code calculate it each time it is run. This short write-up on effects of machine error in the solution of a quadratic equation might be helpful.)
input a b c: 1 -5 6
std-roots: 2 3
alt-roots: 2 3
best-roots: 2 3
1-percent-error-threshold: XXX
Thus one of the first things your code should do is send the user a message:
cout << "input a b c: ");
See the example code
~p5720/examples/c++in_out.cc
for a way to do this.
You may assume that the user will only put in values of (a,b,c) for
which nothing pathological happens (i.e., two real, non-zero
solutions exist).
Since there will be a sqrt-function call in there, don't forget to
#include <cmath>, as in the example code ~p5720/examples/c++mathfns.cc
Please turn in your C++ code only, quadroots.c++, and not any binary (executable) files.
This is an exercise with C++ involving a random number generator, as well as practice with command line arguments. The file ~p5720/examples/c++args.cc and might be helpful for dealing with command line arguments, while ~p5720/examples/c++mathfns.cc demonstrates how to come up with a random number generator using the cmath library.
Write a file called randgen.cc which, when compiled and linked, behaves as follows:
darkstar> randgen 1000 314159265printing (to std output) a column of 1000 random numbers using 314159265 as a seed for the "random" sequence.
0.08127079073
0.985625782
...
Details: The recommended starting point for this problem is the file c++args.c, since it has the command line argument stuff set and will take only minor modifications to work here. Then use the file c++mathfns.cc to add in the random number generator. Note that both the functions
double myrandom(); void myrandomseed(int);are needed. You must call the myrandomseed first to initialize the generator! Be sure to put the function prototypes near the top of your file, at least above the declaration of main(). You may place the function declarations at the end of your program. Work in double precision; try
cout.precision(10);before you write the random numbers to set the output to 10 decimal digits.
Turn in your source code, randgen.cc.
Write a C++ file called minmax.cc which, when compiled and linked, reads a file (with filename specified in the command line), line by line. The file is expected to be in text format, a 1-column list of floating-point numbers. If no filename is given in the command line, have your file read from standard input. Your program should work exactly like this example:
darkstar> minmax file.datwhere tot is the number of data elements; min, max and avg are (not surprisingly) minimum, maximum and average values of the data, respectively.
tot: 1000
min: 1.3445e-05
max: 0.999324291
avg: 0.50179001
Details: Perhaps start with the code ~p5720/examples/c++in_redirect.cc as an example of how to set the input designated by "cin" to a correspond to an input file. Also maybe look at ~p5720/examples/c++fileio.cc to see how to read in a list of numbers from a file (but you may wish to modify this code to read from standard input, as in the previous example). Ultimately, you will have to put together a code which interprets command line arguments, sets "cin" to a file (if necessary), and reads in data, an element at a time.
To check if your code works when reading from standard input, try
darkstar> randgen 1000 314159265 | minmax
to see that you get sensible results.
Turn in your C++ source code, mimax.c.