Giter VIP home page Giter VIP logo

go-prng-test's Introduction

Some tests for some properties of the math/rand PRNG which are mainly related to its initialization

The PRNG of the math/rand package is implemented by the rngSource struct, which has the Seed method, whose beginning contains a surprise:

	seed = seed % int32max
	if seed < 0 {
		seed += int32max
	}
	if seed == 0 {
		seed = 89482311
	}

See https://tip.golang.org/src/math/rand/rng.go

(The constant int32max defined as (1 << 31) - 1 in the same file.)

The Seed function throws away entropy, even though even the full 64 bits (seed is of type int64) wouldn't be enough to fill the huge 4856-byte state of the PRNG! This is actually partially documented, at least for the default Source, for which the documentation says:

Seed values that have the same remainder when divided by 2³¹-1 generate the same pseudo-random sequence.

This blog post prompted me to do some tests to check how the small amount (relative to state size) of input entropy affects certain qualities of the rngSource PRNG.

Terminology

I'm not an expert (far from it), so it's possible I'm abusing some terminology myself. I'll give this definition though, it might help someone.

The pseudo-random stream/sequence, mentioned in several places in this repo, refers to the ordered collection of number values generated by a PRNG (pseudo-random number generator). The "pseudo" is because these are deterministic algorithms, as opposed to true randomness.

Sometimes I refer to positions within the stream, position 0 is the first generated value, position 1 is the second one, etc.

Results

See this for the results regarding generated values that belong to a small predetermined range.

See this for the results of a test that concetrates on math/rand.Rand.Int63, and the first position of its pseudo-random sequences, counting how many distinct generated values exist.

Go 2?

Note that the experimental code in golang.org/x/exp/rand, currently the intended replacement for math/rand in Go 2, (apart from implementing a better PRNG algorithm) has the method UnmarshalBinary (on PCGSource), which kind of prevents similar issues there, as it makes it possible to initialize the entire 128-bit state of the PRNG. But PCGSource also has a Seed method, which only takes a single uint64 input value as the seed, and the Source interface in golang.org/x/exp/rand only includes the Seed method. I hope the Source interface gets a redesign before any breaking changes to Go are made, maybe the API could be based on a sponge/duplex construction (which would be quite flexible, enable reseeding, but would perhaps be a better fit to a PRNG that actually is a sponge/duplex, unlike the simpler PCG family).

go-prng-test's People

Contributors

nsajko avatar

Stargazers

 avatar  avatar  avatar

Watchers

 avatar  avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.