Horner

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;
using namespace chrono;

double F(double x, const vector<double>& factors, const vector<int>& powers) {
    double result = 0;
    for (int i = 0; i < factors.size(); i++) {
        double act = 1;
        for (int j = 0; j < powers[i]; j++) {
            act *= x;
        }
        result += factors[i] * act;
    }
    return result + 1;
}

double horner(double x, const vector<double>& factors, const vector<int>& powers) {
    int max_power = *max_element(powers.begin(), powers.end());

    vector<double> complete_factors(max_power + 1, 0);
    for (int i = 0; i < factors.size(); ++i) {
        complete_factors[max_power - powers[i]] = factors[i];
    }

    double result = complete_factors[0];
    for (int i = 1; i < complete_factors.size(); ++i) {
        result = result * x + complete_factors[i];
    }
    return result;
}

int main() {
    double x;
    cin >> x;

    vector<double> factors;
    vector<int> powers;

    while (true) {
        double f;
        int p;
        cin >> f >> p;
        if (f != 0 && p != 0) {
            factors.push_back(f);
            powers.push_back(p);
        } else {
            break;
        }
    }

    vector<int> indices(factors.size());
    for (int i = 0; i < indices.size(); ++i) {
        indices[i] = i;
    }

    sort(indices.begin(), indices.end(), [&](int a, int b) {
        return powers[a] > powers[b];
    });

    vector<double> sorted_factors(factors.size());
    vector<int> sorted_powers(powers.size());
    for (int i = 0; i < indices.size(); ++i) {
        sorted_factors[i] = factors[indices[i]];
        sorted_powers[i] = powers[indices[i]];
    }

    auto start = high_resolution_clock::now();
    double result_F = F(x, sorted_factors, sorted_powers);
    auto stop = high_resolution_clock::now();
    auto duration_F = duration_cast<duration<double>>(stop - start);
    cout << "F: " << result_F << " (" << duration_F.count() << " seconds)" << endl;

    start = high_resolution_clock::now();
    double result_horner = horner(x, sorted_factors, sorted_powers);
    stop = high_resolution_clock::now();
    auto duration_horner = duration_cast<duration<double>>(stop - start);
    cout << "Horner: " << result_horner << " (" << duration_horner.count() << " seconds)" << endl;

    return 0;
}