Linjär kongruensgenerator

Från Rilpedia

Texten från svenska Wikipedia

En linjär kongruensgenerator (LKG) är en typ av pseudoslumptalsgenerator, en algoritm som producerar en sekvens till synes slumpmässiga tal. Linjära kongruensgeneratorer hör till de enklaste slumptalsgeneratorerna, både matematiskt och implementationsmässigt, och är dessutom mycket snabba. Dessvärre uppvisar de brister som gör dem olämpliga för många användningsområden.

En linjär kongruensgenerator definieras av en differensekvation på formen

där S_n representerar generatorns interna tillstånd såväl som sekvensen av utmatade slumptal, och A, B samt M är heltalskonstanter som måste väljas noggrant. Numerical Recipes rekommenderar exempelvis

A = 1664525, B = 1013904223, M = 2³².

Den främsta anledningen att använda en linjär kongruensgenerator är att minnesåtgången närmast är obefintlig och att beräkningarna kan utföras snabbt. Framför allt är linjära kongruensgeneratorer effektiva då M sätts till en tvåpotens, eftersom modulo-operationen då kan utföras kostnadsfritt på de flesta datorer. En linjär kongruensgenerator kan ofta vara ett lämpligt val i inbyggda system med små minnen eller i datorspel där slumptalen måste produceras snabbt och kvaliteten oftast inte är viktig.

Brister

Då slumptalen från en linjär kongruensgenerator exempelvis används för att välja punkter i tre dimensioner faller de bara längs vissa plan.

Oberoende av hur konstanterna väljs har linjära kongruensgeneratorer flera brister som bland annat gör dem olämpliga för Monte Carlo-simuleringar och kryptografi:

• Perioden kan högst vara M, och är ofta kortare. För längsta möjliga period krävs att

1. B och M är relativt prima
2. A-1 är delbart med alla M:s primtalsfaktorer
3. A-1 är en multipel av 4 och M är en multipel av 4
4. M är större än A, B och begynnelsevärdet S₀
5. A och B är positiva

• Värdena är starkt seriellt korrelerade, vilket gör att om en linjär kongruensgenerator exempelvis används för att välja slumpmässiga koordinater i ett n-dimensionell rum så faller punkterna som mest längs M^1/n olika hyperplan. Spektraltestet för slumptalsgeneratorer utformades med den här defekten i åtanke.

• Ytterligare ett problem är att de minst signifikanta bitarna får en betydligt kortare period än sekvensen som helhet om M är en tvåpotens. Om M = m^k gäller mer generellt att den n:te minst signifikanta siffran i S uttryckt i basen m har en period på högst mⁿ. Med anledning av detta är bara de mest signifikanta bitarna i S användbara.