Manipulating Polynomials C++

Creating and Using Dynamic Arrays

Manipulating Arrays

Using Arrays as Formal Parameters

Polynomial

De?nition 1. A univariate polynomial is a mathematical expression involving a sum of powers in one variable multiplied by coe?cients. A polynomial in one variable with constant coe?cients is given by the expression p(x) = n P i=0 cixi, where the ci 0s are numeric values representing the coe?cients. The polynomial is said to be an nth-degree polynomial if its highest power is n. For example, 3x4 ?2x3 + x2 ?1 is a fourth-degree polynomial. To evaluate a univariate polynomial, given a numeric value, the value is substituted for the variable and the expression is evaluated. For example, given the polynomial p(x) = 3x4 ? 2x3 + x2 ? 1, p(?2) = 67 since 3 (?2)4 ? 2 (?2)3 + (?2)2 ? 1 = 67. A univariate polynomial can be represented as a degree-coe?cients array, that is, with its ?rst element representing the degree of the polynomial and the remaining elements its coe?cients in order of descending powers. For example, the polynomials 3x4?2x3 +x2?1 and 3x2 +2x?5 are represented as [4,3,?2,1,0,?1] and [2,3,2,?5], respectively.

In this project you will write an interactive program that represents univariate polynomials using arrays in which the coe?cients are arranged in order of descending powers. The program will have functions generate a string representation of a polynomial in standard form, compute the indefinite integral of a polynomial, compute the derivative of a polynomial and evaluate a polynomial.

In order to e?ectively manage memory, the array representing the polynomial entered by the user will be dynamically allocated. To dyanically allocate an array, the following syntax may be used:

arrayType* arrayName = new arrayType[arraySize];

Example 1. double* salaries = new double[10];

Dynamically allocating an array gives a programmer the ?exibility of being able to create an array of any size during run-time and deallocating the array when it is no longer needed. Unlike static arrays that are deallocated when the function in which they are declared is terminated, dynamically allocated arrays are fully within the programmers control and may be deallocated at any point after they are created. The example above creates an array of doubles that has the size of 10. To deallocate a dynamically allocated array, use the following syntax:

delete[] nameOfArray;

This example shows how the salaries array can be deallocated.

Example 2. delete[] salaries;

When an array is deallocated, it is no longer accessible. It has to be reallocated if there is a need to re-use it. Proceed with caution when working with dynamically allocated arrays. When a variable associated with a dynamically allocated array is re-used, be sure to deallocate the array before using the variable. Failure to do so leads to memory leak. Memory leak is the allocation of a chunk of memory that contains inaccessible data and cannot be reallocated. There is a lot more to dynamic memory allocation. For now, this is enough to get us through the project.

Write a program called PolyManipulator that uses a modular design. This program will involve the implementation of several functions that use arrays as formal parameters. Some function will return dynamically allocated arrays. As was the case with your previous project, use an sstream object when writing the polyToStr function that returns a string representation of a polynomial.

In addition to the main, your program should consist of the following functions:

/** * Gives a string representation of this polynomial in descending

* powers in standard form where zero terms, coefficients 1 or -1,

* and exponents 1 are not displayed.

*

 
* Note: Rules for Representing a Polynomial in Normalized Form:
 
* 1. If the degree of the polynomial is 0, return a string
 
 representing the number.
 
* 2. If the degree of the polynomial is 1, return a string
 
 * representing the polynomial in the form ax + b, where when b
 
* is zero it should not be displayed and when a is -1 or 1
 
* it should not be displayed as a coefficient of x.
 
* 3. If the degree of the polynomial is 2 or more, follow these steps:
 
* A. Generate the string representation of the highest order term
 
* without using 1, -1 as its coefficient.
 
* B. Generate the string representations of all other, but the
 
* last two, terms beginning from the second highest order term
 
* without the use of 1 and -1 as coefficients and without
 
* including a zero term. Then deal with the last two terms:
 
* i. If its linear term is non-zero, generate and append
 
* the linear term but without the use of 1 and -1 as its
 
* coefficient and 1 as its exponent.
 
* ii. Finally, append the constant term, the lowest order term,
 
* if it is non-zero.
 
* eg: [6, 3, 0, -1, 0, 1, 1, 0] -> 3x^6 - x^4 + x^2 + x
 
* [5, -1, 0, 3, 0, -1, 1] -> -x^5 + 3x^3 - x + 1 * 

* @param poly a degree-coefficients array representation of a polynomial.

* @return a string representation of this polynomial

*/

