5 releases
0.1.4 | Jun 27, 2024 |
---|---|
0.1.3 | Jun 25, 2024 |
0.1.2 | Jun 21, 2024 |
0.1.1 | Jun 21, 2024 |
0.1.0 | Jun 20, 2024 |
#886 in Algorithms
65KB
1K
SLoC
Simple Random
Simple pseudo-random number generators.
Intro
This project provides simplerandom
, simple pseudo-random number
generators.
Features:
- Main API functions:
- Seed
- Generate "next" random value
- "Jump-ahead" (also known as "discard" in C++) to skip the generator ahead by 'n' samples.
- Simple algorithms that are easily ported to different languages.
- Safe seeding. Many generators have some "bad" state values that must be avoided. The seed functions for all generators ensure that any "bad" state values are avoided, and replaced by a suitable alternative initial state.
- These random number generators have been implemented in the following
languages:
- C
- Python
- Rust
- Same numeric output in each supported language. It can be useful to be able to implement the identical algorithm on muliple platforms and/or languages.
- Simple algorithms and state size appropriate for limited RAM and ROM (e.g. in embedded systems).
- Decent cross-platform support.
- Various OS.
- Various processors, 8- to 64-bit.
- Implement target language's API idioms and/or existing random number generator API.
- Reasonable statistical properties of pseudo-random output (though not for all generators provided).
Algorithms
Most algorithms were obtained from two newsgroup posts by George Marsaglia [mars1] [mars2]. However, some modifications have been made. From [rose1], it seems that the SHR3 algorithm defined in [mars1] is flawed and should not be used. It doesn't actually have a period of 2^{32}-1 as expected, but has 64 different cycles, some with very short periods. The SHR3 in the 2003 post is very similar, but with two shift values swapped. It has a period of 2^{32}-1 as expected.
We still find KISS from [mars1] useful mainly because it uses 32-bit calculations for MWC, which can be more suitable for small embedded systems. So we define KISS that uses a MWC based on [mars1], but the Cong and SHR3 from [mars2].
From Pierre L'Ecuyer [lecuyer1] [lecuyer2], the Combined LFSR (Tausworthe) LFSR113 algorithm [lecuyer3] and LFSR88 (aka Taus88) have been implemented.
Random Number Generators Provided
The following pseudo-random number generators are provided:
Generator | Notes |
---|---|
MWC1 |
Two 32-bit MWCs combined. From [mars1]. |
MWC2 |
Very similar to MWC1 , but slightly modified to improve its statistical properties. |
Cong |
From [mars2]. |
SHR3 |
From [mars2]. |
MWC64 |
A single 64-bit multiply-with-carry calculation. From [mars2]. |
KISS |
Combination of MWC2, Cong and SHR3. Based on [mars1] but using Cong and SHR3 from [mars2], and the modified MWC. |
KISS2 |
Combination of MWC64, Cong and SHR3. From [mars2]. |
LFSR113 |
Combined LFSR (Tausworthe) random number generator by L'Ecuyer. From [lecuyer1] [lecuyer3]. |
LFSR88 |
Combined LFSR (Tausworthe) random number generator by L'Ecuyer. From [lecuyer2]. |
License
The code is released under the MIT license. See LICENSE.txt for details.
References
[mars1]
Random Numbers for C: End, at last?
George Marsaglia
Newsgroup post, sci.stat.math and others, Thu, 21 Jan 1999
[mars2]
RNGs
George Marsaglia
Newsgroup post, sci.math, 26 Feb 2003
[rose1]
KISS: A Bit Too Simple
Greg Rose
Qualcomm Inc.
[lecuyer1]
Tables of Maximally-Equidistributed Combined LFSR Generators
Pierre L'Ecuyer
Mathematics of Computation, 68, 225 (1999), 261–269.
[lecuyer2]
Maximally Equidistributed Combined Tausworthe Generators
P. L'Ecuyer
Mathematics of Computation, 65, 213 (1996), 203–213.
[lecuyer3]
LFSR113 C double implementation
Pierre L'Ecuyer
Dependencies
~200KB