Tananyag‎ > ‎Kódolás‎ > ‎

Lineáris Kongruencia Generátor (LCG)

Az LCG algoritmus egy sorozatot ad meg, melyet bizonyos szempontból randomnak tekinthetünk.

  • Egzaktul kiszámítható, ezért ha fontos a megjósolhatatlanság (pl. rejtjelezésnél), nem használható
  • Viszont szimulációkhoz, játékokhoz nagyszerűen megfelel az egyszerűsége miatt.
Az algoritmusnak 4 paramétere van, a, c, m és x0, ezek közül a-t, c-t, m-et kell jól választani úgy, hogy a sorozat periódusa elérje a maximális értékét (ami m).
A 0. elem paraméter: x0, ezután minden xn-et az előző tagból számítunk a következő képlet segítségével:
xn ≡ a·xn-1+c (mod m)

(Olvasd: xn kongruens a·xn-1+c modulo m. Jelentése: a bal és a jobb oldal azonos maradékot ad m-mel osztva. Gyakorlatilag xn számításához képezzük a jobb oldal m-mel vett maradékát).

Tipikus paraméterhármas kinézhető ebből a táblázatból.

Egy lehetséges paraméterhármas: m=1l<<32, a=1664525, c=1013904223

public class LCG {
    
    private int x, a, c, m;

    public LCG(int x, int a, int c, int m) {
        this.x = x;
        this.a = a;
        this.c = c;
        this.m = m;
    }
    
    public int nextRandom() {
        x = (int)(((long)a * x + c) % m);
        return x;
    }
    
    
}