Subtract with carry

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

算法

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

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

其中 ${\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满足条件${\displaystyle 0<S<R}$。 因此，表达式${\displaystyle x(i-S)}$与${\displaystyle x(i-R)}$对应于序列中之前的第S项与第R项。取模操作M的值为${\displaystyle M=2^{W}}$，其中W是状态序列的字（word）的位长度，${\displaystyle W>0}$。

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

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

参考文献

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