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.[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

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

[math]\displaystyle{ x(i) = (x(i-S) - x(i-R) - cy(i-1))\ \bmod\ M }[/math]

where [math]\displaystyle{ cy(i) = \begin{cases} 1, & \text{if } x(i-S) - x(i-R) - cy(i-1) \lt 0\\\ 0, & \text{otherwise} \end{cases} }[/math].

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

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

1. ↑ 1.0 1.1 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Subtract with carry. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Subtract_with_carry&oldid=60019"