rand

README

rand

Fast, high quality alternative to math/rand and golang.org/x/exp/rand.

Compared to these packages, pgregory.net/rand:

• is API-compatible with all *rand.Rand methods,
• is significantly faster, while providing state-of-the-art generator quality,
• has simpler generator initialization:
  • rand.New() instead of rand.New(rand.NewSource(time.Now().UnixNano()))
  • rand.New(1) instead of rand.New(rand.NewSource(1))
• is deliberately not providing top-level functions like Float64() or Int() and the Source interface.

Benchmarks

All benchmarks were run on Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz (frequency-locked), linux/amd64.

Compared to math/rand:

name                    old time/op    new time/op    delta
Rand_New-8                19.4µs ± 0%     0.1µs ± 4%   -99.54%  (p=0.000 n=8+9)
Rand_ExpFloat64-8         12.8ns ± 1%     9.2ns ± 4%   -28.52%  (p=0.000 n=9+10)
Rand_Float32-8            10.3ns ± 2%     3.4ns ± 1%   -66.60%  (p=0.000 n=10+9)
Rand_Float64-8            7.07ns ± 2%    4.08ns ± 0%   -42.24%  (p=0.000 n=10+9)
Rand_Int-8                6.40ns ± 2%    3.82ns ± 0%   -40.20%  (p=0.000 n=10+9)
Rand_Int31-8              6.27ns ± 2%    2.64ns ± 0%   -57.90%  (p=0.000 n=10+8)
Rand_Int31n-8             16.9ns ± 2%     4.0ns ± 0%   -76.14%  (p=0.000 n=10+8)
Rand_Int31n_Big-8         16.9ns ± 1%     4.0ns ± 0%   -76.07%  (p=0.000 n=10+9)
Rand_Int63-8              6.19ns ± 2%    3.82ns ± 0%   -38.31%  (p=0.000 n=10+9)
Rand_Int63n-8             42.5ns ± 2%     5.6ns ± 0%   -86.86%  (p=0.000 n=10+8)
Rand_Int63n_Big-8         42.5ns ± 1%     9.5ns ± 0%   -77.69%  (p=0.000 n=10+10)
Rand_Intn-8               19.4ns ± 2%     5.6ns ± 0%   -71.29%  (p=0.000 n=10+9)
Rand_Intn_Big-8           45.2ns ± 1%     9.5ns ± 0%   -79.02%  (p=0.000 n=10+9)
Rand_NormFloat64-8        14.1ns ± 1%    10.0ns ± 0%   -29.04%  (p=0.000 n=10+9)
Rand_Perm-8               1.28µs ± 1%    0.39µs ± 0%   -69.35%  (p=0.000 n=9+10)
Rand_Read-8                455ns ± 1%     134ns ± 0%   -70.52%  (p=0.000 n=10+10)
Rand_Seed-8               17.5µs ± 1%     0.0µs ± 0%   -99.74%  (p=0.000 n=9+9)
Rand_Shuffle-8             696ns ± 2%     409ns ± 0%   -41.32%  (p=0.000 n=10+9)
Rand_ShuffleOverhead-8     576ns ± 2%     303ns ± 0%   -47.30%  (p=0.000 n=10+9)
Rand_Uint32-8             6.15ns ± 2%    2.61ns ± 1%   -57.56%  (p=0.000 n=10+9)
Rand_Uint64-8             8.57ns ± 2%    3.87ns ± 0%   -54.88%  (p=0.000 n=10+9)

name                    old alloc/op   new alloc/op   delta
Rand_New-8                5.42kB ± 0%    0.05kB ± 0%   -99.12%  (p=0.000 n=10+10)
Rand_Perm-8                 416B ± 0%      416B ± 0%      ~     (all equal)

name                    old allocs/op  new allocs/op  delta
Rand_New-8                  2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)
Rand_Perm-8                 1.00 ± 0%      1.00 ± 0%      ~     (all equal)

name                    old speed      new speed      delta
Rand_Read-8              563MB/s ± 1%  1908MB/s ± 0%  +239.15%  (p=0.000 n=10+10)
Rand_Uint32-8            650MB/s ± 2%  1531MB/s ± 1%  +135.57%  (p=0.000 n=10+9)
Rand_Uint64-8            934MB/s ± 2%  2069MB/s ± 0%  +121.60%  (p=0.000 n=10+9)

Compared to golang.org/x/exp/rand:

