tree 1fcc001eae3ceada580887dad3f806ffdefacb2c
parent be79676510e5ce293c77bb087cdab4796a461bdb
author Rob Pike <r@golang.org> 1431731982 -0700
committer Rob Pike <r@golang.org> 1504487823 +0000

x/exp/rand: new rand package

This is an approximately compatible new implementation of math/rand.
The differences are:

Source emits uint64s rather than positive int64s.
The method is now
	Uint64() uint64; not
	Int63() int64
There are corresponding new methods on Rand:
	func (r *Rand) Uint64() uint64
	func (r *Rand) Uint64n(n uint64) uint64
The default Source is now an exported type, PCGSource.

The default Source holds 128 bits of state for a 64-bit
result. This has good statistical properties but is slower,
largely because the multiplication step is inefficient.
That can be improved with assembler.

Thus the default Source has a two 64-bit words of state (in
math/rand it has 607 words). It is thus practical to have
millions of Sources in the address space, making it well
suited to lock-free simulations using random numbers.

Benchmarks:

benchmark                        old ns/op     new ns/op     delta
BenchmarkInt63Threadsafe-4       20.0          24.4          +22.00%
BenchmarkInt63Unthreadsafe-4     6.32          13.0          +105.70%
BenchmarkIntn1000-4              16.4          23.8          +45.12%
BenchmarkInt63n1000-4            25.5          23.8          -6.67%
BenchmarkInt31n1000-4            14.2          23.8          +67.61%
BenchmarkFloat32-4               11.8          21.0          +77.97%
BenchmarkFloat64-4               8.76          18.3          +108.90%
BenchmarkPerm3-4                 80.3          94.3          +17.43%
BenchmarkPerm30-4                627           814           +29.82%

The new generator is PCG XSL RR 128/64 (LCG) from
http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf
It has been tested against the C version and generates the same
output if initialized to the same value.
See also http://www.pcg-random.org/.

TODO: Improve performance, make initialization better.

Independently, this fixes a bug in the bias-prevention code that
appears, in this package, in Uint64n.

This also exports LockedSource:
Update golang/go#21393.

Change-Id: I48a410fade5d78b8ec993cc1210b96b7a9ab462f
Reviewed-on: https://go-review.googlesource.com/10161
Reviewed-by: Rob Pike <r@golang.org>