Abstract
Marsaglia and Zaman recently proposed new classes of random number generators, called add-with-carry (AWC) and subtract-with-borrow (SWB), 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. So, the AWC/SWB generators can be viewed as efficient 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 fact that AWC/SWB generators have extremely bad lattice structure in high dimensions.
Keywords
Pseudorandom number generatorRandom number generationMathematicsLinear congruential generatorLattice (music)Discrete mathematicsCarry (investment)AlgorithmPower (physics)
Affiliated Institutions
Related Publications
On lattices, learning with errors, random linear codes, and cryptography
Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning...
The Multiple Sequence Alignment Problem in Biology
The study and comparison of sequences of characters from a finite alphabet is relevant to various areas of science, notably molecular biology. The measurement of sequence simila...
A grid-based Bader analysis algorithm without lattice bias
A computational method for partitioning a charge density grid into Bader volumes is presented which is efficient, robust, and scales linearly with the number of grid points. The...
On the application of phase relationships to complex structures. XVI. A random approach to structure determination
With triple-phase relationships treated as linear equations it is possible to refine a set of phases from given initial values. Phases so obtained are better than those found by...
Biomarker Identification by Feature Wrappers
Gene expression studies bridge the gap between DNA information and trait information by dissecting biochemical pathways into intermediate components between genotype and phenoty...
Publication Info
- Year
- 1993
- Type
- article
- Volume
- 3
- Issue
- 4
- Pages
- 315-331
- Citations
- 53
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
53
OpenAlex
Cite This
Shu Tezuka,
Pierre L’Ecuyer,
Raymond Couture
(1993).
On the lattice structure of the add-with-carry and subtract-with-borrow random number generators.
ACM Transactions on Modeling and Computer Simulation
, 3
(4)
, 315-331.
https://doi.org/10.1145/159737.159749
Identifiers
- DOI
- 10.1145/159737.159749