name                    old time/op    new time/op    delta
Rand_New-8                95.2ns ± 1%    88.9ns ± 4%    -6.68%  (p=0.000 n=10+9)
Rand_ExpFloat64-8         12.4ns ± 1%     9.2ns ± 4%   -25.85%  (p=0.000 n=10+10)
Rand_Float32-8            13.5ns ± 1%     3.4ns ± 1%   -74.38%  (p=0.000 n=9+9)
Rand_Float64-8            11.1ns ± 5%     4.1ns ± 0%   -63.29%  (p=0.000 n=10+9)
Rand_Int-8                7.37ns ± 5%    3.82ns ± 0%   -48.12%  (p=0.000 n=10+9)
Rand_Int31-8              7.10ns ± 4%    2.64ns ± 0%   -62.82%  (p=0.000 n=10+8)
Rand_Int31n-8             26.1ns ± 0%     4.0ns ± 0%   -84.49%  (p=0.000 n=10+8)
Rand_Int31n_Big-8         26.0ns ± 1%     4.0ns ± 0%   -84.50%  (p=0.000 n=9+9)
Rand_Int63-8              6.92ns ± 1%    3.82ns ± 0%   -44.82%  (p=0.000 n=9+9)
Rand_Int63n-8             26.0ns ± 1%     5.6ns ± 0%   -78.55%  (p=0.000 n=9+8)
Rand_Int63n_Big-8         39.8ns ± 0%     9.5ns ± 0%   -76.15%  (p=0.000 n=8+10)
Rand_Intn-8               26.0ns ± 1%     5.6ns ± 0%   -78.55%  (p=0.000 n=9+9)
Rand_Intn_Big-8           39.9ns ± 1%     9.5ns ± 0%   -76.21%  (p=0.000 n=10+9)
Rand_NormFloat64-8        14.0ns ± 0%    10.0ns ± 0%   -28.36%  (p=0.000 n=9+9)
Rand_Perm-8               1.42µs ± 1%    0.39µs ± 0%   -72.23%  (p=0.000 n=9+10)
Rand_Read-8                467ns ± 0%     134ns ± 0%   -71.29%  (p=0.000 n=9+10)
Rand_Seed-8               6.28ns ± 6%   46.18ns ± 0%  +635.79%  (p=0.000 n=10+9)
Rand_Shuffle-8            1.40µs ± 1%    0.41µs ± 0%   -70.75%  (p=0.000 n=9+9)
Rand_ShuffleOverhead-8    1.28µs ± 0%    0.30µs ± 0%   -76.26%  (p=0.000 n=10+9)
Rand_Uint32-8             6.70ns ± 0%    2.61ns ± 1%   -61.02%  (p=0.000 n=10+9)
Rand_Uint64-8             6.71ns ± 0%    3.87ns ± 0%   -42.35%  (p=0.000 n=10+9)
Rand_Uint64n-8            25.0ns ± 1%     5.6ns ± 0%   -77.59%  (p=0.000 n=10+10)
Rand_Uint64n_Big-8        40.0ns ± 1%     9.2ns ± 1%   -76.99%  (p=0.000 n=9+10)
Rand_MarshalBinary-8      36.7ns ± 2%     6.1ns ± 0%   -83.27%  (p=0.000 n=10+10)
Rand_UnmarshalBinary-8    5.31ns ± 0%    6.14ns ± 0%   +15.63%  (p=0.000 n=9+10)

name                    old alloc/op   new alloc/op   delta
Rand_New-8                 48.0B ± 0%     48.0B ± 0%      ~     (all equal)
Rand_Perm-8                 416B ± 0%      416B ± 0%      ~     (all equal)
Rand_MarshalBinary-8       16.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
Rand_UnmarshalBinary-8     0.00B          0.00B           ~     (all equal)

name                    old allocs/op  new allocs/op  delta
Rand_New-8                  2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)
Rand_Perm-8                 1.00 ± 0%      1.00 ± 0%      ~     (all equal)
Rand_MarshalBinary-8        1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)
Rand_UnmarshalBinary-8      0.00           0.00           ~     (all equal)

name                    old speed      new speed      delta
Rand_Read-8              548MB/s ± 0%  1908MB/s ± 0%  +248.24%  (p=0.000 n=9+10)
Rand_Uint32-8            597MB/s ± 0%  1531MB/s ± 1%  +156.55%  (p=0.000 n=10+9)
Rand_Uint64-8           1.19GB/s ± 0%  2.07GB/s ± 0%   +73.45%  (p=0.000 n=10+9)

