Semana 15 — Jerarquías, azar y lo que sigue abierto

Objetivos

  • Enunciar los teoremas de jerarquía y explicar la diagonalización que los demuestra.
  • Explicar qué muestran los oráculos sobre los límites de esa técnica.
  • Definir BPP, analizar un algoritmo probabilístico y reducir su error por repetición.
  • Dibujar el mapa de las clases del curso y decir qué inclusiones se sabe que son estrictas.

Sesión A — Teoremas de jerarquía · ✂️ Oráculos y los límites de la diagonalización

Lectura: Apuntes, semana 15.

Apoyo: Sipser, sec. 9.1 (Hierarchy Theorems) y 9.2 (Relativization).

Temas:

  • Hasta aquí casi todas las inclusiones entre clases podrían ser igualdades. ¿Se sabe que alguna es estricta?
  • Teorema de jerarquía de espacio: con más espacio se decide estrictamente más. La demostración es la diagonal de la semana 9, con un límite de recursos: una máquina que simula a cada máquina con espacio acotado y hace lo contrario.
  • Por qué hacen falta funciones construibles, y por qué la simulación necesita un poco más de recursos que lo simulado.
  • Teorema de jerarquía de tiempo, con su factor logarítmico. Se enuncia y se dice de dónde sale el factor.
  • Consecuencias: P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}, L≠PSPACE\mathsf{L} \neq \mathsf{PSPACE} y NL≠PSPACE\mathsf{NL} \neq \mathsf{PSPACE}. En la cadena P⊆NP⊆PSPACE⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME} alguna inclusión es estricta, y no se sabe cuál.
  • Problemas que se sabe que no están en P: no por conjetura, sino por teorema.
  • ✂️ Oráculos: una máquina que consulta gratis un lenguaje. Existen AA y BB con PA=NPA\mathsf{P}^A = \mathsf{NP}^A y PB≠NPB\mathsf{P}^B \neq \mathsf{NP}^B.
  • ✂️ Lo que eso significa: una demostración que funcione igual con cualquier oráculo, como la diagonalización, no puede resolver P frente a NP.
  • Error común: leer el teorema de jerarquía como “más tiempo siempre ayuda para todo problema”. Dice que existe algún problema al que le ayuda.

Sesión B — Computación probabilística: BPP · Qué sigue abierto · Repaso

Lectura: Apuntes, semana 15.

Apoyo: Sipser, sec. 10.2 (Probabilistic Algorithms). Barak, capítulos 19 (Probabilistic computation) y 20 (Modeling randomized computation).

Temas:

  • Una máquina que lanza monedas. Solo hace falta probabilidad elemental: eventos independientes y la probabilidad de que todos fallen.
  • Verificar A⋅B=CA \cdot B = C sin multiplicar: el algoritmo de Freivalds, en O(n2)O(n^2), se equivoca con probabilidad a lo sumo 1/21/2.
  • Repetir kk veces baja el error a 2−k2^{-k}. Con 100 repeticiones es menos probable que un fallo del hardware.
  • BPP: tiempo polinomial y error a lo sumo 1/31/3. La constante no importa, por amplificación; se enuncia la cota.
  • Otro ejemplo: comprobar si dos polinomios son iguales evaluándolos en un punto al azar.
  • P⊆BPP⊆PSPACE\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{PSPACE}. Se cree que P=BPP\mathsf{P} = \mathsf{BPP}: el azar ayudaría en la práctica, y no en lo que se puede calcular.
  • Qué sigue abierto: P frente a NP, NP frente a coNP, P frente a PSPACE, L frente a NL. Qué cambiaría con cada respuesta.
  • Lo que queda fuera del curso, en una diapositiva cada uno: demostraciones interactivas e IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}, criptografía, computación cuántica.
  • Repaso: el mapa completo, de los lenguajes regulares a lo no reconocible, con un lenguaje que separa cada nivel y la técnica que lo demuestra.
  • Error común: creer que un algoritmo probabilístico “a veces da la respuesta equivocada sin que se pueda controlar”. El error se fija tan pequeño como se quiera.

Laboratorio — Verificar un producto de matrices al azar

  1. Leer tres matrices AA, BB y CC de n×nn \times n y responder si A⋅B=CA \cdot B = C, con el algoritmo de Freivalds repetido kk veces.
  2. Usar aritmética módulo un primo grande para evitar el overflow.
  3. Pasar el caso grande, en el que multiplicar las matrices en O(n3)O(n^3) da TLE.
  4. Con una CC que difiere en una sola posición, medir en 1000 ejecuciones con k=1k = 1 cuántas veces el algoritmo se equivoca, y comparar con la cota 1/21/2.
  5. Repetir con k=2k = 2, 5 y 10, y anotar la tabla.

Preguntas de repaso

  1. ¿En qué se parece la demostración del teorema de jerarquía a la de que ATMA_{\mathrm{TM}} es indecidible? ¿Qué se agrega?
  2. De la cadena L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME}, ¿qué pares de clases se sabe que son distintos?
  3. Demuestren que si A⋅B≠CA \cdot B \neq C, un vector al azar de ceros y unos detecta la diferencia con probabilidad al menos 1/21/2.
  4. ¿Cuántas repeticiones hacen falta para que el error sea menor que 10−910^{-9}?
  5. Elijan una de las preguntas abiertas y expliquen qué consecuencia tendría cada una de sus dos respuestas.

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (9)Pruebas (4)Laboratorio (4)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

diagonal_demo.cppDescargar diagonal_demo.cpp
// La tabla de la diagonal con seis decididores y las seis primeras cadenas binarias.
//
//   build/diagonal_demo
#include <cstdio>

#include "diagonal.h"

