-
Notifications
You must be signed in to change notification settings - Fork 216
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
Random number generation #20
Comments
Hm I haven't studied our options too closely. Technically, the factorization algorithm introduced in #13 also needs randomness. The trouble is providing randomness guarantees strong enough to evade Codeforces hacking. Last I checked, I think the standard library doesn't yet expose the operating system's randomness primitives. Is there anything we can do? |
Ah, good question. So there's two factors at play here:
There's a good blog post about this. Generally, using the system's high resolution time ( For now I'll focus on just resolving issue 1 though, which is the PRNG algorithm itself, and we can add utilities for robustly seeding from time or (see also: https://ekzlib.netlify.app/view/rng.cpp) |
One problem I see with using Rust in programming competition websites is that we can't pull in external dependencies like
rand
. Is there interest in simply offering a very short and sweet random number generator?I was thinking about implementing a simple Treap for a dynamic BBST implementation (which is simple enough in Rust's ownership semantics), so maybe it makes sense to just embed a simple PRNG in the file. Options:
SmallRng
used inrand
: https://docs.rs/rand/0.8.4/src/rand/rngs/xoshiro256plusplus.rs.htmlDo you have any opinions about RNGs here?
The text was updated successfully, but these errors were encountered: