线性同余发生器输出错误

Question

我创建了一个线性同余生成器(LCG)，但它似乎给了我错误的输出。

// Instance variables 
private long currentRandomNumber;
private long a;
private long c;
private long m;
public static void main(String[] args) {
// perform calculations and tests here
final long seed = 99L;

// Java's java.util.Random class values (according to Wikipedia):
long a = 25214903917L;
long c = 11L;
long m = 2^48L;

LCG lcg = new LCG(a, c, m, seed);

System.out.println("Sequence of LCG    class: " + lcg.nextRandom() + ", " + lcg.nextRandom() + ", " + lcg.nextRandom() + ", " + lcg.nextRandom() + ", " + lcg.nextRandom());
}
public LCG(long seed, long a, long c, long m) {
currentRandomNumber = seed;
this.a = a;
this.c = c;
this.m = m;
}
// Implementation of the recurrence relation of the generator
public long nextRandom() {
currentRandomNumber = (a * currentRandomNumber + c) % m;
return currentRandomNumber;
}

我得到的输出是:

Sequence of LCG    class: 28, 61, 28, 61, 28

我使用了a、c和m的这些值，因为我读到java.util.Random类也使用这些值。但是对同一个种子使用这个类会得到不同的答案。我也用其他的计算器检查了一下，我的答案也不匹配。我不知道哪里出错了。

Answer 1

LCG要求大模数

线性同余发生器的关键之一是m必须足够大。或者，您可以快速找到重复的子序列，因为模运算总是为任何等差数列生成重复的子序列。然而，如果足够大，一个重复的子序列本身就会很长，所以它看起来不会重复。

long m = 2^48L;

是50。^不做您期望的事情。是2 XOR 48而不是2的48次方。所以使用

long m = 1L << 48;  // or (long) Math.pow(2, 48)

。然后你会得到

Sequence of LCG    class: 2496275487794, 103243855293781, 72264694917948, -37076138618729, -26695784318378

为什么与java.util.Random不完全相同

根据我的经验，实现几乎总是伴随着启发式。这里是用OpenJDK 15使用的启发式方法重新实现的代码，根据OpenJDK/生成nextIntegerjdk15。特别是从198行到206行。

import java.lang.Math;
import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;
class LCG {
private AtomicLong currentRandomNumber;
//private long a;
//private long c;
//private long m;
private int bits = 32;
private long addend = 0xBL;              // your `c` is here!
private long mask = (1L << 48) - 1;      // your `m` is here!
private long multiplier = 0x5DEECE66DL;  // your `a` is here!
public LCG(long seed, long a, long c, long m) {
currentRandomNumber = new AtomicLong((seed ^ multiplier) & mask);
//this.a = a;
//this.c = c;
//this.m = m;
}
public long nextRandom() {
long oldseed, nextseed;
AtomicLong seed = this.currentRandomNumber;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));  // your `m` is here again
}
}
public class main {
public static void main(String[] args) {
long seed = 99L;
long a = 25214903917L;
long c = 11L;
long m = (long) Math.pow(2, 48);
LCG lcg = new LCG(seed, a, c, m);
Random random = new Random(seed);
System.out.println(lcg.nextRandom());
System.out.println(random.nextInt());
}
}

如果使用OpenJDK 15编译代码，您将看到lcg.nextRandom()和random.nextInt()生成相同的整数。在重新实现时，我发现旧的OpenJDK使用了不同的启发式。