int main() {
    const std::vector<Decider> machines = sample_machines();
    const std::vector<std::string> strings = first_strings(machines.size());
    const std::vector<std::vector<bool>> table = answer_table(machines, strings);
    const std::vector<bool> d = diagonal_row(table);

    std::printf("%-22s", "");
    for (const std::string& w : strings) {
        std::printf(" %4s", w.empty() ? "ε" : w.c_str());
    }
    std::printf("\n");
    for (std::size_t i = 0; i < table.size(); i++) {
        std::printf("%-22s", machines[i].name.c_str());
        for (std::size_t j = 0; j < table[i].size(); j++) {
            // La casilla de la diagonal va entre corchetes.
            std::printf(i == j ? "  [%s]" : "   %s ", table[i][j] ? "A" : "R");
        }
        std::printf("\n");
    }
    std::printf("%-22s", "D: lo contrario");
    for (bool accepts : d) {
        std::printf("   %s ", accepts ? "A" : "R");
    }
    std::printf("\n\n");
    for (std::size_t i = 0; i < table.size(); i++) {
        std::printf("D y M%zu responden distinto con la cadena %s.\n", i + 1,
                    strings[i].empty() ? "ε" : strings[i].c_str());
    }
}
diagonal.hDescargar diagonal.h
// La diagonal sobre una lista finita y explícita: a partir de una tabla de respuestas se arma
// una fila que difiere de cada fila de la tabla en la casilla de la diagonal.
#pragma once

#include <cstddef>
#include <string>
#include <vector>

// Un decididor de juguete: un nombre y una función que acepta o rechaza cada cadena.
struct Decider {
    std::string name;
    bool (*accepts)(const std::string&);
};

// Las primeras n cadenas binarias en el orden de la semana 1: por longitud y, a igual longitud,
// en el orden del alfabeto. La cadena vacía es "".
inline std::vector<std::string> first_strings(std::size_t n) {
    std::vector<std::string> result;
    for (std::size_t length = 0; result.size() < n; length++) {
        for (std::size_t value = 0; value < (std::size_t{1} << length) && result.size() < n; value++) {
            std::string w(length, '0');
            for (std::size_t i = 0; i < length; i++) {
                if ((value >> (length - 1 - i)) & 1u) {
                    w[i] = '1';
                }
            }
            result.push_back(w);
        }
    }
    return result;
}

// table[i][j] dice si la máquina i acepta la cadena j.
inline std::vector<std::vector<bool>> answer_table(const std::vector<Decider>& machines,
                                                   const std::vector<std::string>& strings) {
    std::vector<std::vector<bool>> table;
    for (const Decider& m : machines) {
        std::vector<bool> row;
        for (const std::string& w : strings) {
            row.push_back(m.accepts(w));
        }
        table.push_back(row);
    }
    return table;
}

// La fila de D: con la cadena i hace lo contrario de lo que la máquina i hace con la cadena i.
inline std::vector<bool> diagonal_row(const std::vector<std::vector<bool>>& table) {
    std::vector<bool> row;
    for (std::size_t i = 0; i < table.size(); i++) {
        row.push_back(!table[i][i]);
    }
    return row;
}

// Seis decididores sencillos, para tener una lista concreta.
inline std::vector<Decider> sample_machines() {
    return {
        {"M1: acepta todo", [](const std::string&) { return true; }},
        {"M2: no acepta nada", [](const std::string&) { return false; }},
        {"M3: longitud par", [](const std::string& w) { return w.size() % 2 == 0; }},
        {"M4: termina en 1", [](const std::string& w) { return !w.empty() && w.back() == '1'; }},
        {"M5: contiene un 0", [](const std::string& w) { return w.find('0') != std::string::npos; }},
        {"M6: empieza con 1", [](const std::string& w) { return !w.empty() && w.front() == '1'; }},
    };
}
freivalds_demo.cppDescargar freivalds_demo.cpp
// Freivalds a mano: una matriz C que difiere de A·B, y lo que ve cada uno de los 2^n vectores
// de ceros y unos. Los números son pequeños para poder seguirlos; se calcula módulo 10^9 + 7,
// que aquí no cambia nada porque ningún resultado llega a ese tamaño.
//
//   build/freivalds_demo
#include <cstdio>
#include <string>

#include "freivalds.h"

std::string show(const Vector& v) {
    std::string s = "(";
    for (std::size_t i = 0; i < v.size(); i++) {
        s += (i > 0 ? ", " : "") + std::to_string(v[i]);
    }
    return s + ")";
}

void print_matrix(const char* name, const Matrix& m) {
    for (std::size_t i = 0; i < m.size(); i++) {
        std::printf("%s", i == 0 ? name : "     ");
        for (std::uint64_t x : m[i]) {
            std::printf(" %3llu", static_cast<unsigned long long>(x));
        }
        std::printf("\n");
    }
}

// Prueba los 2^n vectores y devuelve cuántos detectan que A·B ≠ C.
int try_all_vectors(const Matrix& a, const Matrix& b, const Matrix& c) {
    const std::size_t n = a.size();
    int detected = 0;
    std::printf("  r           B·r            A·(B·r)         C·r             ¿detecta?\n");
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        Vector r(n);
        for (std::size_t j = 0; j < n; j++) {
            r[j] = (mask >> (n - 1 - j)) & 1u;
        }
        const Vector br = times(b, r, kPrime);
        const Vector abr = times(a, br, kPrime);
        const Vector cr = times(c, r, kPrime);
        const bool differs = abr != cr;
        detected += differs ? 1 : 0;
        std::printf("  %-11s %-14s %-15s %-15s %s\n", show(r).c_str(), show(br).c_str(), show(abr).c_str(),
                    show(cr).c_str(), differs ? "sí" : "no");
    }
    return detected;
}

