Subtract with carry

帶進位減法(Subtract-with-carry)是一種時滯斐波那契偽隨機數生成器 ,1991年由George Marsaglia英語George Marsaglia與Arif Zaman發明。[1]

算法

帶進位減法的算法需用遞推關係表示:

 

其中  .

常量SR分別稱作短時滯與長時滯。[2]SR滿足條件 。 因此,表達式  對應於序列中之前的第S項與第R項。取模操作M的值為 ,其中W是狀態序列的字(word)的位長度, 

帶進位的減法與add-with-carry英語add-with-carrysubtract-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