数理解析研究所講究録
第 850 巻 1993 年 72-85

72

ON THE LATTICE STRUCTURE OF THE
ADD-WITH-CARRY AND SUBTRACT-WITH-BORROWRANDOM NUMBER GENERATORSSHU TEZUKA
IBM Research, Tokyo Research Laboratory

PIERRE L’ECUYER
Universit\’e de Montr\’eal

ABSTRACT: Marsaglia and Zaman recently proposed new classes of random number generators, called add-with-carry (AWC) and subtract-with-borrow (SWB), which arecapable 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. So, the $AWC/SWB$ generators canbe viewed as effcient ways of implementing such large linear congruential generators. 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. We
also show how the equivalence can be exploited to implement efficient jumping ahead
facilities for the AWC and SWB sequences. Our numerical examples illustrate the factthat $AWC/SWB$ generators have extremely bad lattice structure in high dimensions.
CR Categories and Subject Descriptors: G.3 [Probability and Statistics]:
Random Number Generation

General Terms: Algorithms, Theory
Additional Key Words and Phrases: Lattice structure, add-with-carry, subtractwith-borrow, linear congruential generators, spectral test

Author’s Addresses:
S. Tezuka, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, Japan;
P. L’Ecuyer, D\’epartement d’IRO, U. de Montr\’eal, C.P. 6128, Succ. , Montr\’eal, $H3C3J7$ ,Canada.
$A$

73
THE AWC AND SWB GENERATORS

1.

Marsaglia and Zaman [10] proposed the following types of random number generators,, and be positive
called add-with-carry (AWC) and subtract-with-borrow (SWB). Let
integers, where is caUed the base and $r>s$ are caUed the lags. The AWC generator isbased on the recurrence$b,$ $r$$s$$b$$x_{i}$$=$$(x_{i-s}+x_{i-r}+c_{i})mod b$$c_{i+1}$$=$$I(x_{i-s}+x_{i-r}+c;\geq b)$ ,

(1)
(2)

,

where is called the carry, and is the indicator function, whose value is 1 if its argument is true, and otherwise. That generator is extremely fast, since it requires nomultiplication, and the modulo operation can be performed by just subtracting if andonly if $x_{i-s}+x_{i-r}+c_{i}\geq b$ . The maximum possible (or full) period is $b‘+b^{s}-2$ . It isattained when $M=b‘+b^{S}-1$ is prime and is a primitive root modulo $M$ (see [10]). For
example, one can take aroundand around 20, yielding a period of approximately
if the full period conditions are satisfied. This goes much beyond the requirements
of most applications.
$I$$c_{i}$

$0$

$b$

$b$

$2^{31}$$b$$r$$2^{620}$

To produce values
whose distribution (hopefully) approximates the $U(O, 1)$ distribution, one can use $L\leq r$ successive values ofto produce one as follows [2]:$\{u;\}$$u_{i}$$x_{j}$$u;= \sum_{j=1}^{L}x_{Li-j+1}b^{-j}$.

(3)have the same
andAssuming that is relatively prime to $M-1$ , the sequences
periods. If is small, or if more precision is desired, take a larger . If is large enough(e.g., a large power of two), one can just take $L=1$ . Here, the digits of are filled up
from the least signfficant to the most significant one. The sequence
defined by (3) isan analogue of the Tausworthe sequence $[11, 13]$ . For the latter, the digits of are filled
up by a linear feedback shift register sequence modulo two (i.e., $b=2$ ). The differencewith (1) is the presence of the carry and the fact that is not necessarily equal to two.
$L$$\{x;\}$$\{u;\}$

$L$

$b$

$b$

$u_{i}$$\{u_{i}\}$$u_{i}$$b$

The AWC has a variant called complementary AWC, or AWC-c, based on:$x_{i}$$c_{i+1}$$=$$(2b-1-x_{i-s}-x_{i-r}-c_{i})mod b$$=$$(-x_{i-s}-x_{i-r}-c_{j}-1)mod b$ ,$=I(x_{i-s}+x_{i-r}+c;\geq b)$ .

(4)

(5)

The SWB also comes in two flavors, which we will call SWB-I and SWB-II, based on therecurrences:$x_{i}$$=$$(x_{i-s}-x_{i-r}-c_{i})mod b$ ,(6)$c_{i+1}$$=$$I(x_{i-s}-x_{i-r}-c_{i}<0)$ ,

(7)

74
and
$x_{i}$$c_{i+1}$

respectively. Here,$c_{i}$.

