Generadores congruenciales combinados

01 · Punto de partida

Si uno se queda corto, usá dos

Un LCG solo está limitado por su m: para alargarlo hay que agrandar el módulo (más costo, más overflow). La alternativa de los 80s fue combinar: correr dos o tres LCG chicos en paralelo y mezclar sus salidas. El período resultante es el mínimo común múltiplo de los períodos, que puede ser gigantesco con módulos modestos.

Además la mezcla rompe parte de la estructura reticular de cada componente: lo que era una diagonal en uno se difumina al restarlo con otro.

• ¿Cómo se combinan dos secuencias en una?
• ¿Por qué el período se multiplica (mcm) en vez de sumarse?
• ¿Qué combinaciones clásicas debes conocer?
• ¿Cuándo conviene combinar y cuándo migrar a moderno?

02 · Definición

Componentes, mezcla y período

03 · Por qué funciona

El mcm en una imagen mental

Dos ruedas dentadas

Una de 16 dientes y otra de 15: solo cada 240 pasos vuelven ambas al diente inicial juntas. Ese es el ciclo combinado.

Coprimos rinden

Si mcd(p₁,p₂)=1, mcm = p₁·p₂ (máximo). Si comparten factores, el mcm se achica: por eso los módulos se eligen coprimos.

Mezcla rompe forma

Restar desordena la retícula de cada uno: diagonales que eran claras se vuelven nube. No la elimina del todo, pero la atenúa.

04 · Ejemplos

De 16 y 15 a 240

1. 1
   Componente A.

   (5,3,16), p₁ = 16, semilla 7.

2. 2
   Componente B.

   (7,5,15) (7−1=6 divisible por 3 y 5, c coprimo): p₂ = 15, semilla 4.

3. 3
   Combinado.

   z = (x−y) mod 16, p = 240 = 16·15. Con N = 48 ya no se repite (el solo daba 3 vueltas).

05 · Implementación en Python

Dos estados, una mezcla

def combinado(s1, s2, n=12):
    x, y = s1, s2
    sal = []
    for _ in range(n):
        x = (5 * x + 3) % 16
        y = (7 * y + 5) % 15
        z = (x - y) % 16
        sal.append(round(z / 16, 4))
    return sal


print(combinado(7, 4))

Doce uniformes sin repetición visible: con N = 48 el solo ya daba vueltas y este no.

Período como mcm

import math

print(math.lcm(16, 15))
print(math.lcm(8, 12))

06 · Exploración

Laboratorio: 16 × 15 = 240

Elegí preset y N. La curva lima es el combinado; las finas son A y B. El panel da p₁, p₂, p combinado y vueltas. Compará con el solo del Tema 10.

Si N supera p, el combinado también se repite: solo que tarda 240 en vez de 16.

Preguntas para explorar

1. Con buenos y N = 96, ¿cuántas vueltas da el combinado? ¿Y el A solo?
2. Poné N = 480: ¿el combinado repite? ¿Cuántas vueltas?
3. Con ambos malos, ¿el período combinado te salva? ¿Qué calidad esperarías?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: mcm a mano

Calculá el período combinado de p₁ = 16 y p₂ = 15, y de p₁ = 8 y p₂ = 12. ¿Por qué el segundo no es producto?

import math

print(math.lcm(16, 15))
print(math.lcm(8, 12))
print(math.gcd(8, 12))

Ejercicio 2: medir el combinado

Medí p del combinado didáctico por diccionario y compará con 240.

def p_combinado(s1=7, s2=4):
    v = set()
    x, y = s1, s2
    while (x, y) not in v:
        v.add((x, y))
        x = (5 * x + 3) % 16
        y = (7 * y + 5) % 15
    return len(v)


print(p_combinado())

Ejercicio 3: malos no se reciclan

Combiná (4,2,16) con (4,2,15 adaptado) y medí p y calidad visual con N = 120. ¿Largo salva?

def comb_malo(s1=7, s2=4, n=120):
    x, y = s1, s2
    sal = []
    for _ in range(n):
        x = (4 * x + 2) % 16
        y = (4 * y + 2) % 15
        sal.append((x - y) % 16 / 16)
    return sal


v = comb_malo()
print(len(set(round(u, 9) for u in v)), "distintos en 120")

09 · Síntesis

Ideas para recordar

En el próximo tema cambiaremos de familia: generadores basados en desplazamientos de bits, velocidad pura con álgebra binaria.