lemire / testingrng Goto Github PK
View Code? Open in Web Editor NEWTesting common random-number generators (RNG)
License: Apache License 2.0
Testing common random-number generators (RNG)
License: Apache License 2.0
uint64_t wyrng(uint64_t *s){
*s+=0x60bee2bee120fc15ull;
__uint128_t t=(__uint128_t)(*s^0x1b03738712fad5c9ull)*(*s);
return (t>>64)^t;
}
Dear Lemire:
In your wyrng simplification code, you missed a inline keyword which make wyrng slower.
inline uint64_t wyhash64_stateless(uint64_t *seed) {
adding this inline, wyrng is the fastest :-)
Hello, could you add my PRNG which I designed for hashing, to your test suite? The project page is https://github.com/avaneev/prvhash
You'll just need prvhash_core.h
file.
The minimal PRNG code follows. I would estimate the minimal period as 2^160
. The Seed
can be set to any value, each value puts the PRNG at random position.
#include "prvhash_core.h"
#include <stdio.h>
int main()
{
const uint64_t rc = 1ULL << 27;
uint64_t Seed = 0;
uint64_t lcg = 0;
uint64_t Hash = 0;
uint64_t v = 0;
uint64_t i;
for( i = 0; i < rc; i++ )
{
v = prvhash_core64( &Seed, &lcg, &Hash );
}
printf( "%llu\n", v );
}
I've used your AES-CTR implementation in a couple of projects. Over time, I've made a few changes. It's compatible with boost/C++11 , and templated over all integral types and by UNROLL_COUNT.
On my machines, an UNROLL_COUNT of 8 (rather than 4) was measurably but not enormously faster. (~10% speed increase.)
I don't want to assume you want it included, but I'm mentioning it just in case. Here's a link to the current version I use.
It will not affect PRNG testing, but initialize stateless version w/ seed x
actually mean initialize using splitmix64 with seed = (x - 1) * splitmix_step
It might be better to have both version do the same thing.
Idea: remove the stateless first line for calculating z, call this stateless_aux(z)
splitmix64() == stateless_aux( splitmix64_x += splitmix_step )
stateless(x,i) == stateless_aux( x + (i + 1) * splitmix_step )
Now: stateless(x, 0) == splitmix64() with seed x
Code changes are tiny.
Instead of stateless(x + i), now is stateless(x, i)
I think there might be a problem here:
Line 107 in b608ed3
It probably should be calling populate64
instead. Now unless I'm mistaken only half of the buffer gets filled.
Files produced by some scripts overwrite each other on macOS.
Stefan Kanthak wrote:
While Lehmer’s multiplicative congruential generator is fast, it does NOT pass PractRand 0.94. In [does it beat the minimal standard](url
http://www.pcg-random.org/posts/does-it-beat-the-minimal-standard.html) and [too big to fail](url
http://www.pcg-random.org/posts/too-big-to-fail.html) Melissa O’Neill tested these generators with PractRand 0.93, where they passed.
Consider an idea from George Marsaglia instead: save and add the “carry” of the multiplication, giving a multiply-with-carry generator:
uint64_t seed = 0, carry = 0x...;
uint64_t square_with_carry() {
__uint128_t mwc = (__uint128_t) seed * 0x... + carry;
seed = mwc;
carry = square >> 64;
return seed;
}
uint64_t seed = 0, carry = 0xb5ad4eceda1ce2a9;
uint64_t square_with_carry() {
__uint128_t square = (__uint128_t) seed * seed + carry;
seed = square;
carry = square >> 64;
return seed;
}
This 64-bit generator passes the PractRand test suite (version 0.94) at least up to 4 TB!
See [source](url
https://godbolt.org/z/qFfRYh) and [source](url
https://godbolt.org/z/4jf1i_) for the code generated by GCC 8.2 and clang 7.0 respectively, plus [VC source](url
https://godbolt.org/z/9RRnBL) for an implementation using Microsofts Visual C compiler (which does not support a 128 bit integer type).
I used the latter for the PractRand test.
Hi, I was playing around with this and couldn't reproduce the results. Minor issue was that runtests.sh
was missing the #!/bin/bash
at the beginning, so non-standard shells chokoe on it... but the bigger issue was that often tests aborted with a double-free, while being reported as successful. Example:
> ./runtests.sh [11:50:31]
Testing 512GB of data per run
Note: running the tests longer could expose new failures.
# RUNNING testmitchellmoore Outputting result to testmitchellmoore.log
Failure!
# RUNNING testmersennetwister Outputting result to testmersennetwister.log
free(): double free detected in tcache 2
./runtests.sh: line 11: 10915 Broken pipe ./$t
10916 Aborted | ./RNG_test stdin64 -tlmax $MEM > $filelog
Success!
# RUNNING testxorshift-k4 Outputting result to testxorshift-k4.log
Failure!
# RUNNING testxorshift-k5 Outputting result to testxorshift-k5.log
Failure!
# RUNNING testwidynski Outputting result to testwidynski.log
free(): double free detected in tcache 2
./runtests.sh: line 11: 10935 Broken pipe ./$t
10936 Aborted | ./RNG_test stdin64 -tlmax $MEM > $filelog
Success!
# RUNNING testaesctr Outputting result to testaesctr.log
free(): double free detected in tcache 2
./runtests.sh: line 11: 10941 Broken pipe ./$t
10942 Aborted | ./RNG_test stdin64 -tlmax $MEM > $filelog
Success!
# RUNNING testaesdragontamer Outputting result to testaesdragontamer.log
free(): double free detected in tcache 2
./runtests.sh: line 11: 10947 Broken pipe ./$t
10948 Aborted | ./RNG_test stdin64 -tlmax $MEM > $filelog
Success!
# RUNNING testv8xorshift128plus -H Outputting result to testv8xorshift128plus-H.log
free(): double free detected in tcache 2
./runtests.sh: line 11: 10953 Broken pipe ./$t
10954 Aborted | ./RNG_test stdin64 -tlmax $MEM > $filelog
Success!
# RUNNING testv8xorshift128plus Outputting result to testv8xorshift128plus.log
Failure!
# RUNNING testxorshift128plus -H Outputting result to testxorshift128plus-H.log
free(): double free detected in tcache 2
./runtests.sh: line 11: 10965 Broken pipe ./$t
10966 Aborted | ./RNG_test stdin64 -tlmax $MEM > $filelog
Success!
# RUNNING testxorshift128plus Outputting result to testxorshift128plus.log
...
I tracked the double-free down enough to this backtrace:
Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1 0x00007f996e51d537 in __GI_abort () at abort.c:79
#2 0x00007f996e5766c8 in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7f996e684e31 "%s\n")
at ../sysdeps/posix/libc_fatal.c:155
#3 0x00007f996e57d9ba in malloc_printerr (str=str@entry=0x7f996e687150 "free(): double free detected in tcache 2")
at malloc.c:5347
#4 0x00007f996e57efb5 in _int_free (av=0x7f996e6b6b80 <main_arena>, p=0x56554fb6cad0, have_lock=0) at malloc.c:4201
#5 0x000056554dd8bd76 in std::vector<PractRand::TestResult, std::allocator<PractRand::TestResult> >::~vector() ()
#6 0x000056554dd76595 in show_checkpoint(TestManager*, int, unsigned long long, double, bool, double, bool) [clone .cold] ()
#7 0x000056554dd7c609 in main ()
but unfortunately looking at show_checkpoint()
didn't show anything obviously wrong and I don't have time to keep digging into this problem.
Thank you for your work!
Platform: Debian 11 Linux, x86_64, gcc
This looks like it's an incorrect usage of splitmix64_stateless
Line 22 in bfd776b
I would expect to be using the small seed as the seed to a splitmix64 generator and use two sequential values returned by that generator as the 128bit seed for the target generator (perhaps after skipping some values for mixing).
But this +1
doesn't get the next value instead it gets the first result of the next higher seed, effectively using a constant for the generator of 1
rather than 0x9e3779b97f4a7c15
. This is a very poor value to use as a substitute for "Weyl sequence" that looks to be related to the issue that Dr. O'Neill describes in her "bugs in splitmix" post.
#ifndef ZIBRI128_H
#define ZIBRI128_H
/* Modified by D. Lemire, August 2017 */
#include "splitmix64.h"
#include <stdint.h>
// state for zibri128
uint64_t zibri128_s[2];
static inline uint64_t rotr(const uint64_t x, int k) {
return (x >> k) | (x << (64 - k));
}
// call this one before calling zibri128
static inline void zibri128_seed(uint64_t seed) {
zibri128_s[0] = splitmix64_stateless(seed);
zibri128_s[1] = splitmix64_stateless(seed + 1);
}
// returns random number, modifies zibri128_s
static inline uint64_t zibri128(void) {
const uint64_t s0 = zibri128_s[0];
const uint64_t s1 = zibri128_s[1];
const uint64_t result = rotr(s0 + s1,8);
zibri128_s[0] = result;
zibri128_s[1] = s0;
return result;
}
#endif // ZIBRI128_H
is the fastest so far...
Thanks for this nice rng test suite.
I could not find summarize.pl file however. What does it do? how is a blip defined?
Hello. I have been trying to perform testU01. I am unable to understand what should be the input to tests? I performed NIST tests and all I have to provide NIST tests is a random sequence in a text file generated by my RNG. Does testu01 works the same? or do I have to provide the whole code of my RNG to testu01 suite and it will generate the sequence itself and then test it. There is almost no help or very little help regarding the usage of testu01 online. I would appreciate any kind of help. Thank you!
Dear Lemire:
I am a fan of you :-)
Recently I developed a new fastest hash function wyhash, which is recognized by SMHasher. Based on it, I developed a new PRNG which is the fastest based on your benchmark, and passes practrand and BigCrush (those there is a p-value of 2e-4 which is common if we consider multiple testing). It is located at https://github.com/wangyi-fudan/wyhash
(Issue withdrawn)
VeraCrypt started using Jitter RNG by Stephan Mueller.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.