// Prueba de identidad de polinomios: ¿(x - 1)(x - 2)···(x - 10) es igual a un polinomio dado por
// sus coeficientes? Se evalúan los dos en un punto al azar. Se compara un módulo pequeño, 101, con
// el primo de la semana. La semilla es fija.
//
//   build/pit_demo
#include <cstdio>
#include <string>

#include "pit.h"

// Escribe un coeficiente con signo: los mayores que p/2 se leen como negativos.
long long as_signed(std::uint64_t c, std::uint64_t p) {
    return c > p / 2 ? static_cast<long long>(c) - static_cast<long long>(p) : static_cast<long long>(c);
}

void print_polynomial(const Polynomial& f, std::uint64_t p) {
    bool first = true;
    for (std::size_t i = f.coefficients.size(); i > 0; i--) {
        const long long c = as_signed(f.coefficients[i - 1], p);
        if (c == 0) {
            continue;
        }
        const long long magnitude = c < 0 ? -c : c;
        std::printf("%s", first ? (c < 0 ? "-" : "") : (c < 0 ? " - " : " + "));
        const std::size_t degree = i - 1;
        if (magnitude != 1 || degree == 0) {
            std::printf("%lld", magnitude);
        }
        if (degree >= 1) {
            std::printf("x");
        }
        if (degree >= 2) {
            std::printf("^%zu", degree);
        }
        first = false;
    }
    std::printf("\n");
}

void experiment(std::uint64_t p, std::mt19937_64& rng) {
    const int runs = 1000;
    Factored f;
    for (std::uint64_t root = 1; root <= 10; root++) {
        f.roots.push_back(root);
    }
    const Polynomial expanded = expand(f, p);
    Polynomial one_wrong = expanded;
    one_wrong.coefficients[3] = (one_wrong.coefficients[3] + 1) % p;
    const Polynomial zero{{0}};

    struct Row {
        const char* name;
        const Polynomial* g;
    };
    const Row rows[] = {
        {"su desarrollo", &expanded},
        {"el desarrollo con un coeficiente cambiado", &one_wrong},
        {"el polinomio cero", &zero},
    };
    std::printf("p = %llu, %d ejecuciones por fila, cota 10/p = %.2e\n", static_cast<unsigned long long>(p),
                runs, 10.0 / static_cast<double>(p));
    std::printf("  f se compara con                            coinciden en    responde \"coinciden\"\n");
    for (const Row& row : rows) {
        const int agree = count_agree_answers(f, *row.g, runs, rng, p);
        if (p <= 1000) {
            std::printf("  %-42s  %3llu de %llu      %4d de %d\n", row.name,
                        static_cast<unsigned long long>(count_agreements(f, *row.g, p)),
                        static_cast<unsigned long long>(p), agree, runs);
        } else {
            std::printf("  %-42s  (no se cuenta)  %4d de %d\n", row.name, agree, runs);
        }
    }
    std::printf("\n");
}

int main() {
    // Un ejemplo que se puede seguir a mano.
    const Factored small{{1, 2, 3, 4}};
    const Polynomial small_expanded = expand(small, kPrime);
    std::printf("(x - 1)(x - 2)(x - 3)(x - 4) = ");
    print_polynomial(small_expanded, kPrime);
    std::printf("En x = 7: por factores %llu, por coeficientes %llu\n\n",
                static_cast<unsigned long long>(evaluate(small, 7, kPrime)),
                static_cast<unsigned long long>(evaluate(small_expanded, 7, kPrime)));

    std::printf("f(x) = (x - 1)(x - 2)···(x - 10), de grado 10\n\n");
    std::mt19937_64 rng(2015);
    experiment(101, rng);
    experiment(kPrime, rng);
}
