2

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.

4
  • 3
    the way you call constructor is different from the way it is defined ("a, c, m, seed" vs. "long seed, long a, long c, long m")
    – mangusta
    Commented Jan 27, 2021 at 14:53
  • 2^48 is suspicious. Why don't you just type 50?
    – user202729
    Commented Jan 27, 2021 at 15:24
  • Thanks, but after I matched the order I still get the wrong output. Now I get 44, 9, 14, 49, 44
    – Wilko
    Commented Jan 27, 2021 at 15:32
  • Please accept the answer or leave a comment for rejection.
    – ghchoi
    Commented Jan 29, 2021 at 1:54

1 Answer 1

3

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.

3
  • Thanks, this does indeed solve my problem. I have one follow up question though. I read somewhere that the numbers I use are the same as the java.util.Random class uses, but when I print them next to each other they differ. How is this possible? I have tried this with Random.nextInt() as well as Random.nextLong().
    – Wilko
    Commented Jan 27, 2021 at 18:39
  • @Wilko I made an edit. If you have hacker's mind, just hack it. Please check the edit and accept it. :)
    – ghchoi
    Commented Jan 28, 2021 at 1:37
  • @Wilko Thank you too buddy :)
    – ghchoi
    Commented Jan 30, 2021 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.