string polyToStr(const double poly[])

/**

* Evaluates the polynomial represented by the array at the specified value.

* @param poly a degree-coefficients array representation of a polynomial.

* @param x numeric value at which the polynomial is to be evaluated.

* @return the value of the polynomial when evaluated with x

*/

double polyEval(const double poly[],double x)

/**

* Generates the array representation of the derivative of a polynomial

*

 
* Note: The degree of a polynomial of degree 0 is 0.
 
*This function should return an array of size 2 whose elements are [0, 0]
 
*when called using a polynomial of degree 0.
 
* 

* @param poly a degree-coefficients array representation of a polynomial.

* @return the array representation of the derivative of the * specified polynomial.

*/

double* differentiate(const double poly[])

/**

* Computes an indefinite integral for the specified polynomial

* @param poly a degree-coefficients array representation of a polynomial.

* @param c the constant term

* @return the array representation of the integeral of the specified

* polynomial with the specified constant term.

*/

double* integrate(const double poly[], double c)

Integral and Derivative of a Polynomial

The integral and derivative of polynomials have applications in many ?elds including mathematics, the physical sciences and engineering. Given a univariate polynomial f(x), to calculate its derivative, denoted f0(x), read f prime of x, we compute the derivative of each of its terms. The derivate of the term aixi is aixi?1. For example, the derivate of ?4x7 is ?28x6. Observe that the derivate of the constant term, a number, is 0 since any constant c can be expressed as cx0. The number of terms in f0x) is one less than the number of terms in f(x). The inde?nite integral of f(x), denotedRf(x)dx, is a polynomial obtained by computing the integral of each term of its terms. The integral of the term aixi is ai i+1xi+1. For example, the integral of 3x4 is 0.6x5. When determining the inde?nite integral, we add an arbitrary constant so the integral of f(x) has one more term than f(x). Suppose the de?nite integral of f(x) is denoted F(x), then we can compute the de?nite integral over a range of values [xmax,xmin] by calculating F(xmax)?F(xmin) and obtain a numeric value. That is, by evaluating the inde?nite integral between two values of the variable x, we obtain the de?nite integral.

The Main function

Write the program incrementally. First get the polyToStr to work. Then get polyEval to work. You can then write di?erentiate followed by integrate. When the functions are all working correctly, you can write the main.

When the program begins, it prompts the user for the degree of a polynomial and its coe?cients in order of descending powers as shown in the sample run. It then dynamically allocates an array and stores the degree and coe?cients in an array in degree-coe?cients format as described in this handout. The highest order coe?cient of the polynomial must be non-zero. You may assume that the user always enters the correct number of coe?cients with the ?rst being non-zero. The program then displays the polynomial using the polyToStr function. It prompts the user for a value at which to evaluate the polynomial. It evaluates the polynomial and displays the result. It then computes and displays the derivative of the polynomial. It also computes the inde?nite integral of the polynomial using 1 as the constant. Finally, it prompts the user for the upper and lower limits and then computes the de?nite integral for the polynomial using those limits.

A typically run of the program would be:

Listing 1: Code Segment

1 Enter the degree of the polynomial -> 3

2

3 Enter the coefficients -> 4 1 0 1

4 f(x) = 4x^3 + x^2 + 1

5

6 Enter a value at which to evaluate this polynomial -> 3

7 f(3) = 118

8

9 f(x) = 12x^2 + 2x

10 Integrate[f(x),x] = x^4 + 0.333333x^3 + x + 1

11

12 Enter the upper and lower limits of the integral -> 3 0

13 Integrate[f(x),x,3,0] = 93