Subtract with carry

Subtract-with-carry is a pseudorandom number generator of the lagged Fibonacci type introduced by George Marsaglia and Arif Zaman in 1991.^[1] It is one of three random number generator engines included in the standard C++11 library.^[2]

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.^[3] 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.^[1]

References

1 2 A New Class of Random Number Generators, George Marsaglia and Arif Zaman, The Annals of Applied Probability, Vol. 1, No. 3, 1991
↑ std::subtract_with_carry_engine, cppreference.com
↑ subtract_with_carry_engine Class, Microsoft Visual Studio 2015

This article is issued from Wikipedia - version of the 5/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.