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




References

Kata Kunci Pencarian:

• Set instruksi 14-bit
• International Securities Identification Number
• Set instruksi 12-bit
• Subtract with carry
• Carry flag
• Adder–subtractor
• Subtraction
• Subtractor
• Lagged Fibonacci generator
• Adder (electronics)
• Method of complements
• Carry-skip adder
• Trachtenberg system