int main() {
    const Matrix a = {{1, 2, 0}, {0, 1, 3}, {2, 0, 1}};
    const Matrix b = {{2, 1, 0}, {1, 0, 2}, {0, 3, 1}};
    const Matrix product = multiply(a, b, kPrime);
    print_matrix("A   =", a);
    print_matrix("B   =", b);
    print_matrix("A·B =", product);

    // C1: una sola entrada cambiada, la de la fila 2 y la columna 3.
    Matrix c1 = product;
    c1[1][2] += 1;
    std::printf("\nC1: igual a A·B salvo la entrada (2, 3), que vale %llu en vez de %llu.\n",
                static_cast<unsigned long long>(c1[1][2]), static_cast<unsigned long long>(product[1][2]));
    const int d1 = try_all_vectors(a, b, c1);
    std::printf("  Detectan la diferencia %d de 8 vectores.\n", d1);

    // C2: dos entradas cambiadas en la misma fila, una en +1 y otra en -1.
    Matrix c2 = product;
    c2[0][0] += 1;
    c2[0][1] -= 1;
    std::printf("\nC2: en la fila 1, la entrada (1, 1) vale uno más y la (1, 2) uno menos.\n");
    const int d2 = try_all_vectors(a, b, c2);
    std::printf("  Detectan la diferencia %d de 8 vectores.\n", d2);

    // C3: una entrada cambiada en cada fila, en columnas distintas.
    Matrix c3 = product;
    c3[0][0] += 1;
    c3[1][1] += 1;
    c3[2][2] += 1;
    std::printf("\nC3: las tres entradas de la diagonal valen uno más.\n");
    const int d3 = try_all_vectors(a, b, c3);
    std::printf("  Detectan la diferencia %d de 8 vectores.\n", d3);
}
freivalds_experiment.cppDescargar freivalds_experiment.cpp
// El experimento de la semana: ¿cuántas veces se equivoca Freivalds con k rondas?
// Se arma una C que difiere de A·B en una sola posición y se corre el algoritmo 1000 veces por
// cada k. Un fallo es responder "iguales". La semilla es fija, así que la tabla sale siempre igual.
//
//   build/freivalds_experiment [semilla]
#include <cmath>
#include <cstdio>
#include <cstdlib>

#include "freivalds.h"

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

    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;

    std::printf("n = %zu, p = %llu, semilla = %llu, %d ejecuciones por fila\n", n,
                static_cast<unsigned long long>(kPrime), static_cast<unsigned long long>(seed), runs);
    std::printf("C difiere de A·B solo en la entrada (18, 5).\n\n");
    std::printf(" k   fallos   fracción   cota 2^-k\n");
    for (int k : {1, 2, 5, 10}) {
        const int failures = count_equal_answers(a, b, wrong, k, runs, rng, kPrime);
        std::printf("%2d   %6d   %8.3f   %9.6f\n", k, failures, static_cast<double>(failures) / runs,
                    std::pow(0.5, k));
    }

    // El otro lado: si C es de verdad A·B, ninguna ronda puede encontrar una diferencia.
    const int false_alarms = runs - count_equal_answers(a, b, product, 10, runs, rng, kPrime);
    std::printf("\nCon C = A·B y k = 10: %d respuestas \"distintos\" en %d ejecuciones.\n", false_alarms, runs);
}
freivalds.hDescargar freivalds.h
// Matrices módulo p y el algoritmo de Freivalds: comprobar si A·B = C sin multiplicar A por B.
// Todo se calcula módulo p. Las entradas de las matrices están en {0, ..., p - 1}.
#pragma once

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <random>
#include <vector>

using Vector = std::vector<std::uint64_t>;
using Matrix = std::vector<Vector>;

// El primo de la semana: 10^9 + 7. Es menor que 2^30.
constexpr std::uint64_t kPrime = 1'000'000'007;

// a·b módulo p. Con a, b < p < 2^32, el producto es menor que 2^64 y cabe en 64 bits sin signo.
// En 32 bits no cabe: (p - 1)·(p - 1) tiene unas 18 cifras.
inline std::uint64_t mul_mod(std::uint64_t a, std::uint64_t b, std::uint64_t p) {
    assert(p < (std::uint64_t{1} << 32) && a < p && b < p);
    return a * b % p;
}

// El producto de una matriz de n×n por un vector: n² multiplicaciones.
inline Vector times(const Matrix& m, const Vector& x, std::uint64_t p) {
    Vector y(m.size(), 0);
    for (std::size_t i = 0; i < m.size(); i++) {
        for (std::size_t j = 0; j < x.size(); j++) {
            y[i] = (y[i] + mul_mod(m[i][j], x[j], p)) % p;
        }
    }
    return y;
}

// El producto exacto de dos matrices de n×n, por la definición: n³ multiplicaciones.
inline Matrix multiply(const Matrix& a, const Matrix& b, std::uint64_t p) {
    const std::size_t n = a.size();
    Matrix c(n, Vector(n, 0));
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = 0; j < n; j++) {
            for (std::size_t k = 0; k < n; k++) {
                c[i][j] = (c[i][j] + mul_mod(a[i][k], b[k][j], p)) % p;
            }
        }
    }
    return c;
}

// Una ronda con el vector r: ¿A·(B·r) = C·r? Son tres productos de matriz por vector.
// Si devuelve false, es seguro que A·B ≠ C. Si devuelve true, no se sabe.
inline bool freivalds_round(const Matrix& a, const Matrix& b, const Matrix& c, const Vector& r,
                            std::uint64_t p) {
    return times(a, times(b, r, p), p) == times(c, r, p);
}