$-c_{i})mod b$ ,$=$$(x_{i-r}-x_{i-}$$=$$I(x_{i-r}-x_{i-s}-c;<0)$ ,

(8)
(9)

is called the borrow.

We $wiU$ use the general notation $AWC/SWB$ to refer to any of those four variants.
For each of them, the maximum possible period is $M-1$ , achieved when $M$ is prime andis a primitive root modulo $M$ , where the value of $M$ depends on the variant, as shownin Table 1.
$b$

can be produced from theas in (3). For a full period
In all cases, the$AWC/SWB$ generator, theare provably almost equidistributed in up to dimensions,, over thei.e., among all (overlapping) r-dimensional vectors of successive values ofwhole period, every r-dimensional vector with components in $\{0, \ldots , b-1\}$ appears exactly
once, except for a tiny percentage of exceptions [10].
$u_{i}’ s$$x_{j}’ s$$x_{i}’ s$$r$$x_{i}’ s$

The $AWC/SWB$ methods can be viewed as slight modifications to the so-called additiveor subtractive methods discussed in Knuth [3]. The only difference in implementationis that for the latter, there is no carry or borrow ( $c_{i}=0$ for all ). But in terms of
period length, this makes an enormous difference: for example, if $b=2^{e}$ (a power oftwo), the maximal period lengths for the additive and subtractive generators are only$(2^{f}-1)2^{e-1}\approx 2^{\tau+e-1}$ , which falls way short of $b^{f}+b^{s}-2\approx 2^{re}$ , unless $e=1$ .
Theadditive and subtractive generators belong to the more general class of lagged-Fibonacci
generators. See $[4, 9]$ for more details.
$i$Marsaglia and Zaman [10] give alist of parameter sets for SWB-I generators, for which
the order of modulo $M$ is very large or near the maximum. Those generators do nothave full period, but a large period anyway. Finding full period generators with a verylarge period is hard, because checking the primitivity requires the factorization of $M-1$ ,which is a difficult task in practice when $M$ is large. For example, for $M$ around,the best factorization programs currently available typically cannot factorize $M-1$ in
reasonable time.
$b$$2^{1000}$

75
In this paper, we analyze the structure of the sequence $u;,$ $i=1,2,$ , produced by
an $AWC/SWB$ generator. That sequence turns out to be practically the same as thesequence produced by a linear congruential generator (LCG). More precisely, we have thebe the state of the $AWC/SWB$ generator at step
following. Let
into the uniform variate . Suppose that $M$. Equation (3) transforms the state
be the multiplicative inverse of modulo $M$ , i.e.,(given in Table 1) is prime and letsuch that $b^{*}bmod M=1$ . That inverse can be computed easily as $b^{*}=b^{M-2}mod M$ .
Consider the following LCG with modulo $M$ and multiplier $A=b^{*}$ :$\ldots$$s_{i}=$ $(x_{i-r+1}, \ldots , x_{i}, c_{i+1})$$i$$s_{Li}$$u_{i}$$b$$b^{*}$$X_{i}$$=$$AX_{i-1}mod M$,$v_{i}$$=$$X_{i}/M$$w_{i}$$=$$v_{Li}=X_{Li}/M$

(10)

,

(11)
(12)

.

Our main result is:
THEOREM 1. Let $\{u_{i}, i\geq 0\}$ be the sequence (3) produced by an $AWC/SWB$ generator,
correspond,
while $\{w_{i}, i\geq 0\}$ is the sequence produced by (12). If andfor$i\geqr$, the (fractional) digital expansions in base of andhave the same firstalldigits. In other words, one has(13).
$s_{0}$$b$$u_{i}$$then_{f}$$X_{0}$$L$$w_{i}$$u_{i}=b^{-L}\lfloor b^{L}w_{i}\rfloor$

correspond” means that the two sequences must have corand
The condition
responding initial seeds. Otherwise, (13) will hold after an appropriate shift of one of
the two sequences. Equation (13) means thatis a truncated version of : only the
first fractional digits in base are kept, the others are chopped off. As a consequence,$|u_{i}-w;|\leq b^{-L}$ . So, the sequences (3) and (12) are the same, if they have corresponding. For example, it could be reasonable to take $b>2^{30}$
initial seeds, up to a precision of
and $L=2$ , in which case the first 60 bits of andwill be the same. For all practical
purposes, considering the limited precision of floating point numbers on computers, one
can then safely assume that $u_{i}=w_{i}$ .
$s_{0}$$X_{0}$$w_{i}$$u_{i}$$L$$b$$b^{-L}$$u_{i}$$w_{i}$

We call (10-12) the $LCG$ representation of the corresponding $AWC/SWB$ generator.
For a theoretical evaluation of the structural properties of an $AWC/SWB$ generator, one
can study the lattice structure of its LCG representation. We discuss that in Section 2.
In Section 3, we illustrate those properties with numerical examples. Some of them are
generators taken from Marsaglia and Zaman [10]. It turns out that all the generators
examined perform extremely badly, in the spectral test, in dimensions $r+1$ and higher.
At the end of Section 2, we show that this holds in general: for all $AWC/SWB$ generatorswith $L=1$ , the distance between the hyperplanes in the lattice of the associated LCG is
at least
in all dimensions larger than . The full version of the paper will appear
soon somewhere.
$1/\sqrt{3}$

$r$

76
LATTICE STRUCTURE AND SPECTRAL TEST2.

It is well known that linear congruential generators have a lattice structure which canbe analyzed through the Beyer and spectral tests {3, 4, 7]. More precisely, suppose weconstruct points in $[0,1)^{t}$ by taking successive values produced by the generator:$t$$w_{\ell,i}=(w_{i}, \ldots, w_{i+t-1})$Let$T_{t}$.

be the set of all such points, for all possible initial states $X_{0}\in Z_{M}$ :$T_{t}=\{w_{t,i}=(w_{i}, \ldots, w_{i+t-1})|i\geq 0, X_{0}\in Z_{M}\}$.

with the unit hypercube $[0,1)^{t}$ . The Beyer
is the intersection of a latticeThenof the lengths of the shortest and longest vectors inquotient is defined as the ratioa Minkowski-Reduced Basis of that lattice. A value of close to one indicates thatthe points of are rather “uniformly” distributed, while a very small value indicates the
opposite (a “bad” lattice structure). The lattice structure also means that the points lie ina set of equidistant parallel hyperplanes. Let be the distance between those hyperplanes
in dimension . Generally speaking, we would like to be as small as possible, because
larger values of (close to 1) mean thicker slices of space containing no points.
$L_{t}$$T_{t}$$q_{t}$$q_{t}$$L_{t}$$d_{t}$$t$$d_{t}$$d_{t}$The LCG that produces the points$T_{t}$

is in fact equivalent to$Y_{1}$.

$=$$\tilde{A}Y_{i-1}mod M$$w_{i}$$=$$Y_{i}/M$

(14)

,

(15)

,

where $Y_{0}=X_{0}$ and $\tilde{A}=A^{L}mod M=b^{M-L-1}mod M$ . If the multiplier
above is$\tilde{A}^{*}=b^{L}mod M$
replaced by its inverse, then it will produce the same sequence, but
in reverse order. Since the reverse sequence has the same lattice structure as the original
one, applying the spectral or Beyer test with the multiplierorwill yield the same
results.
$\tilde{A}$$\{w_{i}\}$$b^{L}$$A^{L}$

Consider now the points produced by an AWC or SWB generator:$u_{t,i}=(u_{i}, \ldots, u_{i+t-1})$,

assuming that $s_{0}=\psi(X_{0})$ . It follows from Theorem 1 that $|u_{i}-w_{i}|<b^{-L}$ . Therefore,
the Euclidean distance between
and. If that bound isis bounded bysmall with respect to the Euclidean distance
between hyperplanes, then the AWC
or SWB generator inherits the lattice structure of the associated LCG, with some small(often negligible) added “noise” due to the truncation. We will examine specific numericalexamples in the next section.
$w_{t,i}$$b^{-L}\sqrt{t}$$u_{t,i}$$d_{t}$

The following result shows that $AWC/SWB$ generators with $L=1$ always have a badlattice structure in dimensions larger than . We give a simple proof here for completeness.
$r$

77
LEMMA 1. For the $LCG(10-11)_{f}$ one has$d_{t}\geq 1/\sqrt{3}$for all $t\geq r+1$ .

Consider the AWC generator (the proof is similar for the other variants).

PROOF.
One has$X_{i-r}+X_{i-s}-X;\equiv(b^{r}+b^{s}-1)X_{i}\equiv MX_{j}\equiv 0$$(mod M)$ .

So, by following the same reasoning as in Section 3.3.4 of Knuth [3], it follows that thedual lattice has a vector of square length equal to 3, and the conclusion follows. 1

3.

NUMERICAL EXAMPLES

3.1

Example 1: A SmaII SWB Generator

Consider the SWB-I generator with $(b, s, r, L)=(2,2,9,9)$ . Here, $x_{i}=(x_{i-2}-x_{i-9}-$$c_{i})mod 2$,$u;= \sum_{j=1}^{9}x_{9i-j+1}2^{-j}$,and the period is $2^{9}-2^{2}=508$ . Figure 1 shows a two-dimensional plot of the pairs of
produced by this generator over its entire period. The starting
successive points
values were $s_{0}=(x_{-8}, \ldots, x_{0}, c_{1})=(1,0, \ldots, 0)$ . This looks like a typical lattice structureof a (bad) LCG.
$(u_{i}, u_{i+1})$

The LCG representation of that SWB generator is$Y_{i}=170Y_{i-1}mod 509$ ;$w_{i}=Y_{i}/509$,

where $Y_{i}=X_{Li}$ and 170 is the inverse of $2^{9}(=3)$ modulo 509. Since isjust the truncatedversion of , the points produced by the SWB generator do not form exactly a lattice,
but it really takes sharp eyes see that the points in Figure 1 are not exactly aligned on
the three lines. The approximation is quite good indeed.
$u_{i}$$w_{i}$

If the multiplier 170 was replaced by 3, we would get the same graphic, but refiected$with\cdot respect$ to the diagonal $u;=u_{i+1}$ . Hence, the points of the LCG representation will
be on three lines of slope 3 instead of slope 1/3.

78

Figure 1: All pairs of successive points for the SWB generator of Example 1.

79
3.2 Example 2: A ”Classroom“ AWC Generator
We now examine the “classroom” AWC generator given in Section 7 of Marsaglia andZaman [10], for which $(b, s,r, L)=(6,2,21, L)$ . The sequence is defined by$u_{i}= \sum_{j=1}^{L}x_{Li-j+1}6^{-j}$,where is generated by $x_{i}=(x_{i-21}+x_{i-2}+c_{i})mod 6$ . We will look at different valuesof . Since $M=6^{21}+6^{2}-1=21,936,950,640,377,891$ is prime and $b=6$ is a primitive
have period $M-1$ . When is relatively prime toroot modulo $M$ , the sequence of$M-1$ , thealso have that same period. According to Marsaglia and Zaman [10], the, if used directly, could provide an excellent simulation of independent throws of adice.
$x_{i}$$L$$L$$x_{i}’ s$$u_{i}’ s$$x_{j}’ s$

The LCG representation is given by$X_{Li}=Y_{i}=(6^{*})^{L}Y_{i-1}mod M$;$w_{i}=Y_{i}/M$.

The following values of are relatively prime to $M-1:L=1,3,7,9,11,17,19$ . For
small , like 1 or 3, the resolution is much too low and as a result, the LCG is not a good
approximation of the AWC sequence. We have computed the values of and for thecorresponding LCG’s for the other values of . The results are given in Table 2. For all
those values of , the lattice structure turns out to be quite bad in low dimensions. In
fact, it is amazing to see how terrible are some of those multipliers in lower dimensions
on the noise is much smaller(e.g., for $L=17$ and $L=19$ ). The upper boundthan the distance between hyperplanes, except for $L=7,9,11$ in dimension 2 and $L=7$
in dimension 3.
$L$

$L$

$q_{t}$$d_{t}$$L$$L$$6^{-L}\sqrt{t}$3.3

Example 3: A Larger SWB Generator

One SWB-I generator recommended by Marsaglia and Zaman (1991) has parameters$(b, s, r, L)=(2^{32},6,21,1)$ . That generator does not have full period, it has 192 subcyclesof period $(2^{666}-2^{186})/3$ each (besides the two trivial cycles of period 1). The LCG
representation has modulus $M=2^{672}-2^{192}+1$ and multiplier $A=(2^{32})^{*}mod M=$$2^{160}-2^{640}mod M$ .

can study the lattice structure formed by the vectors of successive points in the. union of all the subcycles (for a single cycle, the points do not necessarily form a lattice,$1!Ve$

80

81

Figure 2: 2000 pairs of successive points for the SWB of Example 2, with $L=19$ .

82

but for the union of all cycles, they do). Table 3 gives the values of and for up to 30.
The bad behavior in dimensions larger than 21 is in accordance with Lemma 4. We recall
that for dimensions smaller or equal to 21, the lattice structure of the associated LCG
provides only limited information on the behavior of the $AWC/SWB$ generator, because
the truncation error is as large as the distance between the successive hyperplanes. But
the small values of for $t\leq 21$ agree with the fact that over the full period, the points
are very evenly distributed over the unit hypercube.
$d_{t}$$d_{t}$$q_{t}$

$t$

83

84
3.4 Example 4: The RANMAR SWB Generator
James [2] recommends the SWB-I generator with parameters $(b, s, r, L)=(2^{32}-5,22,43,1)$ .
That generator is also given in [10] and used as a component of the combined generator
proposed in [8]. Since is primitive modulo $M=b^{43}-b^{22}+1$ , the (full) period lengthis $M-1=2^{1376}-2^{704}+1$ . The LCG representation has modulus $M$ and multiplier$b$.

$A=(2^{32}-5)^{*}mod M=(2^{32}-5)^{21}-(2^{32}-5)^{42}mod M$

Table 4 gives the values of and for that LCG generator, for up to $t=50$ . In
, while for $t\geq 44$ , we have $d_{t}=1/\sqrt{3}\approx 0.577$ ,all dimensions $t\leq 43$ , one hasin accordance with Lemma 4. So, using that generator for applications which requirepoints in large dimensional spaces could lead to problems. L’Ecuyer [5] has applied afew statistical tests to this generator and found that it fails (rather spectacularly) the“birthday spacing” test proposed by Marsaglia [7].
$d_{t}$$q_{t}$$d_{t}\leq b^{-1}$4.

Conclusion

We have shown in this paper that the $AWC/SWB$ generators are essentially equivalent
to LCGs with large moduli. So, they can be viewed as (extremely) efficient ways of
implementing LCGs with (huge’ moduli. The difference is a “truncation error” of size
at most. When the associated LCG has a lattice structure with distance between
in dimension , the $AWC/SWB$ generator
hyperplanes significantly larger thanalso inherits that lattice structure. Our examples illustrate how bad could be that lattice
structure for the generators proposed in [10]. In fact, it turns out that all $AWC/SWB$
generators with $L=1$ have a very bad lattice structure in dimensions larger than .
Therefore, such $AWC/SWB$ generators should not be used directly by themselves. To
make those generators useful, one would have to find appropriate combinations withother types of generators, with good theoretical properties. This could be a subject for
further research.
$b^{-L}$$b^{-L}\sqrt{t}$

$t$

$r$

Acknowledgments
The second author’s work was supported by NSERC-Canada grant
OGP0110050 and
FCAR-Qu\’ebec grant $\# 93ER1654$ . Part of the work was accomplished while the second
author was holding the Toshiba Chair at Waseda University, in Tokyo. Jos\’ee Turgeon
helped doing the computations for the second numerical example.
$\#$

85
References[1] R. Couture, P. L’Ecuyer, and S. Tezuka, On the Distribution of k-Dimensional Vectors for Simple and Combined Tausworthe Sequences. To appear in Mathematics ofComputation.
[2] F. James, A review of pseudorandom number generators. Computer Physics Communications, 60 (1990) 329-344.
[3] D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, vol.
2, second edition. Addison-Wesley, 1981.

[4] P. L’Ecuyer, Random Numbers for Simulation. Communications of the A CM 33, 10(1990) 85-97.

[5] P. L’Ecuyer, Testing Random Number Generators. Proceedings of the 1992 Winter
Simulation Conference, IEEE Press, 305-313.
[6] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications.
Cambridge University Press, Cambridge, 1986.
[7] G. Marsaglia, A Current View of Random Number Generation. Computer Scienceand Statistics, Proceedings of the Sixteenth Symposium on the Interface, Atlanta,
march 1984. Elsevier Science Publ. (North-Holland), 1985, 3-10.
[8] G. Marsaglia, B. Narasimhan, and A. Zaman, A Random Number Generator for
PC’s, Computer Physics Communications 60 (1990) 345-349.

[9] G. Marsaglia and L.-H. Tsay, Matrices and the Structure of Random Number Sequences, Linear Algebra and its Applications 67 (1985) 147-156.

[10] G. Marsaglia and A. Zaman, A New Class of Random Number Generators, The
Annals of Applied Probability 1 (1991) 462-480.
[11] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo llethods,
SIAM CBMS-NFS Regional Conference Series in Applied Mathematics, vol. 63,
SIAM, Philadelphia, 1992.
[12] S. Tezuka, Analysis of Marsaglia’s New Random Number Generators, IBM TRL
Technical Report, RT-5018, (Feb. 1991)[13] S. Tezuka, A Unified View of Long-Period Random Nulnber Generators, Submitted
for publication.

[14] S. Tezuka and P. L’Ecuyer, Analysis of Add-with-carry and Subtract-with-borrowgenerators, Proceedings of the 1992 Winter Simulation Conference, IEEE Press.
(1992) 443-447.