1;3409;0c Analysis of Add-with-Carry and Subtract-with-Borrow Generators

Analysis of Add-with-Carry and Subtract-with-Borrow Generators

Proceedings of the 24th Winter Simulation Conference, 1992
Pages: 443-447DOI: 10.1145/167293.167399



Marsaglia and Zaman recently proposed a new class of random number generators, acid-with-carr~ and subtractwith-borrow, which are capable of quickly generating very long period (pseudo) -random number sequences using very little memory. We show that these sequences are essentially equivalent to linear congruential sequences with very large prime moduli. As a consequence, the theoretical properties of such generators can be studied in the same way as for linear congruential generators, namely via the spectral and lattice tests. 1. THE AWC AND SWB GENERATORS Marsaglia and Zaman (1991) recently proposed two new types of random number generators, called add-withcarry (AWC) and subtract-with-borrow (SWB). The AWC generator is based on the recursion Xi = (z,_. + x,_. + c,) mod b, (1) C;+l ~ I~zi-s + ~i.-r + C, z b), (2) where r > s are positive integers called the lags, ci is called the carry, and 1 is the indicator function, whose value is 1 if its argument is true, and O otherwise. That generator is extremely fast, since it requires no multiplication, and the modulo operation can be performed by just subtracting b if t,-, + 21–. + c, ~ b. The maximum possible (or full) period is br + b’ - 2. It is attained when J4 = b’ +b” – 1 is prime and b is a primitive root modulo ill. For example, one can take b around 231 and r around 20, yielding a mo if the full period conditionsperiod of approximately 2 are satisfied. This is much beyond what could be required by any application