我创建了一个线性同余生成器 (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 类也使用这些值。但是使用相同种子的此类会给出不同的答案。我还检查了其他 lcg 计算器,我的答案也不匹配。我不知道出了什么问题。
最佳答案
LCG 需要大模数
Linear congruential generator的关键之一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 /
jdk15 生成 nextInt
eger 。特别是根据lines from 198 to 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 使用不同的启发式方法。
关于java - 线性同余发生器给出错误的输出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65921545/