Subtract with carry

带进位减法（Subtract-with-carry）是一种时滞斐波那契伪随机数生成器 ，1991年由George Marsaglia（英语：George Marsaglia）与Arif Zaman发明。[1]

## 算法

[编辑]

带进位减法的算法需用递推关系表示：

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

其中  c ( i ) = { 1 , if x ( i − S ) − x ( i − R ) − c ( i − 1 ) < 0 0 , 否 则 {\displaystyle c(i)={\begin{cases}1,&{\text{if }}x(i-S)-x(i-R)-c(i-1)<0\\\0,&{\text{否 则}}\end{cases}}} .

常量S与R分别称作短时滞与长时滞。[2]S与R满足条件 0 < S < R {\displaystyle 0<S<R} 。 因此，表达式 x ( i − S ) {\displaystyle x(i-S)} 与 x ( i − R ) {\displaystyle x(i-R)} 对应于序列中之前的第S项与第R项。取模操作M的值为 M = 2 W {\displaystyle M=2^{W}} ，其中W是状态序列的字（word）的位长度， W > 0 {\displaystyle W>0} 。

带进位的减法与add-with-carry（英语：add-with-carry）、subtract-with-borrow（英语：subtract-with-borrow）为同一族随机数生产引擎。[1]

带进位的减法是C++11标准模板库中的三种随机数生成器之一。[3]

## 参考文献

[编辑]

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