查看“︁Subtract with carry”︁的源代码

'''带进位减法（Subtract-with-carry）'''是一种[[时滞斐波那契生成器|时滞斐波那契]][[伪随机数生成器]] ，1991年由{{tsl|en|George Marsaglia}}与Arif Zaman发明。<ref name=marsaglia>[http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoap/1177005878 A New Class of Random Number Generators] {{Wayback|url=http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoap%2F1177005878 |date=20200710055113 }}, George Marsaglia and Arif Zaman, The Annals of Applied Probability, Vol. 1, No. 3, 1991</ref>

==算法==
带进位减法的算法需用[[遞迴關係式|递推关系]]表示：

<math>
x(i) = (x(i-S) - x(i-R) - c(i-1))\ \bmod\ M
</math>

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

常量''S''与''R''分别称作短时滞与长时滞。<ref>[https://msdn.microsoft.com/en-us/library/ee462331.aspx subtract_with_carry_engine Class] {{Wayback|url=https://msdn.microsoft.com/en-us/library/ee462331.aspx |date=20161019131636 }}, Microsoft Visual Studio 2015</ref>''S''与''R''满足条件<math>0 < S < R</math>。
因此，表达式<math>x(i - S)</math>与<math>x(i - R)</math>对应于序列中之前的第''S''项与第''R''项。[[取模操作]]''M''的值为<math>M = 2^W</math>，其中''W''是状态序列的字（word）的位长度，<math>W > 0</math>。

带进位的减法与{{tsl|en|add-with-carry}}、{{tsl|en|subtract-with-borrow}}为同一族随机数生产引擎。<ref name=marsaglia/>

带进位的减法是[[C++11]][[标准模板库]]中的三种随机数生成器之一。<ref>[http://en.cppreference.com/w/cpp/numeric/random/subtract_with_carry_engine std::subtract_with_carry_engine] {{Wayback|url=http://en.cppreference.com/w/cpp/numeric/random/subtract_with_carry_engine |date=20200710055721 }}, cppreference.com</ref>

==参考文献==
{{Reflist}}

[[Category:伪随机数生成器]]