FAQ

Why did you write this?

math/rand is both slow and not up to standards in terms of quality (but can not be changed because of Go 1 compatibility promise). golang.org/x/exp/rand improves the quality, but does not improve the speed, and it seems that there is no active development happening there.

How does this thing work?

This package builds on 3 primitives: raw 64-bit generation using sfc64, floating-point generation using floating-point multiplication, and integer generation in range using 32.64 or 64.128 fixed-point multiplication.

Why is it fast?

The primitives selected are (as far as I am aware) about as fast as you can go without sacrificing quality. On top of that, it is mainly making sure the compiler is able to inline code, and a couple of micro-optimizations.

Why no Source?

In Go (but not in C++ or Rust) it is a costly abstraction that provides no real value. How often do you use a non-default Source with math/rand?

Why no top-level functions?

Dislike for global mutable state. Also, without some kind of thread-local state they are very slow (because global state needs to be mutex-protected). If you like the convenience of top-level functions, math/rand is a fine choice.

Why sfc64?

I like it. It has withstood the test of time, with no known flaws or weaknesses despite a lot of effort and CPU-hours spent on finding them. Also, it provides guarantees about period length and distance between generators seeded with different seeds. And it is fast.

Why not...

...pcg?

A bit slow. Otherwise, pcg64dxsm is probably a fine choice.

...xoshiro/xoroshiro?

Quite a bit of controversy and people finding weaknesses in variants of this design. Did you know that xoshiro256**, which author describes as an "all-purpose, rock-solid generator" that "passes all tests we are aware of", fails them in seconds if you multiply the output by 57?

...splitmix?

With 64-bit state and 64-bit output, splitmix64 outputs every 64-bit number exactly once over its 2^64 period — in other words, the probability of generating the same number is 0. A birthday test will quickly find this problem.

...wyrand?

An excellent generator if you are OK with slightly lower quality. Because its output function (unlike splitmix) is not a bijection, some outputs are more likely to appear than others. You can easily observe this non-uniformity with a birthday test.

...romu?

Very fast, but relatively new and untested. Also, no guarantees about the period length.

Status

pgregory.net/rand is alpha software. API breakage and bugs should be expected before 1.0.

License

pgregory.net/rand is licensed under the Mozilla Public License Version 2.0.

Documentation

Overview

Package rand implements pseudo-random number generators unsuitable for security-sensitive work.

This package is considerably faster and generates higher quality random than the math/rand package. However, this package's outputs might be predictable regardless of how it's seeded. For random numbers suitable for security-sensitive work, see the crypto/rand package.

Index

• type Rand
  • func New(seed ...uint64) *Rand
  • func (r *Rand) ExpFloat64() float64
  • func (r *Rand) Float32() float32
  • func (r *Rand) Float64() float64
  • func (r *Rand) Int() int
  • func (r *Rand) Int31() int32
  • func (r *Rand) Int31n(n int32) int32
  • func (r *Rand) Int63() int64
  • func (r *Rand) Int63n(n int64) int64
  • func (r *Rand) Intn(n int) int
  • func (r *Rand) MarshalBinary() ([]byte, error)
  • func (r *Rand) NormFloat64() float64
  • func (r *Rand) Perm(n int) []int
  • func (r *Rand) Read(p []byte) (n int, err error)
  • func (r *Rand) Seed(seed uint64)
  • func (r *Rand) Shuffle(n int, swap func(i, j int))
  • func (r *Rand) Uint32() uint32
  • func (r *Rand) Uint32n(n uint32) uint32
  • func (r *Rand) Uint64() uint64
  • func (r *Rand) Uint64n(n uint64) uint64
  • func (r *Rand) UnmarshalBinary(data []byte) error
• type Zipf
  • func NewZipf(r *Rand, s float64, v float64, imax uint64) *Zipf
  • func (z *Zipf) Uint64() uint64

Types

type Rand

type Rand struct {
	// contains filtered or unexported fields
}

Rand is a pseudo-random number generator based on the SFC64 algorithm by Chris Doty-Humphrey.

SFC64 has 256 bits of state, average period of ~2^255 and minimum period of at least 2^64. Generators returned by New (with empty or distinct seeds) are guaranteed to not run into each other for at least 2^64 iterations.

func New

func New(seed ...uint64) *Rand

