#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <chrono>

using namespace std;

double horner(double* p, double x, int n) {
    double y = 0;

    for (int i = 0; i < n; ++i)
        y = x * y + p[i];

    return y;
}

double simple(double* p, double x, int n) {
    double y = 0;
    double xi = 1;

    for (int i = n - 1; i >= 0; --i, xi *= x)
        y += p[i] * xi;

    return y;
}

void print_poly(double* p, int n) {
    for (int i = 0; i < n; ++i) {
        cout << " + (" << p[i] << ") x^" << (n - i - 1);
    }
}

void rand_poly(double* p, int n) {
    for (int i = 0; i < n; ++i) {
        p[i] = ((double) rand() / (RAND_MAX));
    }
}

int main() {
    cout.precision(15);
    const int NUMBER_OF_EXPERIMENTS = 20;
    const int NUMBER_OF_REPETITIONS = 1000000;

    srand(time(NULL));

    cout << "---------------------------------------------------\n";
    cout << "|    WARTOSC WIELOMIANU W PUNKCIE - POROWNANIE    |\n";
    cout << "---------------------------------------------------\n\n";

    int n;
    double x;

    cout << "Prosze podac rozmiar tablicy: ";
    cin >> n;

    double* p = new double[n]; // dynamiczna alokacja tablicy

    std::chrono::steady_clock::time_point start, stop;
    double mean_horner_time = 0;
    double mean_simple_time = 0;
    double y_horner, y_simple, time_horner, time_simple;

    for (int experiment = 1; experiment <= NUMBER_OF_EXPERIMENTS; ++experiment) {
        cout << "Cykl " << experiment << ".\n\n";
        rand_poly(p, n);
        cout << "p(x) =";
        print_poly(p, n);
        x = ((double) rand() / (RAND_MAX));
        cout << "\nx = " << x << "\n";

        start = std::chrono::steady_clock::now();
        for (int j = 0; j < NUMBER_OF_REPETITIONS; ++j)
            y_horner = horner(p, x, n);
        stop = std::chrono::steady_clock::now();
        time_horner = (double) std::chrono::duration_cast<std::chrono::nanoseconds> (stop - start).count() / NUMBER_OF_REPETITIONS;
        mean_horner_time += time_horner;
        cout << "\nMetoda Hornera\np(x) = " << y_horner <<
                "\nczas = " << time_horner << "\n";

        start = std::chrono::steady_clock::now();
        for (int j = 0; j < NUMBER_OF_REPETITIONS; ++j)
            y_simple = simple(p, x, n);
        stop = std::chrono::steady_clock::now();
        time_simple = (double) std::chrono::duration_cast<std::chrono::nanoseconds> (stop - start).count() / NUMBER_OF_REPETITIONS;
        mean_simple_time += time_simple;
        cout << "\nMetoda zwykla\np(x) = " << y_simple <<
                "\nczas = " << time_simple << "\n";

        cout << "\nRoznica pomiedzy wynikami: " << fabs(y_horner - y_simple) << "\n\n";
    }

    mean_horner_time /= NUMBER_OF_EXPERIMENTS;
    mean_simple_time /= NUMBER_OF_EXPERIMENTS;

    cout << "Podsumowanie\n";
    cout << "Sredni czas metody Hornera: " << mean_horner_time;
    cout << "\nSredni czas metody zwyklej: " <<  mean_simple_time;

    delete[] p; // usuniecie tablicy

    return 0;
}