// Un vector de n ceros y unos, cada uno con una moneda independiente: el bit más alto de un
// número de 64 bits del generador.
inline Vector random_bits(std::size_t n, std::mt19937_64& rng) {
    Vector r(n);
    for (std::uint64_t& bit : r) {
        bit = rng() >> 63;
    }
    return r;
}

// Freivalds con k rondas. Devuelve false ("distintos") apenas una ronda encuentra una diferencia,
// y true ("iguales") si ninguna la encuentra. Solo se puede equivocar al responder true.
inline bool freivalds(const Matrix& a, const Matrix& b, const Matrix& c, int k, std::mt19937_64& rng,
                      std::uint64_t p) {
    for (int round = 0; round < k; round++) {
        if (!freivalds_round(a, b, c, random_bits(a.size(), rng), p)) {
            return false;
        }
    }
    return true;
}

// Corre Freivalds con k rondas `runs` veces y cuenta cuántas responde "iguales".
// Si A·B ≠ C, ese número es la cantidad de fallos.
inline int count_equal_answers(const Matrix& a, const Matrix& b, const Matrix& c, int k, int runs,
                               std::mt19937_64& rng, std::uint64_t p) {
    int count = 0;
    for (int run = 0; run < runs; run++) {
        count += freivalds(a, b, c, k, rng, p) ? 1 : 0;
    }
    return count;
}

// Cuántos de los 2^n vectores de ceros y unos detectan que A·B ≠ C. Solo para n pequeño.
inline int count_detecting_vectors(const Matrix& a, const Matrix& b, const Matrix& c, std::uint64_t p) {
    const std::size_t n = a.size();
    assert(n < 20);
    int detected = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        Vector r(n);
        for (std::size_t j = 0; j < n; j++) {
            r[j] = (mask >> (n - 1 - j)) & 1u;
        }
        detected += freivalds_round(a, b, c, r, p) ? 0 : 1;
    }
    return detected;
}

// Una matriz de n×n con entradas al azar en {0, ..., p - 1}.
// rng() % p no es exactamente uniforme, pero el sesgo es menor que 2^-33 y aquí no importa.
inline Matrix random_matrix(std::size_t n, std::mt19937_64& rng, std::uint64_t p) {
    Matrix m(n, Vector(n));
    for (Vector& row : m) {
        for (std::uint64_t& x : row) {
            x = rng() % p;
        }
    }
    return m;
}
majority_table.cppDescargar majority_table.cpp
// Amplificación por mayoría: un algoritmo se equivoca con probabilidad 1/3 en cada ejecución.
// Se corre k veces, con k impar, y se responde lo que diga la mayoría. Este programa calcula la
// probabilidad exacta de que la mayoría se equivoque y la compara con la cota (8/9)^(k/2).
//
//   build/majority_table
#include <cmath>
#include <cstdio>

#include "majority.h"

int main() {
    const double error = 1.0 / 3.0;
    std::printf("  k   la mayoría se equivoca   cota (8/9)^(k/2)\n");
    for (int k : {1, 5, 11, 25, 51, 101, 201}) {
        std::printf("%3d   %22.3e   %16.3e\n", k, majority_error(k, error), std::pow(8.0 / 9.0, k / 2.0));
    }
}
majority.hDescargar majority.h
// La probabilidad exacta de que la mayoría de k ejecuciones independientes se equivoque, cuando
// cada una se equivoca con probabilidad `error`.
#pragma once

#include <cstddef>
#include <vector>

// Suma, para cada i > k/2, la probabilidad de que se equivoquen exactamente i de las k:
// C(k, i) · error^i · (1 - error)^(k - i). Las probabilidades de "exactamente i" se calculan
// agregando las ejecuciones una por una, sin factoriales.
inline double majority_error(int k, double error) {
    std::vector<double> exactly(static_cast<std::size_t>(k) + 1, 0.0);  // exactly[i]: fallan i de las vistas
    exactly[0] = 1.0;
    for (int run = 1; run <= k; run++) {
        for (int i = run; i >= 1; i--) {
            exactly[i] = exactly[i] * (1.0 - error) + exactly[i - 1] * error;
        }
        exactly[0] *= 1.0 - error;
    }
    double total = 0.0;
    for (int i = k / 2 + 1; i <= k; i++) {
        total += exactly[i];
    }
    return total;
}
pit_demo.cppDescargar pit_demo.cpp
// 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);
}
pit.hDescargar pit.h
// Polinomios en una variable con coeficientes módulo p, y la prueba de identidad al azar:
// dos polinomios distintos de grado a lo sumo d coinciden en a lo sumo d puntos.
#pragma once

#include <cstddef>
#include <cstdint>
#include <random>
#include <vector>

#include "freivalds.h"  // mul_mod

// Un polinomio por sus coeficientes: coefficients[i] es el de x^i, en {0, ..., p - 1}.
struct Polynomial {
    std::vector<std::uint64_t> coefficients;
};

// Un polinomio por sus factores: (x - roots[0])·(x - roots[1])···
struct Factored {
    std::vector<std::uint64_t> roots;
};

// Evalúa con la regla de Horner: d multiplicaciones para grado d.
inline std::uint64_t evaluate(const Polynomial& f, std::uint64_t x, std::uint64_t p) {
    std::uint64_t value = 0;
    for (std::size_t i = f.coefficients.size(); i > 0; i--) {
        value = (mul_mod(value, x, p) + f.coefficients[i - 1]) % p;
    }
    return value;
}

// Evalúa el producto factor por factor, sin desarrollarlo: d multiplicaciones.
inline std::uint64_t evaluate(const Factored& f, std::uint64_t x, std::uint64_t p) {
    std::uint64_t value = 1 % p;
    for (std::uint64_t root : f.roots) {
        value = mul_mod(value, (x + p - root % p) % p, p);
    }
    return value;
}

