EbTech/rust-algorithms

Random number generation

ekzhang opened this issue · 2 comments

ekzhang commented

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:

Do you have any opinions about RNGs here?

EbTech commented

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?

ekzhang commented

Ah, good question. So there's two factors at play here:

  1. The PRNG algorithm. Most algorithms (besides linear congruential generators) have good enough statistical properties that we'll be fine no matter what.
  2. Adversarial hacking. This is actually based on the seed of the pseudorandom number generator. No matter how good the PRNG algorithm is, if a hacker knows the seed, then they can always adversarially select a test case input.

There's a good blog post about this. Generally, using the system's high resolution time (std::time::SystemTime in nanoseconds from Unix epoch) is a good enough seed to prevent hacking.

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 unsafe { core::arch::x86::_rdtsc() } if that's desired. Not all competition websites have an open hacking phase where people generate adversarial stuff! :)

(see also: https://ekzlib.netlify.app/view/rng.cpp)