quickcheck icon indicating copy to clipboard operation
quickcheck copied to clipboard

Cannot use Rng methods on `Gen` when implementing `Arbitrary`

Open nbraud opened this issue 3 years ago • 5 comments

I noticed when trying to update a project to quickcheck 1.x, that Gen is now an opaque struct and users implementing Arbitrary can only use Gen::choose to get randomness. This isn't sufficient in some usecases, which were previously served by using Gen's Rng methods: for instance, in uutils' factor I need to draw integers from large ranges known at runtime, to generate integers of known factorization:

impl quickcheck::Arbitrary for Factors {
    fn arbitrary(gen: &mut quickcheck::Gen) -> Self {
        use rand::Rng;
        let mut f = Factors::one();
        let mut g = 1u64;
        let mut n = u64::MAX;

        // Adam Kalai's algorithm for generating uniformly-distributed
        // integers and their factorization.
        //
        // See Generating Random Factored Numbers, Easily, J. Cryptology (2003)
        'attempt: loop {
            while n > 1 {
                n = gen.gen_range(1, n);
                if miller_rabin::is_prime(n) {
                    if let Some(h) = g.checked_mul(n) {
                        f.push(n);
                        g = h;
                    } else {
                        // We are overflowing u64, retry
                        continue 'attempt;
                    }
                }
            }

            return f;
        }
    }
}

(Technically, I could repeatedly use gen.choose(&[0, 1]) to draw individual, random bits, but this would be beyond silly)

nbraud avatar Mar 16 '21 20:03 nbraud