Métodos congruenciales

Se define el siguiente método congruencial: Se genera

$$X_i = aX_{i-1} + c ( M )$$

a partir de una semilla X₀, con

$$a \in \mathbb{Z} ,\quad 1\leq a \leq M,\quad X_0 \in \mathbb{Z} ,\quad 0\leq X_0 \leq M-1$$

$$c \in \mathbb{Z} ,\quad 0\leq c \leq M,\quad M \in \mathbb{Z} .$$

Entonces se toma

$$u_i=\frac{X_i}{M} \in [0,1).$$

Ejemplo: M=1000, a=7, c=501, X₀=0.

$X_1= (7 \cdot 0 + 501) ( 1000 ) = 501$.

$X_2= (7 \cdot 501 + 501) ( 1000 ) = 8$.

Y así sucesivamente. Si X_i=X_i+k por vez primera, entonces k se denomina período del generador. Si c=0 el método se dice multiplicativo. A continuación, enunciamos dos resultados relacionados con congruencias cuya demostración se omite. Condición necesaria para que un generador multiplicativo tenga un período de longitud M-1 es que M sea primo. Si M es primo, el período divide a M-1. En este caso, el período es M-1 si, y sólo si,

$$a^{\frac{M-1}{p}}\not \equiv 1 (M) \text{ para ningún factor primo $p$ de } M-1.$$

Sea $a\neq 0$. Un generador congruencial tiene período M si, y sólo si, se cumplen las tres condiciones siguientes:

1.

mcd(c,M)=1.

2.

$a \equiv 1 (p) \ \forall p$ factor primo de M.

3.

$a \equiv 1 (4)$ si M es múltiplo de 4.

A continuación se presenta el generador implementado en los IBM380 en 1970. Este método resultó tener un gran problema: hay quince planos paralelos en el cubo [0,1]³ que contienen todos los puntos que se obtienen tomando tres valores X_i, X_i+1, X_i+2 cualesquiera.

Ejemplo: c=0, a=2¹⁶+3, M=2³¹ Los c_i que se utilizan a continuación representan enteros. Su valor exacto se omite pues no tiene interés.

X_i+1=(2¹⁶+3) X_i + 2³¹ c₀

$$X_{i+2}=(2^{16}+3) X_{i+1} + 2^{31} c_1 = (2^{16}+3)^2 X_i + 2^{31} c_3 = (6\cdot 2^{16} + 9)X_i + 2^{31} c_4 =$$

=(6 (2¹⁶+3)-9) X_i + 2³¹ c₄ = 6 (2¹⁶+3)X_i - 9 X_i + 2³¹ c₄ = 6 X_i+1 -9 X_i + 2³¹ c₅

Así

$$u_{i+2} - 6 u_{i+1} + 9 u_i = c_5 \in \mathbb{Z} .$$

Como u_i, u_i+1, $u_{i+2} \in [0,1)$ y $c_5 \in \mathbb{Z}$, enonces $c_5 \in \{-5,-4,\dots,8,9\}$. Es decir, todas las ternas (u_i,u_i+1,u_i+2) están concentradas en quince planos.

Un generador recomendado es

$$X_{i+1} = (69069X_i + 1) \equiv 2^{32}.$$