Restar con acarreo

Subtract-with-carry es un generador de números pseudoaleatorios : uno de los muchos algoritmos diseñados para producir una larga serie de números de apariencia aleatoria a partir de una pequeña cantidad de datos iniciales. Es del tipo Fibonacci rezagado introducido por George Marsaglia y Arif Zaman en 1991. ^[1] "Fibonacci rezagado" se refiere al hecho de que cada número aleatorio es una función de dos de los números anteriores en algunos desplazamientos fijos especificados o "rezagos".

Algoritmo

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

${\displaystyle x(i)=(x(i-S)-x(i-R)-cy(i-1))\ {\bmod {\ }}M}$

dónde . ${\displaystyle cy(i)={\begin{cases}1,&{\text{if }}x(i-S)-x(i-R)-cy(i-1)<0\\0,&{\text{otherwise}}\end{cases}}}$

Las constantes S y R se conocen como los rezagos corto y largo, respectivamente. ^[2] Por lo tanto, las expresiones y corresponden a los términos previos S -ésimo y R -ésimo de la secuencia. S y R satisfacen la condición . El módulo M tiene el valor , donde W es el tamaño de palabra, en bits, de la secuencia de estados y . ${\displaystyle x(i-S)}$ ${\displaystyle x(i-R)}$ ${\displaystyle 0<S<R}$ ${\displaystyle M=2^{W}}$ ${\displaystyle W>0}$

El motor de resta con acarreo es uno de la familia de generadores que incluye también los motores de suma con acarreo y de resta con préstamo. ^[1]

Es uno de los tres motores generadores de números aleatorios incluidos en la biblioteca estándar C++11 . ^[3]

Referencias

1. Una nueva clase de generadores de números aleatorios, George Marsaglia y Arif Zaman, The Annals of Applied Probability, vol. 1, n.º 3, 1991
2. Clase subtract_with_carry_engine, Microsoft Visual Studio 2015
3. std::subtract_with_carry_engine, cppreference.com