Challenge introduction

Solving this task helps familiarize yourself with key aspects of programming in C++. Firstly, it reinforces the fundamentals of user input handling, conditional statements, loops, and exception handling. Besides, it introduces mathematical concepts related to polynomials and roots, demonstrating how programming can be used to solve real-world mathematical problems.

The problem is sourced from the programming languages subject from UNED and is available at the following link. I recommend attempting to solve the challenge independently before reviewing the provided solution.

Problem statement

The polynomial \(f(x)\) can be expressed in the following form:

    \(f(x) = x^{n} + a_{1} · x^{n−1} + · · · + a_{n−1} · x + a_{n}\)

or equivalently,

    \(f(x) = (x − α_1) · (x − α_2) · · · (x − α_n)\)

Where \(n\) is the degree of the polynomial; \(a_1, a_2, . . . , a_n\) are the coefficients; and \(α_1, α_2, . . . , α_n\) are the roots. In this exercise, we will assume that all the roots of the polynomial \(f(x)\) are real numbers.

Write a C++ program that performs the following actions:

1. Display a message on the console, requesting the user to input the degree of the polynomial via the console. Read the value entered via the console and store it in an integer variable named \(n\).
2. If \(n < 1\), display a message on the console indicating this condition and terminate.
3. Display a message on the console, requesting the user to input the n roots of the polynomial. Read the values entered via the console and store them in a double vector named alpha.
4. Calculate the coefficients of the polynomial \((a1, a2, . . . , an)\) and display them on the console in scientific notation with 8 digits after the decimal point.
5. Terminate.

Solution

The rationale behind the provided solution can be divided into distinct logical steps. Initially, the program is tasked with handling user input, which encompasses correctly gathering and storing information while also assessing the appropriateness of the responses.

Moving on to the mathematical aspect of the problem, an iterative approach is employed. It commences with the polynomial \(f_0(x) = 1\). With each new root introduced, the polynomial undergoes expansion following the specific rule: \(f_i(x) = f_{i-1}(x) · (x - \alpha_i) = f_{i-1}(x) · x - f_{i-1}(x) · \alpha_i\). In this context, \(f_i(x)\) denotes the expanded polynomial up to the i-th root (inclusive), and \(\alpha_i\) represents the i-th root. Concerning the polynomial's coefficients, multiplying the expanded polynomial up to the previous root by \(x\) is akin to shifting all coefficients one position to the left while introducing a zero in place of the last coefficient (if they are organized in descending order of power). Conversely, multiplication by \(\alpha_i\) entails multiplying all coefficients of the expanded polynomial up to the previous root by the scalar \(\alpha_i\). Consequently, this process systematically updates the coefficients of the entire polynomial in each iteration, progressively incorporating all the roots.

For those seeking to enhance the algorithm's efficiency, it is conceivable to leverage specific properties of the polynomial's roots. For example, when dealing with repeated roots, it is plausible to initiate the expansion process from those roots, utilizing the expansion of Newton's binomial. However, it is essential to note that these particular optimizations, contingent on the characteristics of certain root families, have not been integrated into the solution for this problem.

Throughout the code, error handling has been implemented to address exceptions. Should any issues arise during user input or calculations, the program furnishes informative error messages and concludes execution in a controlled manner.

#include <iostream>
#include <iomanip>
#include <vector>
#include <stdexcept>
#include <sstream>
std::vector<double> load_all_roots(int n)
throw (std::invalid_argument) {
    double root;
    std::vector<double> alpha;
    for (int i = 1; i < n + 1; i++) {
        std::cout << "Please enter root alpha" << i << ": ";
        if (!(std::cin >> root)) {
            std::stringstream ss;
            ss << "A non-numeric root has been entered, program terminated.";
            throw std::invalid_argument(ss.str());
        }
        alpha.push_back(root);
    }
    return alpha;
}

std::vector<double> expand_by_single_root(std::vector<double> coefficients, double root) {
    std::vector<double> expanded_coefficients = coefficients;
    expanded_coefficients.push_back(0);
    std::vector<double>::iterator it_1 = expanded_coefficients.begin();
    std::vector<double>::iterator it_2 = coefficients.begin();
    for (int i = 0; i < coefficients.size(); i++) {
       *(it_1 + i + 1) -= *(it_2 + i) * root;
    }
    return expanded_coefficients;
}

std::vector<double> expand_polynomial(std::vector<double> alpha) {
    std::vector<double> expanded_coefficients = { 1 };
    std::vector<double>::iterator root;
    for (root = alpha.begin(); root < alpha.end(); root++) {
        expanded_coefficients = expand_by_single_root(expanded_coefficients, *root);
    }
    return expanded_coefficients;
}

int main() {
    int n;
    std::cout << "Please enter the degree of the polynomial: ";
    if (!(std::cin >> n) || std::cin.get() != '\n') {
        std::cout << "The selected degree is not an integer, program terminated." << std::endl;
        return -1;
    }else if (n < 1) {
        std::cout << "The selected degree is less than one, program terminated" << std::endl;
        return -1;
    }else {
        try {
            std::vector<double> alpha = load_all_roots(n);
            std::vector<double> expanded_coeffs = expand_polynomial(alpha);
            std::cout << "\n-------- Polynomial coefficients --------" << std::endl;
            int i = 1;
            std::vector<double>::iterator coef;
            for (coef = expanded_coeffs.begin() + 1; coef < expanded_coeffs.end(); coef++) {
                std::cout << std::scientific << std::setprecision(8) << "Coefficient a" << i;
                std::cout << " (x^" << n - i << "): " << *coef << std::endl;
                i++;
            }
        }
        catch (std::invalid_argument& exception) {
    	    std::cout << exception.what() << std::endl;
    	    return -1;
        }
    }
    return 0;
}