java - java中使用线性同余方程的实现

Question

我在 Random 类下看到 Java 中的 LCG 实现，如下所示:

/*
 * This is a linear congruential pseudorandom number generator, as
 * defined by D. H. Lehmer and described by Donald E. Knuth in
 * <i>The Art of Computer Programming,</i> Volume 3:
 * <i>Seminumerical Algorithms</i>, section 3.2.1.
 *
 * @param  bits random bits
 * @return the next pseudorandom value from this random number
 *         generator's sequence
 * @since  1.1
 */

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

但下面的链接告诉 LCG 应该采用以下形式:x2=(ax1+b)modM

https://math.stackexchange.com/questions/89185/what-does-linear-congruential-mean

但是上面的代码看起来并不类似。相反，它使用 & 代替模运算，如下行

nextseed = (旧种子 * 乘数 + 加数) & 掩码;

有人可以帮助我理解这种使用 & 代替模运算的方法吗？

Answer 1

使用 2^n - 1 形式的掩码进行按位与运算与计算模 2^n 的数字相同:任何 1 的较高位该数字是2^n的倍数，因此可以安全地丢弃。但请注意，如果将模数设置为 2 的幂(而不是 2 的幂减一)，则某些乘法器/加数组合的效果非常差。该代码很好，但请确保它适合您的常量。