// Pasos 4 y 5 del laboratorio: medir cuántas veces se equivoca Freivalds con k rondas.
//
// El programa arma dos matrices A y B de 40×40 y una C que difiere de A·B en una sola entrada.
// Para cada k en {1, 2, 5, 10} corre 1000 veces "k rondas" y cuenta en cuántas ninguna ronda vio
// la diferencia: esos son los fallos. No lee nada de la entrada.
//
//   g++ -Wall -Wextra -std=c++20 -O2 experiment.cpp -o build/experiment
//   build/experiment [semilla]
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <random>
#include <vector>

const std::uint64_t kPrime = 1'000'000'007;

// Igual que en solution.cpp: la entrada (i, j) está en [i·n + j].
using Matrix = std::vector<std::uint32_t>;

// Por hacer: una ronda de Freivalds, la misma de su solution.cpp. Elige un vector r de n ceros y
// unos con rng y devuelve true si A·(B·r) y C·r son distintos, es decir, si la ronda detectó que
// A·B ≠ C.
bool round_detects(const Matrix& a, const Matrix& b, const Matrix& c, std::size_t n, std::mt19937_64& rng) {
    (void)a, (void)b, (void)c, (void)n, (void)rng;  // todavía no se usan
    return false;
}

int main(int argc, char** argv) {
    const std::uint64_t seed = argc > 1 ? std::strtoull(argv[1], nullptr, 10) : 1;
    const std::size_t n = 40;
    const int runs = 1000;
    std::mt19937_64 rng(seed);

    Matrix a(n * n), b(n * n), c(n * n);
    for (std::size_t i = 0; i < n * n; i++) {
        a[i] = static_cast<std::uint32_t>(rng() % kPrime);
        b[i] = static_cast<std::uint32_t>(rng() % kPrime);
    }
    // C = A·B, por la definición. Aquí n es pequeño y n³ no cuesta nada.
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = 0; j < n; j++) {
            std::uint64_t sum = 0;
            for (std::size_t k = 0; k < n; k++) {
                sum = (sum + std::uint64_t{a[i * n + k]} * b[k * n + j]) % kPrime;
            }
            c[i * n + j] = static_cast<std::uint32_t>(sum);
        }
    }
    // La única diferencia: una entrada al azar vale uno más.
    std::uint32_t& changed = c[rng() % (n * n)];
    changed = static_cast<std::uint32_t>((changed + 1) % kPrime);

    std::printf("semilla %llu, %d ejecuciones por fila\n", static_cast<unsigned long long>(seed), runs);
    std::printf(" k   fallos   fracción   cota 2^-k\n");
    for (int k : {1, 2, 5, 10}) {
        int failures = 0;
        for (int run = 0; run < runs; run++) {
            bool detected = false;
            for (int round = 0; round < k && !detected; round++) {
                detected = round_detects(a, b, c, n, rng);
            }
            failures += detected ? 0 : 1;
        }
        std::printf("%2d   %6d   %8.3f   %9.6f\n", k, failures, static_cast<double>(failures) / runs,
                    1.0 / static_cast<double>(1 << k));
    }
    return 0;
}
