Subtract with carry

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (July 2013) (Learn how and when to remove this message)

|

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

[edit]

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

x ( i ) = ( x ( i − S ) − x ( i − R ) − c y ( i − 1 ) ) mod M {\displaystyle x(i)=(x(i-S)-x(i-R)-cy(i-1))\ {\bmod {\ }}M}

where  c y ( i ) = { 1 , if x ( i − S ) − x ( i − R ) − c y ( i − 1 ) < 0 0 , otherwise {\displaystyle 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.[2] Therefore, expressions  x ( i − S ) {\displaystyle x(i-S)} and  x ( i − R ) {\displaystyle 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 {\displaystyle 0<S<R} . Modulus M has the value  M = 2 W {\displaystyle M=2^{W}} , where W is the word size, in bits, of the state sequence and  W > 0 {\displaystyle 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]

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

## References

[edit]

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