Project 1

Due Thursday June 21 at 6 p.m.

Your code will be graded on both its correctness and its elegence. So please take the time to try to come up with short and easy to understand solutions. Please read the programming guides on the Assignments page.

Please consult the directory ~hsc/classes/270/examples on CDF. Some of the examples may prove useful in solving these problems.

1. Roots of a Polynomial (40%)

The program will input data in the following order:

• The number of coefficients of the polynomial.
• The coefficients for the polynomial in integers.
• A desired tolerance as a floating point number.
• The maximum number of iterations.

Here is a sample execution:

%eddie: factorpoly
>>>> 5 1 -3 -3 7 6 5.0e-7 100
        Degree:        4
        Coeff:         1 -3 -3 7 6 
        Tolerance:     5.0e-07
        # Interations: 100

        Root:  3.000000, P( 3.000000) = 0
        Root:  2.000000, P( 2.000000) = 0
        Root: -1.000000, P(-1.000000) = 2.27374e-13
        Root: -1.000000, P(-1.000000) = 0

I have started the program for you: factorpoly.c

You have to write the following routines:

• abs_maximum(A, n): takes an array A of size n and finds the element of largest absolute magnitude and returns that absolute magnitude. For example of A = {1, -5, 3}, the returned value will be 5.
• derivative_of_poly(n, P, P_prime): P and P_prime are arrays. P holds the coefficients of the polynomial, and n is the number of coefficients. The function will set P_prime to hold the coefficients of the derivative of P. P[n-1] will hold the leading coefficient of the polynomial, and P_prime[n-2] will hold the leading coefficient of the derivative.
• findRoot(n, P, tol, ic, x0, errflag): returns a root for P using Newton's Method.
  • P holds the coefficients of the polynomial, and n is the number of coefficients. (Thus the degree of P is n-1). The leading coefficient is in P[n-1].
  • x0 is the initial guess that you should use for the root,
  • ic is the maximum number of iterations (i.e. guesses) you should try. If the function does not find a root after ic iterations, the function will set the error flag errflag and return.
  • tol is the tolerance to use. If the difference between two guesses is less than tol, then assume that the last guess made is the root.

Please place all your code in the file factorpoly.c and submit it electronically.

2. Floating Point Calculator (60%)

The structure you will use for the floating point number is as follows:

#define MANTISSA_SIZE   60
#define NEGATIVE        1
#define POSITIVE        0

struct floating {
    char sign;
    char mantissa[MANTISSA_SIZE];
    signed char exponent;
};

You should realize that the above floating point structure will allow calculations of more precision than either the float or double type of C.

Hint: This is not an easy problem, and I do not expect everyone to complete it so the grading will be weighted accordingly. Please attempt each piece in order because each piece is more difficult than the previous piece, and each later piece may depend on an earlier one.

You are to add the following pieces:

1. floating_add(num1, num2): Returns the result of adding each floating point number together. It is assumed that the signs of the two numbers are the same.
2. floating_sub(num1, num2): Returns the result of subtracting the second floating point number from the first. It is assumed the signs of the two numbers are different.
3. floating_mult(num1, num2): Returns the result of multiplying the two floating point numbers together.
4. floating_div(num1, num2): Returns the result of dividing the first number by the second. To implement division, I want you to use Newton's Method to calculate the reciprocal of the second number and multiply the first number with the reciprocal of the second.

Besides divide-by-zero errors, your program will also have to catch underflow and overflow errors. These errors occur if the floating point number is too large or small to fit in the data structure. In this case, you check for this error by detecting if the exponent goes out of the [-128, 127] bound.

Since we are dealing with decimal and not binary numbers, the first digit after the decimal point is stored. For your homework, assume that the number 0 is stored with all digits of the mantissa equal to 0 and the exponent equal to -128. If an error occurs, your program should report the type of error and exit.

Hint: To simplify your error checking, you may want to reduce the MANTISSA_SIZE to something more reasonable (like 4), and increase it once you get the functions working.

Note that you should not try to convert the mantissa characters to integer or floating point because the mantissa is too large to fit in either a C integer or double. Thus, you will have to write your own arithmetic utilities.

Here is some code that reads in and prints our floating point numbers: floating_numbers.c

Place all of your code in a file called calculator.c and submit the file electronically.