// Desarrolla el producto: multiplica por (x - raíz) una vez por cada factor.
inline Polynomial expand(const Factored& f, std::uint64_t p) {
    Polynomial result{{1 % p}};
    for (std::uint64_t root : f.roots) {
        const std::uint64_t minus_root = (p - root % p) % p;
        std::vector<std::uint64_t> next(result.coefficients.size() + 1, 0);
        for (std::size_t i = 0; i < result.coefficients.size(); i++) {
            next[i + 1] = (next[i + 1] + result.coefficients[i]) % p;
            next[i] = (next[i] + mul_mod(result.coefficients[i], minus_root, p)) % p;
        }
        result.coefficients = next;
    }
    return result;
}

// La prueba: evaluar los dos en un punto al azar de {0, ..., p - 1}.
// false: son distintos, con seguridad. true: coinciden en ese punto, y no se sabe más.
template <typename F, typename G>
bool agree_at_random_point(const F& f, const G& g, std::mt19937_64& rng, std::uint64_t p) {
    const std::uint64_t x = rng() % p;
    return evaluate(f, x, p) == evaluate(g, x, p);
}

// En cuántos de los p puntos coinciden. Solo para p pequeño.
template <typename F, typename G>
std::uint64_t count_agreements(const F& f, const G& g, std::uint64_t p) {
    std::uint64_t count = 0;
    for (std::uint64_t x = 0; x < p; x++) {
        count += evaluate(f, x, p) == evaluate(g, x, p) ? 1 : 0;
    }
    return count;
}

// Corre la prueba `runs` veces y cuenta cuántas responde "coinciden".
template <typename F, typename G>
int count_agree_answers(const F& f, const G& g, int runs, std::mt19937_64& rng, std::uint64_t p) {
    int count = 0;
    for (int run = 0; run < runs; run++) {
        count += agree_at_random_point(f, g, rng, p) ? 1 : 0;
    }
    return count;
}

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_diagonal.cppDescargar test_diagonal.cpp
// Pruebas de diagonal.h: la fila de D difiere de cada fila de la tabla en la diagonal.
#include <cassert>
#include <cstdio>

#include "diagonal.h"

int main() {
    const std::vector<std::string> expected = {"", "0", "1", "00", "01", "10", "11", "000"};
    assert(first_strings(8) == expected);
    assert(first_strings(0).empty());

    const std::vector<Decider> machines = sample_machines();
    const std::vector<std::string> strings = first_strings(machines.size());
    const std::vector<std::vector<bool>> table = answer_table(machines, strings);
    const std::vector<bool> d = diagonal_row(table);
    assert(table.size() == 6 && d.size() == 6);

    // La fila que muestran los apuntes: R A A A R R.
    const std::vector<bool> shown = {false, true, true, true, false, false};
    assert(d == shown);

    // D no es ninguna de las seis: con la cadena i responde distinto que la máquina i.
    for (std::size_t i = 0; i < table.size(); i++) {
        assert(d[i] != table[i][i]);
        assert(d != table[i]);
    }
    std::printf("test_diagonal: correcto\n");
}
test_freivalds.cppDescargar test_freivalds.cpp
// 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");
}
test_majority.cppDescargar test_majority.cpp
// Pruebas de majority.h: la probabilidad exacta de que la mayoría se equivoque y su cota.
#include <cassert>
#include <cmath>
#include <cstdio>

#include "majority.h"

bool close(double a, double b) {
    return std::fabs(a - b) <= 1e-9 * std::fabs(b) + 1e-15;
}

int main() {
    const double error = 1.0 / 3.0;
    // Con una ejecución, la mayoría es esa ejecución.
    assert(close(majority_error(1, error), 1.0 / 3.0));
    // Con tres: fallan las tres, o exactamente dos. 1/27 + 3 · (1/9) · (2/3) = 7/27.
    assert(close(majority_error(3, error), 7.0 / 27.0));
    // Con cinco: (1 + 5·2 + 10·4) / 243 = 51/243.
    assert(close(majority_error(5, error), 51.0 / 243.0));
    // Una moneda justa no mejora: la mayoría de k impar se equivoca la mitad de las veces.
    assert(close(majority_error(101, 0.5), 0.5));
    // La cota (8/9)^(k/2) se cumple, y el error baja al aumentar k.
    double previous = 1.0;
    for (int k = 1; k <= 301; k += 2) {
        const double exact = majority_error(k, error);
        assert(exact <= std::pow(8.0 / 9.0, k / 2.0));
        assert(exact < previous);
        previous = exact;
    }
    // Los valores de la tabla de los apuntes, con tres cifras.
    assert(std::fabs(majority_error(11, error) - 0.1221) < 5e-5);
    assert(std::fabs(majority_error(51, error) - 6.888e-3) < 5e-7);
    assert(std::fabs(majority_error(101, error) - 2.724e-4) < 5e-8);
    assert(std::fabs(majority_error(201, error) - 5.531e-7) < 5e-11);
    std::printf("test_majority: correcto\n");
}
test_pit.cppDescargar test_pit.cpp
// Pruebas de pit.h: el desarrollo, la evaluación y los números de pit_demo.
#include <cassert>
#include <cstdio>

#include "pit.h"

Factored one_to_ten() {
    Factored f;
    for (std::uint64_t root = 1; root <= 10; root++) {
        f.roots.push_back(root);
    }
    return f;
}

