Subtract with carry
{{Technical|date=July 2013}}
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.[http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoap/1177005878 A New Class of Random Number Generators], George Marsaglia and Arif Zaman, The Annals of Applied Probability, Vol. 1, No. 3, 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.[https://msdn.microsoft.com/en-us/library/ee462331.aspx subtract_with_carry_engine Class], Microsoft Visual Studio 2015
Therefore, expressions and correspond to the S-th and R-th previous terms of the sequence.
S and R satisfy the condition .
Modulus M has the value , where W is the word size, in bits, of the state sequence and .
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.[http://en.cppreference.com/w/cpp/numeric/random/subtract_with_carry_engine std::subtract_with_carry_engine], cppreference.com
References
{{Reflist}}