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: , y . En la cadena 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 y con y .
- ✂️ 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 sin multiplicar: el algoritmo de Freivalds, en , se equivoca con probabilidad a lo sumo .
- Repetir veces baja el error a . Con 100 repeticiones es menos probable que un fallo del hardware.
- BPP: tiempo polinomial y error a lo sumo . 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.
- . Se cree que : 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 , 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
- Leer tres matrices , y de y responder si , con el algoritmo de Freivalds repetido veces.
- Usar aritmética módulo un primo grande para evitar el overflow.
- Pasar el caso grande, en el que multiplicar las matrices en da TLE.
- Con una que difiere en una sola posición, medir en 1000 ejecuciones con cuántas veces el algoritmo se equivoca, y comparar con la cota .
- Repetir con , 5 y 10, y anotar la tabla.
Preguntas de repaso
- ¿En qué se parece la demostración del teorema de jerarquía a la de que es indecidible? ¿Qué se agrega?
- De la cadena , ¿qué pares de clases se sabe que son distintos?
- Demuestren que si , un vector al azar de ceros y unos detecta la diferencia con probabilidad al menos .
- ¿Cuántas repeticiones hacen falta para que el error sea menor que ?
- 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.
// 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());
}
}// 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 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);
}// 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);
}// 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;
}// 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));
}
}// 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;
}// 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);
}// 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.
// 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");
}// 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");
}// 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");
}// 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.
// 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;
}TIEMPO = 3
include ../../../lab.mk# 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?// 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.
# 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)