void test_expand() {
    const Factored small{{1, 2, 3, 4}};
    const Polynomial expanded = expand(small, kPrime);
    // x^4 - 10x^3 + 35x^2 - 50x + 24
    const std::vector<std::uint64_t> expected = {24, kPrime - 50, 35, kPrime - 10, 1};
    assert(expanded.coefficients == expected);
    assert(evaluate(small, 7, kPrime) == 360);
    assert(evaluate(expanded, 7, kPrime) == 360);
    // Un producto vacío vale 1, y el polinomio sin coeficientes vale 0.
    assert(evaluate(Factored{}, 5, kPrime) == 1);
    assert(evaluate(Polynomial{}, 5, kPrime) == 0);
    assert(expand(Factored{}, kPrime).coefficients == std::vector<std::uint64_t>{1});
}

// Las dos formas del mismo polinomio coinciden en todos los puntos, con cualquier módulo.
void test_same_polynomial() {
    const Factored f = one_to_ten();
    for (std::uint64_t p : {std::uint64_t{101}, std::uint64_t{7}, kPrime}) {
        const Polynomial expanded = expand(f, p);
        assert(expanded.coefficients.size() == 11);
        for (std::uint64_t x = 0; x < 200 && x < p; x++) {
            assert(evaluate(f, x, p) == evaluate(expanded, x, p));
        }
    }
}

// Dos polinomios distintos de grado a lo sumo 10 coinciden en a lo sumo 10 puntos de los 101.
void test_agreement_counts() {
    const std::uint64_t p = 101;
    const Factored f = one_to_ten();
    const Polynomial expanded = expand(f, p);
    assert(count_agreements(f, expanded, p) == 101);
    Polynomial one_wrong = expanded;
    one_wrong.coefficients[3] = (one_wrong.coefficients[3] + 1) % p;
    assert(count_agreements(f, one_wrong, p) == 1);    // la diferencia es x³: solo se anula en 0
    assert(count_agreements(f, Polynomial{{0}}, p) == 10);  // las raíces 1, ..., 10
    // Cualquier cambio en los coeficientes deja a lo sumo 10 coincidencias.
    std::mt19937_64 rng(7);
    for (int trial = 0; trial < 300; trial++) {
        Polynomial g = expanded;
        std::uint64_t& c = g.coefficients[rng() % g.coefficients.size()];
        c = (c + 1 + rng() % (p - 1)) % p;
        assert(count_agreements(f, g, p) <= 10);
    }
}

// Los conteos de pit_demo, con la misma semilla y el mismo orden.
void test_demo_table() {
    std::mt19937_64 rng(2015);
    const Factored f = one_to_ten();
    const int expected[2][3] = {{1000, 10, 102}, {1000, 0, 0}};
    int row = 0;
    for (std::uint64_t p : {std::uint64_t{101}, kPrime}) {
        const Polynomial expanded = expand(f, p);
        Polynomial one_wrong = expanded;
        one_wrong.coefficients[3] = (one_wrong.coefficients[3] + 1) % p;
        assert(count_agree_answers(f, expanded, 1000, rng, p) == expected[row][0]);
        assert(count_agree_answers(f, one_wrong, 1000, rng, p) == expected[row][1]);
        assert(count_agree_answers(f, Polynomial{{0}}, 1000, rng, p) == expected[row][2]);
        row++;
    }
}

int main() {
    test_expand();
    test_same_polynomial();
    test_agreement_counts();
    test_demo_table();
    std::printf("test_pit: correcto\n");
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/freivalds/experiment.cppDescargar lab/freivalds/experiment.cpp
// 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;
}
lab/freivalds/MakefileDescargar lab/freivalds/Makefile
TIEMPO = 3
include ../../../lab.mk
lab/freivalds/README.mdDescargar lab/freivalds/README.md
# Verificar un producto de matrices al azar

Alguien les entrega tres matrices $A$, $B$ y $C$ de $n \times n$ y afirma que $C = A \cdot B$. Comprobarlo
multiplicando cuesta $n^3$ operaciones. Con el algoritmo de Freivalds se comprueba con $O(n^2)$ por ronda,
lanzando monedas, y con una probabilidad de error que ustedes eligen.

Todas las cuentas de este problema son **módulo el primo $p = 10^9 + 7 = 1\,000\,000\,007$**. Las entradas de
las matrices son restos, entre 0 y $p - 1$, y la pregunta es si cada entrada de $A \cdot B$, reducida módulo
$p$, es igual a la entrada correspondiente de $C$.

## Entrada

La primera línea tiene $n$. Siguen $3n$ líneas con $n$ números cada una, separados por espacios: las $n$ filas
de $A$, después las $n$ filas de $B$ y después las $n$ filas de $C$.

```text
2
1 2
3 4
5 6
7 8
19 22
43 50
```

## Salida

Una sola línea: `iguales` si $A \cdot B = C$ módulo $p$, y `distintos` si no.

## Límites

- $1 \leq n \leq 2000$.
- Todas las entradas de $A$, $B$ y $C$ son enteros entre 0 y $p - 1 = 1\,000\,000\,006$.
- La entrada tiene siempre el formato descrito: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba la salida es:

```text
iguales
```

porque

$$
\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \cdot \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix} = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix}.
$$

Es el caso `casos/01.in`. El caso `casos/02.in` es igual salvo la última entrada de $C$, que vale 51, y su
salida es:

```text
distintos
```

## Tiempo

3 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

En los dos casos grandes $n = 2000$. Calcular $A \cdot B$ por la definición son $n^3 = 8 \cdot 10^9$
multiplicaciones con su reducción módulo $p$, y el juez da `TLE`. Una ronda de Freivalds son tres productos de
matriz por vector: $3n^2 = 1{,}2 \cdot 10^7$ operaciones.

## El algoritmo

Una ronda:

