javalcg

Linear congruential generator gives wrong output


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.


Solution

  • LCG Requires a Big Modulus

    One of the key of Linear congruential generator is that m should 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

    long m = 2^48L;
    

    is 50. ^ does not do what you expect. It's 2 XOR 48 instead of 2 to the power of 48. So use

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

    instead. Then you will get

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

    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.

    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());
        }
    }
    
    

    You will see lcg.nextRandom() and random.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.