// Pruebas de freivalds.h: comprueban lo que los apuntes afirman sobre el algoritmo.
#include <cassert>
#include <cstdio>

#include "freivalds.h"

// El ejemplo de los apuntes.
const Matrix kA = {{1, 2, 0}, {0, 1, 3}, {2, 0, 1}};
const Matrix kB = {{2, 1, 0}, {1, 0, 2}, {0, 3, 1}};

void test_arithmetic() {
    // (p - 1)·(p - 1) = p² - 2p + 1, que es 1 módulo p. En 32 bits el producto no cabe.
    assert(mul_mod(kPrime - 1, kPrime - 1, kPrime) == 1);
    assert(mul_mod(0, kPrime - 1, kPrime) == 0);
    assert(mul_mod(123456789, 987654321, kPrime) == 259106859);
    const Matrix expected = {{4, 1, 4}, {1, 9, 5}, {4, 5, 1}};
    assert(multiply(kA, kB, kPrime) == expected);
    assert(times(kB, {0, 1, 1}, kPrime) == (Vector{1, 2, 4}));
    assert(times(kA, {1, 2, 4}, kPrime) == (Vector{5, 14, 6}));
}

// Los tres casos de freivalds_demo: 4, 4 y 7 vectores de 8 detectan la diferencia.
void test_demo_counts() {
    const Matrix product = multiply(kA, kB, kPrime);
    assert(count_detecting_vectors(kA, kB, product, kPrime) == 0);
    Matrix c1 = product;
    c1[1][2] += 1;
    assert(count_detecting_vectors(kA, kB, c1, kPrime) == 4);
    Matrix c2 = product;
    c2[0][0] += 1;
    c2[0][1] -= 1;
    assert(count_detecting_vectors(kA, kB, c2, kPrime) == 4);
    // El vector de solo unos no ve la diferencia de C2: las dos se cancelan.
    assert(freivalds_round(kA, kB, c2, {1, 1, 1}, kPrime));
    Matrix c3 = product;
    c3[0][0] += 1;
    c3[1][1] += 1;
    c3[2][2] += 1;
    assert(count_detecting_vectors(kA, kB, c3, kPrime) == 7);
}

// El teorema, comprobado sin azar: para matrices pequeñas se prueban los 2^n vectores.
// Si A·B = C ninguno detecta nada; si A·B ≠ C, al menos la mitad detecta la diferencia.
// Se prueba con varios módulos, también con uno que no es primo.
void test_at_least_half() {
    std::mt19937_64 rng(15);
    int different = 0;
    for (std::uint64_t p : {std::uint64_t{2}, std::uint64_t{3}, std::uint64_t{6}, std::uint64_t{7}, kPrime}) {
        for (int trial = 0; trial < 400; trial++) {
            const std::size_t n = 1 + trial % 5;
            const Matrix a = random_matrix(n, rng, p);
            const Matrix b = random_matrix(n, rng, p);
            const Matrix product = multiply(a, b, p);
            assert(count_detecting_vectors(a, b, product, p) == 0);
            // Se cambian entre 1 y 3 entradas, que pueden coincidir o cancelarse.
            Matrix c = product;
            const int changes = 1 + trial % 3;
            for (int t = 0; t < changes; t++) {
                std::uint64_t& entry = c[rng() % n][rng() % n];
                entry = (entry + rng() % p) % p;
            }
            const int detected = count_detecting_vectors(a, b, c, p);
            if (c == product) {
                assert(detected == 0);
            } else {
                different++;
                assert(2 * detected >= (1 << n));
            }
        }
    }
    assert(different > 1000);
}

// Con una sola entrada distinta, en la columna j, detectan exactamente los vectores con r_j = 1.
void test_single_entry() {
    std::mt19937_64 rng(4);
    const std::size_t n = 6;
    const Matrix a = random_matrix(n, rng, kPrime);
    const Matrix b = random_matrix(n, rng, kPrime);
    Matrix c = multiply(a, b, kPrime);
    c[3][2] = (c[3][2] + 5) % kPrime;
    assert(count_detecting_vectors(a, b, c, kPrime) == 32);
    for (unsigned mask = 0; mask < 64; mask++) {
        Vector r(n);
        for (std::size_t j = 0; j < n; j++) {
            r[j] = (mask >> j) & 1u;
        }
        assert(freivalds_round(a, b, c, r, kPrime) == (r[2] == 0));
    }
}

// La tabla de freivalds_experiment que citan los apuntes, con la misma semilla y el mismo orden.
void test_experiment_table() {
    std::mt19937_64 rng(2015);
    const std::size_t n = 30;
    const Matrix a = random_matrix(n, rng, kPrime);
    const Matrix b = random_matrix(n, rng, kPrime);
    const Matrix product = multiply(a, b, kPrime);
    Matrix wrong = product;
    wrong[17][4] = (wrong[17][4] + 1) % kPrime;
    assert(count_equal_answers(a, b, wrong, 1, 1000, rng, kPrime) == 508);
    assert(count_equal_answers(a, b, wrong, 2, 1000, rng, kPrime) == 245);
    assert(count_equal_answers(a, b, wrong, 5, 1000, rng, kPrime) == 34);
    assert(count_equal_answers(a, b, wrong, 10, 1000, rng, kPrime) == 1);
    // Error de un solo lado: con C = A·B la respuesta es siempre "iguales".
    assert(count_equal_answers(a, b, product, 10, 1000, rng, kPrime) == 1000);
}

int main() {
    test_arithmetic();
    test_demo_counts();
    test_at_least_half();
    test_single_entry();
    test_experiment_table();
    std::printf("test_freivalds: correcto\n");
}
