Restar con acarreo

Un ejemplo sencillo puede ilustrar el proceso. Sean los parámetros:

• Módulo M = 10
• Retardo largo R = 3
• Retardo corto S = 1
• Estado inicial (semilla): una lista de 3 números${\displaystyle x=(x_{0},x_{1},x_{2})=(6,8,3)}$y un acarreo inicial${\displaystyle c_{2}=0}$.

Para generar el siguiente número,${\displaystyle x_{3}}$:

1. Identificar el valor de retardo corto${\displaystyle x_{3-S}=x_{2}=3}$y el valor de retardo largo${\displaystyle x_{3-R}=x_{0}=6}$.
2. Realiza la resta:${\displaystyle x_{2}-x_{0}-c_{2}}$→${\displaystyle 3-6-0=-3}$.
3. Como el resultado es negativo, se produce un préstamo. El nuevo acarreo${\displaystyle c_{3}}$se convierte en 1.
4. El nuevo número${\displaystyle x_{3}}$es el resultado módulo M :${\displaystyle -3\mod 10=7}$.
5. El estado se actualiza. La lista se convierte en${\displaystyle (x_{1},x_{2},x_{3})=(8,3,7)}$y el acarreo ahora es 1 para el siguiente paso.

Este proceso puede repetirse para generar una larga secuencia de números pseudoaleatorios.

La secuencia generada por el motor de resta con acarreo se describe mediante la relación de recurrencia :

${\displaystyle x(i)=(x(iS)-x(iR)-cy(i-1))\ {\bmod {\ }}M}$

donde el nuevo portador,${\displaystyle cy(i)}$, se define como:

${\displaystyle cy(i)={\begin{cases}1,&{\text{si }}x(iS)-x(iR)-cy(i-1)<0\\0,&{\text{en otro caso}}\end{cases}}}$

Los retardos deben satisfacer la condición${\displaystyle 0<S<R}$. El módulo M suele ser una potencia de 2, como por ejemplo${\displaystyle M=2^{W}}$, donde W es el tamaño de palabra de la secuencia de estado en bits. ^{[ 1 ]}