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

MIT license

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 232-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 232-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