Subtract with carry

Subtract-with-carry is a pseudorandom number generator: one of many algorithms designed to produce a long series of random-looking numbers based on a small amount of starting data. It is of the lagged Fibonacci type introduced by George Marsaglia and Arif Zaman in 1991. "Lagged Fibonacci" refers to the fact that each random number is a function of two of the preceding numbers at some specified, fixed offsets, or "lags".

Algorithm

Sequence generated by the subtract-with-carry engine may be described by the recurrence relation:

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

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

Constants S and R are known as the short and long lags, respectively. Therefore, expressions $x(i-S)$ and $x(i-R)$ correspond to the S-th and R-th previous terms of the sequence. S and R satisfy the condition $0<S<R$. Modulus M has the value $M=2^{W}$, where W is the word size, in bits, of the state sequence and $W>0$.

The subtract-with-carry engine is one of the family of generators which includes as well add-with-carry and subtract-with-borrow engines.

It is one of three random number generator engines included in the standard C++11 library.