1. Elegir un vector $r$ de $n$ coordenadas, cada una 0 o 1 con una moneda independiente.
2. Calcular $x = B \cdot r$, después $y = A \cdot x$, y aparte $z = C \cdot r$. Todo módulo $p$.
3. Si $y \neq z$, la respuesta es `distintos`, con seguridad.

Si $A \cdot B \neq C$, una ronda lo detecta con probabilidad al menos $1/2$: está demostrado en los apuntes de
la semana 15. Repitan la ronda **$k = 30$ veces**, con monedas nuevas cada vez, y respondan `iguales` solo si
ninguna encontró una diferencia. La probabilidad de responder `iguales` por error es a lo sumo
$2^{-30} < 10^{-9}$.

Eso quiere decir que una solución correcta puede, en principio, recibir un `WA`. Hay 11 casos con respuesta
`distintos`, así que la probabilidad de que el juez le marque algún error a una solución correcta es menor que
$11 \cdot 10^{-9}$ por cada vez que lo corren. Si ven un `WA`, no es eso: busquen el error.

## Cuidado con el overflow

- Una entrada es menor que $p < 2^{30}$ y cabe en 32 bits.
- El producto de dos entradas llega a $(p - 1)^2 \approx 10^{18}$. **No cabe en 32 bits**, y sí en 64 bits
  sin signo, que llegan hasta $1{,}8 \cdot 10^{19}$. Conviertan a `std::uint64_t` **antes** de multiplicar:
  `std::uint64_t{a} * b`, y no `a * b` guardado después en una variable de 64 bits.
- Al sumar productos, reduzcan módulo $p$ antes de que la suma pase de $2^{64}$. Lo más simple es reducir
  después de cada suma.
- Las coordenadas de $B \cdot r$ ya son restos módulo $p$, y no ceros y unos: en $A \cdot (B \cdot r)$ hay
  productos de verdad.

Los casos `05` y `11` tienen entradas iguales a $p - 1$ para que un producto en 32 bits no pase.

## Qué trae el esqueleto

`solution.cpp` ya lee la entrada, y deja las tres matrices en vectores de `std::uint32_t` guardados por filas:
la entrada $(i, j)$ de una matriz `m` está en `m[i * n + j]`. La lectura usa un lector por bloques, porque en
los casos grandes hay 12 millones de números y leerlos uno por uno con `std::cin` tarda más que todo el
algoritmo. No hace falta tocarlo.

Falta la función `probably_equal`. Tal como está, responde siempre `iguales`, y el juez da `WA` en los casos
con respuesta `distintos`.

En `code/week-15/freivalds.h` hay una versión del algoritmo, la que usan los ejemplos de los apuntes. Pueden
leerla. Está escrita para que se parezca a la definición y no para ser rápida, con un vector por fila y una
división en cada operación; `solution.cpp` se escribe **sin incluirla**, porque el juez compila ese único
archivo.

## Cómo avanzar

```sh
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

Los dos casos grandes no están guardados: `make test` los genera con `casos/gen_19.cpp` y `casos/gen_20.cpp`.
Ocupan unos 120 MB cada uno en `build/casos/`; `make clean` los borra.

1. Escriban una ronda de Freivalds y pasen `casos/01.in` y `casos/02.in`. Hagan primero a mano el caso `02`
   con $r = (0, 1)$ y con $r = (1, 0)$: ¿cuál de los dos detecta la diferencia, y por qué?
2. Pongan la aritmética módulo $p$ y pasen los casos pequeños. Antes de correr el juez, respondan: ¿cuánto vale
   $(p - 1) \cdot (p - 1)$ módulo $p$? Es el caso `05`.
3. Repitan la ronda 30 veces y pasen los casos grandes. Si alguno da `TLE`, cuenten cuántas operaciones hace
   su programa por ronda: tienen que ser unas $3n^2$.

Los casos traen, entre otros: matrices de $1 \times 1$; una matriz $A$ nula; la identidad; entradas iguales a
$p - 1$; una $C$ que es $B \cdot A$ en vez de $A \cdot B$; diferencias en una sola entrada, la primera o la
última; y dos casos (`07` y `17`) en los que cada fila de $C$ tiene dos entradas cambiadas, una en $+d$ y otra
en $-d$, de modo que la suma de cada fila queda igual. En esos, el vector de solo unos no ve nada: no reemplacen
las monedas por un vector fijo.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Medir el error con una ronda

Este es el paso 4 de la guía. El archivo `experiment.cpp` arma dos matrices de $40 \times 40$ y una $C$ que
difiere de $A \cdot B$ en **una sola entrada**, que es el peor caso para el algoritmo. Después corre 1000 veces
"$k$ rondas" y cuenta en cuántas ninguna ronda detectó la diferencia. No lee nada de la entrada.

Copien en la función `round_detects` de ese archivo su ronda de Freivalds: tiene que elegir el vector con el
generador `rng` que recibe y devolver `true` si $A \cdot (B \cdot r) \neq C \cdot r$.

```sh
g++ -Wall -Wextra -std=c++20 -O2 experiment.cpp -o build/experiment
build/experiment
```

Tal como viene, la función no detecta nunca nada, y la tabla lo muestra:

```text
semilla 1, 1000 ejecuciones por fila
 k   fallos   fracción   cota 2^-k
 1     1000      1.000    0.500000
 2     1000      1.000    0.250000
 5     1000      1.000    0.031250
