Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Test OCaml's PRNG against the new TestU01 testsuite #7073

Closed
vicuna opened this issue Dec 3, 2015 · 4 comments
Closed

Test OCaml's PRNG against the new TestU01 testsuite #7073

vicuna opened this issue Dec 3, 2015 · 4 comments

Comments

@vicuna
Copy link

vicuna commented Dec 3, 2015

Original bug ID: 7073
Reporter: @gasche
Status: acknowledged (set by @damiendoligez on 2016-02-10T16:53:25Z)
Resolution: open
Priority: low
Severity: feature
Target version: later
Category: standard library
Tags: testsuite

Bug description

In the previous weeks many of the Pseudo-Random Number Generators (PRNG) in Javascript implementation were found to be much weaker than they should -- even at non-security, non-crypto applications, I am not talking about crypto-randomness here. See the following article on LWN.net for a summary of the issues found in Chrome, Firefox and Safari:

http://lwn.net/SubscriberLink/666407/44be03d386807580/

(This link is made available from my LWN subscription. Consider subscribing to support this excellent source of technical journalism!)

The PRNG of web browsers were all found insufficient by Pierre L'Ecuyer's TestU01 set of statistical tests, which seems to be the modern version of the venerable Diehard PRNG testsuite.

http://simul.iro.umontreal.ca/testu01/tu01.html

It could be interesting to test OCaml's random generator against this new testsuite. Our implementation is non-standard, partly because of OCaml's integger tagging which makes the output domain of our PRNGs non-standard.

Note: the web browsers decided to move to a PRNG named xorshift128+, found at

http://xorshift.di.unimi.it/

@vicuna
Copy link
Author

vicuna commented Jan 2, 2016

Comment author: vigna

Erlang had a similar problem. I designed for them a variant of xorshift128+ based on 58-bits integers:

http://xorshift.di.unimi.it/xorshift116plus.c

If you're interested in a better/faster PRNG, and you use a different number of tagging bits, I can put up together a similar generator with a different bit size.

@vicuna
Copy link
Author

vicuna commented Feb 10, 2016

Comment author: @damiendoligez

As a first step, I'm happy to report that OCaml's PRNG (version 4.02.3) passes all the SmallCrush tests.

@github-actions
Copy link

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label May 11, 2020
@xavierleroy
Copy link
Contributor

I tested with dieharder and the Random PRNG passes with flying colors:

  • byte per byte: 110 tests passed, 4 tests weak, 0 tests failed
  • 32 bit words: 112 tests passed, 2 tests weak, 0 tests failed
  • 64-bit words: 114 tests passed, 0 tests weak, 0 tests failed.

Anyone is welcome to test with their statistical test of choice and report the results. I'll stick with dieharder, because I find it to be quite complete.

The conclusion is that the Random PRNG is solid, statistically speaking. Its only issue is that the API is missing a few operations, first and foremost splitting.

On this note I'll close this report.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants