01 · Punto de partida
La misma fórmula, destinos opuestos
En el Tema 12 iteraste (5·x+3) mod 16 (período 16) y (4·x+2) mod 16 (período ≤ 4). Misma receta, mismo m, una letra distinta y un generador sirve y el otro es basura. La diferencia no es suerte: son los parámetros.
Este tema disecciona m, a, c y la semilla: qué decide cada uno, qué fallos típicos producen y qué checklist aplicar antes de adoptar un trío.
- ¿Qué tamaño de
mnecesito para mi N? - ¿Por qué
cdebe ser coprimo conm? - ¿Por qué
a = 4colapsa ya = 5funciona con m = 16? - ¿Cómo verifico overflow antes de portar a C?
02 · Rol de cada uno
Quién manda qué
Módulo m
Techo del período (≤ m) y costo del mod. Potencia de 2 = rapidísimo pero bits bajos débiles; primo grande = mejor estadística y mod más caro.
Incremento c
El «empujón» que evita puntos fijos. Para período completo debe ser coprimo con m (sin divisor común). Con m potencia de 2: c impar.
Multiplicador a
La mezcla. Controla período y estructura multidimensional (pares/triplas). Con m = 2ᵏ se exige a ≡ 1 mod 4; además conviene a ni tiny ni pegado a m.
| Parámetro | Error típico | Síntoma |
|---|---|---|
m chico | m = 16 para N = 10 000 | Vueltas calcadas, histograma de picos |
c con divisor común | m = 16, c = 2 o 4 | Período ≤ 8 aunque a sea bueno |
a malo | a = 4 con m = 16; 65539 con 2³¹ | Ciclo corto o triplas en planos |
| Overflow | a·(m−1) > 2³² en C 32 bits | Secuencia distinta a la teórica |
03 · Guía práctica
Checklist antes de adoptar
- 1. m según N
- Pedí
m ≫ N(idealm > 1000·N). Si N es millonario,m = 2³¹queda corto: migrá a moderno (Tema 17). - 2. c coprimo
mcd(c, m) = 1. Conm = 2ᵏ:cimpar. Conc = 0aceptás techom−1y semilla ≠ 0.- 3. a con teoría
- Con
m = 2ᵏ:a mod 4 = 1yalejos de 1 y dem. Nunca «redondo por velocidad» estilo RANDU sin validar espectro. - 4. Overflow
- Verificá
a·(m−1) + centra en tu entero (64 bits o Schrage). Lo que en Python anda, en C puede desbordar.
Trío sano (m = 16)
(5, 3): período 16
c impar, a mod 4 = 1: cumple el checklist y recorre todo el anillo.
Trío roto (m = 16)
(4, 2): período ≤ 4
c par y a mod 4 = 0: viola todo y colapsa a un rincón del anillo.
04 · Ejemplos
Un dígito cambia todo
- 1(5,3,16): completo.
16 estados, histograma parejo en N = 64 con 4 vueltas.
- 2(5,2,16): roto por c.
cpar comparte factor 2 con 16: el ciclo se parte. - 3(4,3,16): roto por a.
a mod 4 = 0: aunquecsea impar, no recorre todo. - 4(16807,0,2³¹−1): clásico.
Multiplicativo con primo: período m−1 si
aes raíz primitiva. Semilla ≠ 0.
05 · Barrido en Python
Probar tríos en miniatura
Con m chico podés barrer y ver el patrón que la teoría resume. Con m real no barres: aplicás el teorema.
Python en tu navegador. Barrete a 1–15 con (c=3,m=16) y anotá cuáles dan 16.
def periodo(a, c, m, semilla=7):
visto = set()
x = semilla
while x not in visto:
visto.add(x)
x = (a * x + c) % m
return len(visto)
for a in range(1, 16):
print(a, periodo(a, 3, 16))Verás 16 solo en a = 1, 5, 9, 13 (los ≡ 1 mod 4): el patrón que el laboratorio confirma.
Chequear overflow
def entra(a, c, m, bits=32):
return a * (m - 1) + c < 2**bits
print(entra(16807, 0, 2**31 - 1, 32))
print(entra(65539, 0, 2**31, 32))06 · Exploración
Laboratorio: qué rompe cada letra
Fijá m y mové a, c. El semáforo chequea c impar y a mod 4 = 1 (para m potencia de 2). El canvas muestra la secuencia y el panel el período real.
Checklist en vivo
c impar · a ≡ 1 (mod 4)
Con (5,3,16) ambas luces en verde y p = 16.
Luces verdes + período = m: trío sano. Alguna roja + período corto: letra culpable a la vista.
Preguntas para explorar
- Dejá a = 5 y poné c = 2: ¿qué luz se apaga? ¿p?
- Dejá c = 3 y poné a = 4: ¿qué luz se apaga? ¿p?
- Con m = 32, buscá un trío completo distinto de (5,3). ¿Qué patrón cumplen los
aque funcionan?
Ver respuestas sugeridas
- Se apaga
cimpar; p se parte (≤ 8). El par comparte el factor 2 con 16. - Se apaga
a mod 4; p colapsa (≤ 4–8). El multiplicador no mezcla. - Funcionan 1, 5, 9, 13, 17…: todos ≡ 1 mod 4. Es el patrón que el Tema 14 demuestra.
07 · Comprensión
Confusiones frecuentes
«m grande compensa a y c malos»
No: con m = 2³² y (4,2) sigues atrapado en un rincón minúsculo del anillo. El tamaño no cura la aritmética.
«a grande = mezcla mejor»
Un a pegado a m o con mala estructura espectral es peor que uno moderado validado. Grande no es criterio.
«c = 0 da período m»
Con c = 0 el 0 queda fuera del ciclo útil: el techo es m−1 y solo si a es raíz primitiva (primo) o cumple condiciones (potencia de 2 con restricciones).
«Cambio la semilla y zafa»
La semilla no toca el largo del ciclo ni la estructura. Si el trío es malo, todas las semillas son malas.
08 · Práctica guiada
Ejercicios con Python
Ejercicio 1: el culpable c
Fijá a = 5, m = 16 y barrete c 0–7. ¿Cuáles dan período 16?
def periodo(a, c, m, s=7):
v = set()
x = s
while x not in v:
v.add(x)
x = (a * x + c) % m
return len(v)
for c in range(8):
print(c, periodo(5, c, 16))Ver solución razonada
Solo los impares dan 16: los pares comparten factor 2 con 16 y parten el ciclo. Es mcd(c,m)=1 en acción.
Ejercicio 2: el culpable a
Fijá c = 3, m = 16 y barrete a 1–8. ¿Qué patrón ves?
for a in range(1, 9):
print(a, periodo(a, 3, 16))Ver solución
16 solo en 1 y 5 (≡ 1 mod 4). El resto cae a 8, 4 o 2. Un dígito en a decide todo.
Ejercicio 3: overflow antes de portar
¿Entra 1103515245·(2³¹−1) (glibc) en 64 bits? ¿Y en 32?
Ver una posible respuesta
a, m = 1103515245, 2**31
print(a * (m - 1) < 2**64)
print(a * (m - 1) < 2**32)En 64 sí, en 32 no: por eso glibc trunca a 32 bits por diseño (y por eso sus bits bajos son débiles). Saberlo evita «bugs» que son especificación.
09 · Síntesis
Ideas para recordar
- m: techo y costo; c: coprimo para alcanzar el techo; a: mezcla y estructura.
- Con m = 2ᵏ: c impar y a ≡ 1 mod 4 para período completo.
- Semilla no compensa trío malo; m grande tampoco.
- Verificá overflow: a·(m−1)+c vs. tu entero.
- Período completo es piso; la calidad fina se testea.
En el próximo tema formalizaremos el techo: el período máximo y el teorema de Hull–Dobell que lo garantiza.