I created a linear congruential generator (LCG), but it appears to give me the wrong output.
// 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;
}
The output I get is:
Sequence of LCG class: 28, 61, 28, 61, 28
I used these values of a,c and m because I read that the java.util.Random class uses these values too. But usage of this class with the same seed gives different answers. I also checked with other lcg calculators and my answers do not match these either. I have no idea what went wrong.
LCG Requires a Big Modulus
One of the key of Linear congruential generator is that
mshould be big enough. Or, you quickly find repeated sub-sequences because modulo operation always generates repeated sub-sequences for any arithmetic progressions. If big enough, however, a repeated sub-sequence itself would be very long so it would not seem repeated.Your
is 50.
^does not do what you expect. It's2 XOR 48instead of 2 to the power of 48. So useinstead. Then you will get
Why Not Exactly the Same with java.util.Random
In my experience, implementations almost always come with heuristics. Here is re-implementation of your code with those heuristics used by OpenJDK 15 to generate
nextInteger according to openjdk / jdk15. Especially according to lines from 198 to 206.You will see
lcg.nextRandom()andrandom.nextInt()generate the same integers if you compile the code using OpenJDK 15. While re-implementing, I found that an older OpenJDK uses different heuristics.