New returns an initialized generator. If seed is empty, generator is initialized to a non-deterministic state. Otherwise, generator is seeded with the values from seed. New panics if len(seed) > 3.

func (*Rand) ExpFloat64

func (r *Rand) ExpFloat64() float64

ExpFloat64 returns an exponentially distributed float64 in the range (0, +math.MaxFloat64] with an exponential distribution whose rate parameter (lambda) is 1 and whose mean is 1/lambda (1). To produce a distribution with a different rate parameter, callers can adjust the output using:

sample = ExpFloat64() / desiredRateParameter

func (*Rand) Float32

func (r *Rand) Float32() float32

Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0, 1.0).

func (*Rand) Float64

func (r *Rand) Float64() float64

Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0, 1.0).

func (*Rand) Int

func (r *Rand) Int() int

Int returns a non-negative pseudo-random int.

func (*Rand) Int31

func (r *Rand) Int31() int32

Int31 returns a non-negative pseudo-random 31-bit integer as an int32.

func (*Rand) Int31n

func (r *Rand) Int31n(n int32) int32

Int31n returns, as an int32, a non-negative pseudo-random number in the half-open interval [0, n). It panics if n <= 0.

func (*Rand) Int63

func (r *Rand) Int63() int64

Int63 returns a non-negative pseudo-random 63-bit integer as an int64.

func (*Rand) Int63n

func (r *Rand) Int63n(n int64) int64

Int63n returns, as an int64, a non-negative pseudo-random number in the half-open interval [0, n). It panics if n <= 0.

func (*Rand) Intn

func (r *Rand) Intn(n int) int

Intn returns, as an int, a non-negative pseudo-random number in the half-open interval [0, n). It panics if n <= 0.

func (*Rand) MarshalBinary

func (r *Rand) MarshalBinary() ([]byte, error)

MarshalBinary returns the binary representation of the current state of the generator.

func (*Rand) NormFloat64

func (r *Rand) NormFloat64() float64

NormFloat64 returns a normally distributed float64 in the range -math.MaxFloat64 through +math.MaxFloat64 inclusive, with standard normal distribution (mean = 0, stddev = 1). To produce a different normal distribution, callers can adjust the output using:

sample = NormFloat64() * desiredStdDev + desiredMean

func (*Rand) Perm

func (r *Rand) Perm(n int) []int

Perm returns, as a slice of n ints, a pseudo-random permutation of the integers in the half-open interval [0, n).

func (*Rand) Read

func (r *Rand) Read(p []byte) (n int, err error)

Read generates len(p) random bytes and writes them into p. It always returns len(p) and a nil error.

func (*Rand) Seed

func (r *Rand) Seed(seed uint64)

Seed uses the provided seed value to initialize the generator to a deterministic state.

func (*Rand) Shuffle

func (r *Rand) Shuffle(n int, swap func(i, j int))

Shuffle pseudo-randomizes the order of elements. n is the number of elements. Shuffle panics if n < 0. swap swaps the elements with indexes i and j.

func (*Rand) Uint32

func (r *Rand) Uint32() uint32

Uint32 returns a pseudo-random 32-bit value as a uint32.

func (*Rand) Uint32n

func (r *Rand) Uint32n(n uint32) uint32

Uint32n returns, as a uint32, a pseudo-random number in [0, n). Uint32n(0) returns 0.

func (*Rand) Uint64

func (r *Rand) Uint64() uint64

Uint64 returns a pseudo-random 64-bit value as a uint64.

func (*Rand) Uint64n

func (r *Rand) Uint64n(n uint64) uint64

Uint64n returns, as a uint64, a pseudo-random number in [0, n). Uint64n(0) returns 0.

func (*Rand) UnmarshalBinary

func (r *Rand) UnmarshalBinary(data []byte) error

UnmarshalBinary sets the state of the generator to the state represented in data.

type Zipf

type Zipf struct {
	// contains filtered or unexported fields
}

A Zipf generates Zipf distributed variates.

func NewZipf

func NewZipf(r *Rand, s float64, v float64, imax uint64) *Zipf

NewZipf returns a Zipf variate generator. The generator generates values k ∈ [0, imax] such that P(k) is proportional to (v + k) ** (-s). Requirements: s > 1 and v >= 1.

func (*Zipf) Uint64

func (z *Zipf) Uint64() uint64

Uint64 returns a value drawn from the Zipf distribution described by the Zipf object.