dueling generators

approach

this one is rust only. the starting values are the last word on each input line. each generator multiplies by its factor modulo i32::MAX (2³¹ − 1), and a pair counts when the low 16 bits match, checked with a mask.

part 1 runs both generators 40 million times. part 2 runs 5 million rounds, but step keeps advancing each generator until its value is a multiple of 4 (for a) or 8 (for b).

the trick

compare only the low 16 bits with & mask, and let a compiled loop take care of the tens of millions of rounds.

fn step(mut prev: i64, base: i64, mult: i64, modulo: i64) -> i64 {
    let mask = (1 << 16) - 1;
    let mut nxt = (prev * base) % modulo;
    while (nxt % mult) != 0 {
        prev = nxt;
        nxt = (prev * base) % modulo;
    }
    return nxt;
}