10     1000      1.000    0.000977
```

Con su ronda, miren la fila de $k = 1$. Respondan:

- ¿Cuántos fallos esperaban en 1000 ejecuciones, según la cota $1/2$? ¿Cuántos salieron?
- Corran con otras semillas: `build/experiment 2`, `build/experiment 3`. ¿Cuánto cambia el número?
- La cota dice "a lo sumo $1/2$". ¿Por qué aquí la fracción no sale mucho menor que $1/2$? Miren en los
  apuntes qué pasa cuando la diferencia está en una sola entrada.

Si la fila de $k = 1$ da una fracción muy lejos de $0{,}5$, hay un error: en la ronda, o en cómo se sacan los
bits del generador. Por ejemplo, si todas las coordenadas de $r$ salen del mismo número al azar sin separar sus
bits, las monedas dejan de ser independientes.

## Repetir: k = 2, 5 y 10

Este es el paso 5. El mismo programa llena las otras tres filas. Anoten la tabla y compárenla con la columna
de la cota.

- Con $k = 2$, 5 y 10 se esperan cerca de $1000 \cdot 2^{-k}$ fallos: 250, 31 y 1. ¿Qué obtuvieron?
- Con $k = 10$ lo más probable es ver 0, 1 o 2 fallos. ¿Cuántas ejecuciones habría que hacer para esperar ver
  un fallo con $k = 30$?
- Cambien `experiment.cpp` para que $C$ difiera de $A \cdot B$ en **todas** las entradas de una fila. ¿Qué pasa
  con la fracción de fallos de $k = 1$? ¿Contradice la cota?

## Para seguir

Opcional, sin casos en el juez.

- La variante con $r$ en todo el rango: elijan cada coordenada de $r$ al azar entre 0 y $p - 1$, y no solo
  entre 0 y 1. Es el ejercicio 8 de los apuntes: entonces una ronda falla con probabilidad a lo sumo
  $1/p \approx 10^{-9}$. ¿Cuántas rondas hacen falta ahora para el error de 30 rondas con ceros y unos? ¿Qué
  se pierde en velocidad en el cálculo de $B \cdot r$ y de $C \cdot r$?
- Cuando la respuesta es `distintos`, impriman además una fila $i$ en la que $A \cdot B$ y $C$ difieren. El
  vector $A \cdot (B \cdot r) - C \cdot r$ ya dice cuál. ¿Cómo encontrarían también la columna, sin multiplicar
  las matrices?
lab/freivalds/solution.cppDescargar lab/freivalds/solution.cpp
// Verificar un producto de matrices al azar: ¿A·B = C módulo p = 10^9 + 7?
// La lectura ya está escrita. Falta el algoritmo de Freivalds, en probably_equal.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <iostream>
#include <random>
#include <vector>

const std::uint64_t kPrime = 1'000'000'007;
const int kRounds = 30;

// Lee enteros sin signo de la entrada estándar por bloques. Con 12 millones de números, leerlos
// uno por uno con std::cin tarda más que todo el algoritmo.
struct Reader {
    std::vector<char> buffer = std::vector<char>(1 << 16);
    std::size_t size = 0;
    std::size_t position = 0;

    // El siguiente carácter de la entrada, o -1 si ya no hay más.
    int next_char() {
        if (position == size) {
            size = std::fread(buffer.data(), 1, buffer.size(), stdin);
            position = 0;
            if (size == 0) {
                return -1;
            }
        }
        return static_cast<unsigned char>(buffer[position++]);
    }

    // El siguiente número: salta lo que no sea un dígito y junta los dígitos seguidos.
    std::uint32_t next_number() {
        int c = next_char();
        while (c != -1 && (c < '0' || c > '9')) {
            c = next_char();
        }
        std::uint32_t value = 0;
        while (c >= '0' && c <= '9') {
            value = value * 10 + static_cast<std::uint32_t>(c - '0');
            c = next_char();
        }
        return value;
    }
};

// Una matriz de n×n guardada por filas en un solo vector: la entrada (i, j) está en [i·n + j].
// Las entradas son menores que p < 2^30, así que caben en 32 bits. Sus productos no.
using Matrix = std::vector<std::uint32_t>;

Matrix read_matrix(Reader& in, std::size_t n) {
    Matrix m(n * n);
    for (std::uint32_t& x : m) {
        x = in.next_number();
    }
    return m;
}

// Por hacer: kRounds rondas de Freivalds. En cada una, elegir un vector r de n ceros y unos al
// azar, calcular A·(B·r) y C·r módulo kPrime, y devolver false apenas sean distintos.
// Cuidado con el overflow: el producto de dos entradas no cabe en 32 bits.
bool probably_equal(const Matrix& a, const Matrix& b, const Matrix& c, std::size_t n, std::mt19937_64& rng) {
    // Este esqueleto no hace ninguna ronda: responde siempre "iguales", y el juez da WA en los
    // casos en que la respuesta es "distintos".
    (void)a, (void)b, (void)c, (void)n, (void)rng;  // todavía no se usan
    return true;
}

int main() {
    Reader in;
    const std::size_t n = in.next_number();
    const Matrix a = read_matrix(in, n);
    const Matrix b = read_matrix(in, n);
    const Matrix c = read_matrix(in, n);

    // Para el juez sirve cualquier semilla. Con una fija, su programa responde siempre lo mismo
    // con la misma entrada, y eso ayuda a depurar.
    std::mt19937_64 rng(1);
    std::cout << (probably_equal(a, b, c, n, rng) ? "iguales" : "distintos") << "\n";
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 15: jerarquías, algoritmos probabilísticos y el repaso del curso.
# Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos, con sanitizers
#   make clean     borra lo generado
#
# El laboratorio está en lab/freivalds y tiene su propio Makefile: estas reglas no lo tocan.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = freivalds_demo freivalds_experiment pit_demo majority_table diagonal_demo
TESTS = test_freivalds test_pit test_majority test_diagonal
HEADERS = freivalds.h pit.h majority.h diagonal.h

.PHONY: all test clean

all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)

$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
	@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
	@echo "Todas las pruebas pasaron."

clean:
	rm -rf $(BUILD)