Question
Create a program called main.cpp that meets the requirements identified below. Submit your main.cpp source code file to the Desire2Learn dropbox for this assignment. In
- Create a program called main.cpp that meets the requirements identified below.
- Submit your main.cpp source code file to the Desire2Learn dropbox for this assignment.
- In addition to your program file, please submit a PDF file with a short summary of the results of your timing tests.
In this assignment you will create a C++ program that performs 2 timing tests. One test will time a function that does a straight evaluation of a polynomial and the other will time a function that uses Horners Rule (Algorithm 11.3.4 on page 750 of the Epp text) to evaluate a polynomial of the form:
a_nx^n + a_(n1)x^(n1) + ... + a_2x^2 + a_1x^1 + a_0
Empirical timing tests are a common way of assessing program performance. In this assignment, your program will generate 20 random polynomials (one each of degree 1 through 20), and evaluate these polynomials for a random real number x. Your program will then report the CPU time required to evaluate each polynomial.
The basic design of your program should be:
for n=1 to 20
{
Generate a random polynomial of degree n with integer coefficients between 1 and 99.
Generate a random real value x in the range from -20.00 to 20.00
Display the polynomial and the x value.
Evaluate the polynomial using Horners algorithm.
Report the time required to do this.
Evaluate the polynomial the usual way.
Report the time required to do this.
Print the result of the evaluation, P(x).
}
There should be a function that implements Horners algorithm and another function to do a straight evaluation. For the straight evaluation, do not use any functions that evaluate exponents. Instead do repeated multiplies. In other words x4 would be evaluated by implementing xxxx
Set up the timing to start when you start the evaluations inside the functions. Dont time the part where you generate the polynomials. Wait until you call the functions.
Example from running the program on my laptop with degree limited to 4:
> main.exe
degree 1
71x^1 + 55x^0
x = -1.85714
Horner 2.65e-07seconds.
Not Horner 1.5e-07seconds.
P(x)= -76.8571
degree 2
20x^2 + 94x^1 + 2x^0
x = -1.71429
Horner 1.13e-07seconds.
Not Horner 1.82e-07seconds.
P(x)= -100.367
degree 3
16x^3 + 62x^2 + 72x^1 + 2x^0
x = -1.57143
Horner 1.12e-07seconds.
Not Horner 2.1e-07seconds.
P(x)= -20.1283
degree 4
68x^4 + 11x^3 + 40x^2 + 87x^1 + 23x^0
x = -1.42857
Horner 1.17e-07seconds.
Not Horner 2.3e-07seconds.
P(x)= 231.492
Representing Polynomials in C++
Polynomials of the form anxn + an1xn1 + ... + a2x2 + a1x1 + a0
can be represented as lists (arrays or vectors). The coefficients are int or long int data types, or mpz class objects.
In the example program above, polynomials were stored in an array. The subscript identified the coefficient, i.e. coeff[0] representeda0, coeff[1] represented a1, and so forth.
Random Numbers: The Header
The C++ 11 standard greatly enhanced the ability to generate random numbers with the creation of the header library. The steps needed to create a sequence of random numbers is:
1. Create a random device object
2. Create a random engine object from the random device
3. Create a distribution of random numbers
A sequence of random number is then extracted from the distribution.
For this assignment, a normal distribution with a mean of 50 is sufficient, although you may use other distributions and means if desired. (See lab 5 notes for more information on this.) The code to generate the normal sequence is:
random_device rd; // Random device
mt19937 engine(rd()); // Random engine
normal_distribution<> dist(50,10); //Normal distribution
// Generate 10 random numbers
for(int n = 0; n < 10; n++) {
cout << round(dist(engine));
}
Date and Time: The Header
The C++ 11 header is used to access the system clocks in C++. The steps needed to calculate intervals is:
- Create two time point objects to store the begin and end clock times.
- Execute a system clock::now() command and store the result in one of the time points
- Execute your test code
- Execute a second system clock::now() command and store the result in the other time point
- Create a duration object to hold the difference between the time points
This is a program that uses the code to time how long it take to print a bunch of stars :
// steady_clock example
#include
#include
#include
#include
int main ()
{
using namespace std::chrono;
steady_clock::time_point t1 = steady_clock::now();
std::cout << "printing out 1000 stars... "; //time wasting loop
for (int i=0; i<1000; ++i) std::cout << "*";
std::cout << std::endl;
steady_clock::time_point t2 = steady_clock::now();
duration time_span = duration_cast>(t2 - t1);
std::cout << "It took me " << time_span.count() << " seconds.";
std::cout << std::endl;
return 0;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started