Horner’s Rule Polynomials

This program generates 25 polynomials of increasing degree randomly using a Mersenne twister, solves them via Horner’s rule and records runtime.

///////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include <random>
#include <iomanip>
#include <chrono>
///////////////////////////////////////////////////////////////////////////////
std::vector<int> randIntGen(int count);
float randRealGen(void);
void polyPrint(float x, std::vector<int> polyVals);
void hornersRuleTime(float x, int n, std::vector<int> polyVals);
///////////////////////////////////////////////////////////////////////////////
int main(void)
{
	std::vector<int> polyVals;
	float x;

	for(int i = 1; i <= 25; i++) // iterate through 25 cases
	{
		x = randRealGen(); // generate random real number
		polyVals = randIntGen(i); // Generate random polyvals
		std::cout << std::setprecision(2) << "\nCase " << i << ": " << "x = " 
			<< x << ", ";

		for(auto it = polyVals.begin(); it != polyVals.end(); it++)
		{
			std::cout << "a" << std::distance(polyVals.begin(), it) << " = "
				<< (*(it));
			
			if((it+1) != polyVals.end()) // if it is not the last printed
			{
				std::cout << ", "; // delimit with comma
			}
		}

		polyPrint(x, polyVals);
		hornersRuleTime(x, polyVals.size(), polyVals); // pass this case
		std::cout << std::endl;
	}

	return 0;
}
///////////////////////////////////////////////////////////////////////////////
std::vector<int> randIntGen(int count)
{
		std::vector<int> intArr;
		std::random_device rd;
		std::mt19937 engine(rd());
		std::normal_distribution<> dist(50, 50);
		int intBuff;

		for(int i = 0; i < count; i++)
		{	
			intBuff = (round(dist(engine)));
			
			while((intBuff < 1) || (intBuff > 99)) // while out of range
			{
				intBuff = (round(dist(engine))); // redo
			}
			
			intArr.push_back(intBuff); // push onto the array
		}

		return intArr;
}

///////////////////////////////////////////////////////////////////////////////
float randRealGen(void)
{
	float realBuff;
	std::random_device rd;
	std::mt19937 engine(rd());
	std::normal_distribution dist(0, 20.00);

	realBuff = dist(engine);

	while((realBuff > 20.00) || (realBuff < -20.00)) // While not in range
	{
		realBuff = dist(engine); // redo until it is
	}

	return realBuff;
}
///////////////////////////////////////////////////////////////////////////////
void polyPrint(float x, std::vector<int> polyVals)
{ 
	std::cout << "\n\tPolynomial: "; for(int i = (polyVals.size() - 1); i >= 0; i--)
	{
		std::cout << std::to_string(polyVals[i]) + "("; 
		std::cout << std::setprecision(2) << x << ")**" + std::to_string(i); if((i-1) >= 0) // if there is another
		{
			std::cout << " + "; // put a + to separate
		}
	}
}
///////////////////////////////////////////////////////////////////////////////
void hornersRuleTime(float x, int n, std::vector<int> polyVals)
{
	std::chrono::system_clock::time_point start = // initialize start time
			std::chrono::system_clock::now();

	std::chrono::system_clock::time_point end; // declare end time variable

	double result = polyVals[n]; // Set "seed" value
	
	for(int i = (n-1); i >= 0; i--)
	{
		result = result * x + double(polyVals[i]);
	}

	end = std::chrono::system_clock::now(); // Set end time
	
	/* Cast duration to nanoseconds, and output - sorry, it is a long line!
	*/
	std::cout << "\n\tCPU Time:    " << 
			std::chrono::duration_cast
					(end - start).count() << " nanoseconds";
	
	return;
}
///////////////////////////////////////////////////////////////////////////////

 

Leave a Reply

Your email address will not be published. Required fields are marked *