Le générateur linéaire de congruences donne un résultat erroné

Question

J'ai créé un générateur congruentiel linéaire (LCG), mais il semble me donner un résultat erroné.

// 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;
}

Le résultat que j'obtiens est le suivant :

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

J'ai utilisé les valeurs a, c et m parce que j'ai lu que la classe java.util.Random utilise également ces valeurs. Mais l'utilisation de cette classe avec la même graine donne des réponses différentes. J'ai également vérifié avec d'autres calculateurs lcg et mes réponses ne correspondent pas non plus. Je n'ai aucune idée de ce qui s'est passé.

Answer 1

La LCG nécessite un gros module

L'une des clés de la Générateur congruentiel linéaire est que m devrait suffire. Ou bien, vous trouverez rapidement des sous-séquences répétées car l'opération modulo génère toujours des sous-séquences répétées pour toutes les progressions arithmétiques. Toutefois, si elle est suffisamment grande, une sous-séquence répétée sera elle-même très longue et ne semblera donc pas répétée.

Votre

long m = 2^48L;

est de 50. ^ ne fait pas ce que vous attendez. Il est 2 XOR 48 au lieu de 2 à la puissance 48. Utilisez donc

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

au lieu de cela. Vous obtiendrez alors

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

Pourquoi ne pas faire exactement la même chose avec java.util.Random ?

D'après mon expérience, les mises en œuvre sont presque toujours accompagnées d'une heuristique. Voici une réimplémentation de votre code avec les heuristiques utilisées par OpenJDK 15 pour générer nextInt eger selon la openjdk / jdk15 . En particulier selon lignes de 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());
    }
}

Vous verrez lcg.nextRandom() y random.nextInt() génèrent les mêmes nombres entiers si vous compilez le code en utilisant OpenJDK 15. Lors de la réimplémentation, j'ai découvert qu'un ancien OpenJDK utilise une heuristique différente.