search

smol-rs / fastrand

A simple and fast random number generator
Apache License 2.0
409 stars 35 forks source link

Switch to Wyrand #14

Closed SabrinaJewson closed 3 years ago

SabrinaJewson commented 3 years ago

Wyrand is faster than PCG and also passes all of the tests.

PCG benchmarks:

test shuffle_fastrand   ... bench:         405 ns/iter (+/- 9)
test u32_fastrand       ... bench:      13,779 ns/iter (+/- 657)
test u8_fastrand        ... bench:      13,771 ns/iter (+/- 696)

Wyrand benchmarks:

test shuffle_fastrand ... bench:         225 ns/iter (+/- 2)
test u32_fastrand     ... bench:      11,464 ns/iter (+/- 317)
test u8_fastrand      ... bench:      12,402 ns/iter (+/- 304)

Closes #19

taiki-e commented 3 years ago

It seems the current implementation of this PR vulnerable to some known bad seeds: https://github.com/wangyi-fudan/wyhash/pull/100 https://github.com/ManDeJan/zig-wyhash/issues/2 https://github.com/eldruin/wyhash-rs/issues/6

SabrinaJewson commented 3 years ago

Does this apply to the RNG? The wyhash maintainer recently removed the _wyp default secret, but the wyrand implementation still uses it.

taiki-e commented 3 years ago

Thanks!

taiki-e commented 3 years ago

Published in 1.5.0

flyingmutant commented 3 years ago

I'd say it is a bit careless to say that "wyrand passes all of the tests", it certainly does not. Wyrand can only generate a subset of all u64 values (see https://github.com/wangyi-fudan/wyhash/issues/16), and even if we consider that to not be a problem by itself, it leads to easily detectable biases. For example, the number of duplicates you get is consistently much higher than expected from random data: https://gist.github.com/flyingmutant/cb69e96872023f9f580868e746d1128a