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. It is one of three random number generator engines included in the standard C++11 library.

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

where c y ( i ) = { 1 , if  x ( i − S ) − x ( i − R ) − c y ( i − 1 ) < 0 0 , otherwise .

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.