Lineær kongruensiell generator - Linear congruential generator

To modulo-9 LCG viser hvordan forskjellige parametere fører til forskjellige sykluslengder. Hver rad viser tilstanden som utvikler seg til den gjentas. Den øverste raden viser en generator med m = 9, a = 2, c = 0, og et frø på 1, som produserer en syklus med lengde 6. Den andre raden er den samme generatoren med et frø på 3, som produserer en syklus av lengde 2. Ved å bruke a = 4 og c = 1 (nederste rad) gir du en sykluslengde på 9 med et hvilket som helst frø i [0, 8].

En lineær kongruensiell generator ( LCG ) er en algoritme som gir en sekvens av pseudo-randomiserte tall beregnet med en diskontinuerlig stykkevis lineær ligning . Metoden representerer en av de eldste og mest kjente pseudotilfelle tallgeneratoralgoritmene . Teorien bak dem er relativt lett å forstå, og de er enkle å implementere og raske, spesielt på maskinvare som kan gi modulær aritmetikk ved lagringsbit-trunkering.

Generatoren er definert av gjentakelsesrelasjon :

{\ displaystyle X_ {n+1} = \ venstre (aX_ {n}+c \ høyre) {\ bmod {m}}}

hvor er sekvensen av pseudosluttverdier, og ${\ displaystyle X}$

{\ displaystyle m, \, 0 <m}

- " modulen "

{\ displaystyle a, \, 0 <a <m}

- "multiplikatoren"

{\ displaystyle c, \, 0 \ leq c <m}

- "økningen"

{\ displaystyle X_ {0}, \, 0 \ leq X_ {0} <m}

- "frø" eller "startverdi"

er heltallskonstanter som spesifiserer generatoren. Hvis c = 0, kalles generatoren ofte en multiplikativ kongruensiell generator (MCG), eller Lehmer RNG . Hvis c ≠ 0, kalles metoden en blandet kongruensiell generator .

Når c ≠ 0, ville en matematiker kalle gjentakelsen en affin transformasjon , ikke en lineær , men feilbetegnelsen er veletablert innen datavitenskap.

Historie

Lehmer -generatoren ble utgitt i 1951 og den lineære kongruensielle generatoren ble utgitt i 1958 av WE Thomson og A. Rotenberg.

Periode lengde

En fordel med LCG er at med passende valg av parametere er perioden kjent og lang. Selv om det ikke er det eneste kriteriet, er for kort periode en dødelig feil i en pseudoslått tallgenerator.

Selv om LCG -er er i stand til å produsere pseudoslåtte tall som kan bestå formelle tester for tilfeldighet , er kvaliteten på utgangen ekstremt følsom for valget av parameterne m og a . For eksempel, en = 1 og c = 1, gir en enkel modulo- m teller, som har en lang periode, men er tydeligvis ikke-tilfeldig.

Historisk sett har dårlige valg for a ført til ineffektive implementeringer av LCG. Et spesielt illustrerende eksempel på dette er RANDU , som ble mye brukt tidlig på 1970 -tallet og førte til mange resultater som for tiden stilles spørsmålstegn ved bruk av denne dårlige LCG.

Det er tre vanlige familier med parametervalg:

m prime, c = 0

Dette er den originale Lehmer RNG -konstruksjonen. Perioden er m −1 hvis multiplikatoren a er valgt til å være et primitivt element i heltallene modulo m . Starttilstanden må velges mellom 1 og m −1.

En ulempe med en primmodul er at den modulære reduksjonen krever et produkt med dobbel bredde og et eksplisitt reduksjonstrinn. Ofte brukes en prime bare mindre enn en effekt på 2 ( Mersenne -primtallene 2 ³¹ −1 og 2 ⁶¹ −1 er populære), slik at reduksjonsmodulen m = 2 ^e - d kan beregnes som ( ax mod 2 ^e ) + d ⌊ ax /2 ^e ⌋ . Dette må følges av en betinget subtraksjon på m hvis resultatet er for stort, men antall subtraksjoner er begrenset til ad / m , som lett kan begrenses til en hvis d er liten.

Hvis et produkt med dobbel bredde ikke er tilgjengelig, og multiplikatoren er valgt nøye, kan Schrages metode brukes. For å gjøre dette, faktor m = qa + r , dvs. q = ⌊ m / a ⌋ og r = m mod a . Beregn deretter ax mod m = a ( x mod q ) - r ⌊ x / q ⌋ . Siden x mod q < q ≤ m / a , er det første uttrykket strengt mindre enn am / a = m . Hvis a er valgt slik at r ≤ q (og dermed r / q ≤ 1), er det andre uttrykket også mindre enn m : r ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x < m . Dermed kan begge produktene beregnes med et enkeltbreddeprodukt, og forskjellen mellom dem ligger i området [1− m , m −1], så det kan reduseres til [0, m −1] med et enkelt betinget tillegg .

En annen ulempe er at det er vanskelig å konvertere verdien 1 ≤ x < m til uniforme tilfeldige biter. Hvis en prime bare mindre enn en effekt på 2 brukes, blir noen ganger de manglende verdiene ganske enkelt ignorert.

m en effekt på 2, c = 0

Å velge m til å være en effekt på 2 , oftest m = 2 ³² eller m = 2 ⁶⁴ , gir en spesielt effektiv LCG, fordi dette gjør at moduloperasjonen kan beregnes ved ganske enkelt å avkorte den binære representasjonen. Faktisk er de mest signifikante bitene vanligvis ikke beregnet i det hele tatt. Det er imidlertid ulemper.

Dette skjemaet har maksimal periode m /4, oppnådd hvis a ≡ 3 eller a ≡ 5 (mod 8). Starttilstanden X ₀ må være merkelig, og de lave tre bitene av X veksler mellom to tilstander og er ikke nyttige. Det kan vises at denne formen tilsvarer en generator med en modul en fjerdedel av størrelsen og c ≠ 0.

Et mer alvorlig problem med bruk av en power-of-two-modul er at de lave bitene har en kortere periode enn de høye bitene. Den laveste ordensbiten av X endres aldri ( X er alltid merkelig), og de to neste bitene veksler mellom to tilstander. (Hvis a ≡ 5 (mod 8), endres bit 1 aldri og bit 2 veksler. Hvis a ≡ 3 (mod 8), endres bit 2 aldri og bit 1 veksler.) Bit 3 gjentas med en periode på 4, bit 4 har en periode på 8, og så videre. Bare den mest betydningsfulle biten av X oppnår hele perioden.

c ≠ 0

Når c ≠ 0, tillater riktig valgte parametere en periode lik m for alle frøverdier. Dette vil skje hvis og bare hvis :

${\ displaystyle m}$ og er relativt førsteklasses , ${\ displaystyle c}$
${\ displaystyle a-1}$ er delelig med alle hovedfaktorer for , ${\ displaystyle m}$
${\ displaystyle a-1}$ er delelig med 4 hvis er delelig med 4. ${\ displaystyle m}$

Disse tre kravene omtales som Hull - Dobell -setningen.

Denne formen kan brukes med alle m , men fungerer bare godt for m med mange gjentatte primfaktorer, for eksempel en effekt på 2; bruk av en datamaskins ordstørrelse er det vanligste valget. Hvis m var en kvadratisk fritt heltall , vil dette bare tillate en ≡ 1 (mod m ), noe som gir en svært dårlig PRNG; et utvalg av mulige multiplikatorer for hele perioden er bare tilgjengelig når m har gjentatte primfaktorer.

Selv om Hull - Dobell -setningen gir maksimal periode, er det ikke tilstrekkelig å garantere en god generator. For eksempel er det ønskelig at a - 1 ikke er mer delelig med primfaktorer på m enn nødvendig. Så hvis m er en effekt på 2, bør a - 1 være delelig med 4, men ikke delelig med 8, dvs. a ≡ 5 (mod 8).

Faktisk produserer de fleste multiplikatorer en sekvens som mislykkes i en test for ikke-tilfeldighet eller en annen, og det er ganske utfordrende å finne en multiplikator som er tilfredsstillende for alle gjeldende kriterier. Den spektrale test er en av de viktigste tester.

Legg merke til at en power-of-2 modul deler problemet som beskrevet ovenfor for c = 0: de lave k bitene danner en generator med modul 2 ^k og gjentar dermed med en periode på 2 ^k ; bare den mest betydningsfulle biten oppnår hele perioden. Hvis et pseudosluttall mindre enn r er ønsket, er ⌊ rX / m result et resultat av mye høyere kvalitet enn X mod r . Dessverre gjør de fleste programmeringsspråk sistnevnte mye lettere å skrive ( X % r), så det er den mer vanlige formen.

Generatoren er ikke følsom for valget av c , så lenge den er relativt prim til modulen (f.eks. Hvis m er en effekt på 2, må c være ulik), så verdien c = 1 blir vanligvis valgt.

Serien produsert av andre valg av c kan skrives som en enkel funksjon av serien når c = 1. Spesielt hvis Y er den prototypiske serien definert av Y ₀ = 0 og Y _{n +1} = aY _n +1 mod m, kan en generell serie X _{n +1} = aX _n + c mod m skrives som en affin funksjon av Y :

{\ displaystyle X_ {n} = (X_ {0} (a-1)+c) Y_ {n}+X_ {0} = (X_ {1} -X_ {0}) Y_ {n}+X_ {0 } {\ pmod {m}}.}

Mer generelt er alle to serier X og Z med samme multiplikator og modul relatert til

{\ displaystyle {X_ {n} -X_ {0} \ over X_ {1} -X_ {0}} = Y_ {n} = {a^{n} -1 \ over a-1} = {Z_ {n } -Z_ {0} \ over Z_ {1} -Z_ {0}} {\ pmod {m}}.}

Parametre i vanlig bruk

Tabellen nedenfor viser parameterne for LCG-er som er i vanlig bruk, inkludert innebygde rand () -funksjoner i kjøretidsbiblioteker til forskjellige kompilatorer . Denne tabellen skal vise popularitet, ikke eksempler å etterligne; mange av disse parameterne er dårlige. Tabeller med gode parametere er tilgjengelige.

Kilde	modul m	multiplikator a	økning c	sende ut frøbiter i rand () eller Random (L)
ZX81	2 ¹⁶ + 1	75	74
Numeriske oppskrifter	2 ³²	1664525	1013904223
Borland C/C ++	2 ³²	22695477	1	bits 30..16 i rand () , 30..0 i lrand ()
glibc (brukt av GCC )	2 ³¹	1103515245	12345	biter 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C ++ C90 , C99 , C11 : Forslag i ISO/IEC 9899, C18	2 ³¹	1103515245	12345	biter 30..16
Borland Delphi , Virtual Pascal	2 ³²	134775813	1	bits 63..32 av (seed × L)
Turbo Pascal	2 ³²	134775813 (8088405 ₁₆ )	1
Microsoft Visual/Quick C/C ++	2 ³²	214013 (343FD ₁₆ )	2531011 (269EC3 ₁₆ )	biter 30..16
Microsoft Visual Basic (6 og tidligere)	$224$	1140671485 (43FD43FD ₁₆ )	12820163 (C39EC3 ₁₆ )
RtlUniform fra Native API	2 ³¹ - 1	2147483629 (7FFFFFED ₁₆ )	2147483587 (7FFFFFC3 ₁₆ )
Apple CarbonLib , C ++ 11 's`minstd_rand0`	2 ³¹ - 1	16807	0	se MINSTD
C ++ 11 -tallet`minstd_rand`	2 ³¹ - 1	48271	0	se MINSTD
MMIX av Donald Knuth	2 ⁶⁴	6364136223846793005	1442695040888963407
Newlib , Musl	2 ⁶⁴	6364136223846793005	1	bits 63..32
VMS ' MTH $ RANDOM , gamle versjoner av glibc	2 ³²	69069 (10DCD ₁₆ )	1
Java 's java.util.Random, POSIX [ln] rand48, glibc [ln] rand48 [_r]	2 ⁴⁸	25214903917 (5DEECE66D ₁₆ )	11	biter 47..16
`random0`	134456 = 2 ³ 7 ⁵	8121	28411	${\ displaystyle {\ frac {X_ {n}} {134456}}}$
POSIX [jm] rand48, glibc [mj] rand48 [_r]	2 ⁴⁸	25214903917 (5DEECE66D ₁₆ )	11	biter 47..15
POSIX [de] rand48, glibc [de] rand48 [_r]	2 ⁴⁸	25214903917 (5DEECE66D ₁₆ )	11	biter 47..0
cc65	2 ²³	65793 (10101 ₁₆ )	4282663 (415927 ₁₆ )	biter 22..8
cc65	2 ³²	16843009 (1010101 ₁₆ )	826366247 (31415927 ₁₆ )	biter 31..16
Tidligere vanlig: RANDU	2 ³¹	65539	0

Som vist ovenfor bruker ikke LCGer alltid alle bitene i verdiene de produserer. For eksempel opererer Java- implementeringen med 48-biters verdier ved hver iterasjon, men returnerer bare sine 32 viktigste biter. Dette er fordi bitene av høyere orden har lengre perioder enn de av lavere orden (se nedenfor). LCGer som bruker denne trunkeringsteknikken produserer statistisk bedre verdier enn de som ikke gjør det. Dette er spesielt merkbart i skript som bruker mod -operasjonen for å redusere rekkevidde; endring av tilfeldig tall mod 2 vil føre til vekslende 0 og 1 uten avkortning.

Fordeler og ulemper

SKG er hurtig og krever minimalt med hukommelse (en modulo- m antall, ofte 32 eller 64 biter) for å holde tilstand. Dette gjør dem verdifulle for å simulere flere uavhengige strømmer. LCG er ikke beregnet, og må ikke brukes, for kryptografiske applikasjoner; bruk en kryptografisk sikker pseudoslått tallgenerator for slike applikasjoner.

Hyperplan av en lineær kongruensiell generator i tre dimensjoner. Denne strukturen er det den spektrale testen måler.

Selv om LCG har noen spesifikke svakheter, kommer mange av deres mangler ved å ha en for liten tilstand. Det faktum at folk har blitt lulled i så mange år til å bruke dem med så små moduler, kan sees på som et bevis på teknikkens styrke. En LCG med stor nok tilstand kan bestå selv strenge statistiske tester; en modulo-2 LCG som returnerer de høye 32 bitene passerer TestU01s SmallCrush-pakke, og en 96-biters LCG passerer den strengeste BigCrush-pakken.

For et spesifikt eksempel forventes en ideell tilfeldig tallgenerator med 32 bits utgang (etter fødselsdagssetningen ) å begynne å kopiere tidligere utganger etter √ m ≈ 2 ¹⁶ resultater. Enhver PRNG hvis utgang er dens fulle, uavkortede tilstand, vil ikke produsere duplikater før hele perioden er utløpt, en lett påviselig statistisk feil. Av relaterte årsaker bør enhver PRNG ha en lengre periode enn kvadratet av antall utganger som kreves. Gitt moderne datahastigheter betyr dette en periode på 2 ⁶⁴ for alle unntatt de minst krevende applikasjonene, og lengre for krevende simuleringer.

En feil spesifikk for LCG er at hvis de brukes til å velge punkter i et n-dimensjonalt rom, vil punktene maksimalt ligge på ⁿ √ n ! ⋅ m hyperplaner ( Marsaglias teorem , utviklet av George Marsaglia ). Dette skyldes seriell korrelasjon mellom påfølgende verdier av sekvensen X _n . Uforsiktig valgte multiplikatorer vil vanligvis ha langt færre fly med store mellomrom, noe som kan føre til problemer. Den spektrale testen , som er en enkel test av en LCG kvalitet, måler denne avstand og gir en god multiplikator for å bli valgt.

Flyavstanden avhenger både av modulen og multiplikatoren. En stor nok modul kan redusere denne avstanden under oppløsningen til doble presisjonsnummer. Valget av multiplikatoren blir mindre viktig når modulen er stor. Det er fortsatt nødvendig å beregne spektralindeksen og sørge for at multiplikatoren ikke er en dårlig, men rent sannsynlig blir det ekstremt usannsynlig å støte på en dårlig multiplikator når modulen er større enn ca 2 ⁶⁴ .

En annen feil som er spesifikk for LCG-er, er den korte perioden for biter med lav orden når m er valgt til å være en effekt på 2. Dette kan dempes ved å bruke en modul som er større enn den nødvendige utgangen, og ved å bruke de mest signifikante bitene i staten.

Likevel kan LCG -er for noen applikasjoner være et godt alternativ. For eksempel, i et innebygd system, er mengden tilgjengelig minne ofte sterkt begrenset. På samme måte kan det i et miljø som en videospillkonsoll ta et lite antall høyordensbiter av en LCG godt være tilstrekkelig. (Lavordensbitene til LCG-er når m er en effekt på 2 bør aldri stole på for noen tilfeldighet.) Lavordensbitene går gjennom svært korte sykluser. Spesielt vil en full-syklus LCG, når m er en effekt på 2, gi vekselvis merkelige og jevne resultater.

LCG-er bør evalueres veldig nøye for egnethet i ikke-kryptografiske applikasjoner der høy kvalitet på tilfeldighet er kritisk. For Monte Carlo -simuleringer må en LCG bruke en modul som er større og fortrinnsvis mye større enn terningen til antall tilfeldige prøver som kreves. Dette betyr for eksempel at en (god) 32-biters LCG kan brukes til å oppnå omtrent tusen tilfeldige tall; en 64-bit LCG er bra for ca 2 ²¹ stikkprøver (litt over to millioner), etc. Av denne grunn, i praksis SKG er ikke egnet for storskala Monte Carlo simuleringer.

Eksempelkode

Python -kode

Følgende er en implementering av en LCG i Python , i form av en generator :

from typing import Generator

def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]:
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed

Gratis Pascal

Gratis Pascal bruker en Mersenne Twister som standard pseudo tilfeldig tallgenerator mens Delphi bruker en LCG. Her er et Delphi -kompatibelt eksempel i Free Pascal basert på informasjonen i tabellen ovenfor. Gitt den samme RandSeed -verdien, genererer den samme sekvens av tilfeldige tall som Delphi.

unit lcg_random;
{$ifdef fpc}{$mode delphi}{$endif}
interface

function LCGRandom: extended; overload; inline;
function LCGRandom(const range:longint): longint; overload; inline;

implementation
function IM: cardinal; inline;
begin
  RandSeed := RandSeed * 134775813 + 1;
  Result := RandSeed;
end;

function LCGRandom: extended; overload; inline;
begin
  Result := IM * 2.32830643653870e-10;
end;

function LCGRandom(const range: longint): longint; overload; inline;
begin
  Result := IM * range shr 32;
end;

Som alle pseudotilfelle tallgeneratorer, må en LCG lagre tilstand og endre den hver gang den genererer et nytt nummer. Flere tråder kan få tilgang til denne tilstanden samtidig og forårsake en løpstilstand. Implementeringer bør bruke forskjellige tilstander hver med unik initialisering for forskjellige tråder for å unngå like sekvenser av tilfeldige tall på tråder som utføres samtidig.

LCG -derivater

Det er flere generatorer som er lineære kongruensielle generatorer i en annen form, og dermed kan teknikkene som brukes til å analysere LCG, brukes på dem.

En metode for å produsere en lengre periode er å summere resultatene fra flere LCG -er fra forskjellige perioder som har et stort minst felles multiplum ; den Wichmann-Hill generator er et eksempel på denne form. (Vi foretrekker at de er helt coprime , men en primmodul innebærer en jevn periode, så det må være en felles faktor på 2, i det minste.) Dette kan vises til å være ekvivalent med en enkelt LCG med en modul lik produktet av komponenten LCG moduli.

Marsaglias add-with-carry og subtract-with- loan PRNGs med en ordstørrelse på b = 2 ^w og lag r og s ( r > s ) tilsvarer LCGs med en modul på b ^r ± b ^s ± 1.

Multiply-with-carry PRNGs med en multiplikator på a tilsvarer LCGs med en stor primmodul på ab ^r -1 og en power-of-2 multiplikator b .

En permutert kongruensiell generator begynner med en effekt-av-2-modul LCG og bruker en utgangstransformasjon for å eliminere problemet med kort periode i lavordensbiter.

Sammenligning med andre PRNG -er

Den andre mye brukte primitive for å oppnå langvarige pseudo-tilfeldige sekvenser er den lineære tilbakemeldingsskiftregisterkonstruksjonen , som er basert på aritmetikk i GF (2) [ x ], polynomringen over GF (2) . I stedet for å heltall addisjon og multiplikasjon, de grunnleggende operasjoner er eksklusiv-eller , og bære-mindre multiplikasjon , som vanligvis er utført som en sekvens av logiske skift . Disse har fordelen av at alle bitene deres er fullperiode; de lider ikke av svakheten i lavordensbitene som plager aritmetisk modulo 2 ^k .

Eksempler på denne familien inkluderer xorshift -generatorer og Mersenne -twister . Sistnevnte gir en veldig lang periode (2 ¹⁹⁹³⁷ −1) og variabel ensartethet, men den mislykkes i noen statistiske tester. Forsinkede Fibonacci -generatorer faller også inn i denne kategorien; Selv om de bruker aritmetisk tillegg, er perioden sikret med en LFSR blant de minst signifikante bitene.

Det er lett å oppdage strukturen til et lineært tilbakemeldingsskiftregister med passende tester, for eksempel den lineære kompleksitetstesten implementert i TestU01 -pakken ; en boolsk sirkulasjonsmatrise som er initialisert fra påfølgende biter av en LFSR, vil aldri ha rang større enn polynomgraden . Å legge til en ikke-lineær utgangsblandingsfunksjon (som i xoshiro256 ** og permuterte kongruensielle generatorkonstruksjoner ) kan forbedre ytelsen på statistiske tester sterkt.

En annen struktur for en PRNG er en veldig enkel gjentagelsesfunksjon kombinert med en kraftig utgangsblandingsfunksjon. Dette omfatter tellermodus blokk-kodenøkler og ikke-kryptografiske generatorer som SplitMix64 .

En struktur som ligner på LCG, men ikke ekvivalent, er den multiple-rekursive generatoren: X _n = ( a ₁X _{n −1} + a ₂X _{n −2} + ··· + a _k X _{n - k} ) mod m for k ≥ 2. Med en primmodul kan dette generere perioder opp til m ^k −1, så det er en nyttig forlengelse av LCG -strukturen til større perioder.

En kraftig teknikk for å generere pseudosluttall av høy kvalitet er å kombinere to eller flere PRNGer med forskjellig struktur; summen av en LFSR og en LCG (som i KISS eller xorwow konstruksjoner) kan gjøre det svært bra på noen kostnader i fart.

Se også

Liste over tilfeldige tallgeneratorer - andre PRNG -er, inkludert noen med bedre statistiske kvaliteter
ACORN generator - ikke å forveksle med ACG, hvilket uttrykk ser ut til å ha blitt brukt for varianter av LCG og LFSR generatorer
Tillatt kongruensiell generator
Full syklus
Inversiv kongruensiell generator
Multipliser-med-bære
Lehmer RNG (noen ganger kalt Park - Miller RNG)
Kombinert lineær kongruensiell generator

Merknader

Referanser

Trykk, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 7.1.1. Some History" , Numerical Recipes: The Art of Scientific Computing (3. utg.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods , 2. utgave, Springer, ISBN 0-387-00178-6 .
Joan Boyar (1989). "Slutte sekvenser produsert av pseudo-tilfeldige tallgeneratorer" (PDF) . Journal of the ACM . 36 (1): 129–141. doi : 10.1145/58562.59305 . S2CID 3565772 . (i denne artikkelen er effektive algoritmer gitt for å slutte sekvenser produsert av visse pseudo-tilfeldige tallgeneratorer).

Eksterne linker

Simuleringen Linear Congruential Generator visualiserer korrelasjonene mellom de pseudo-tilfeldige tallene når parametrene manipuleres.
Sikkerhet ved tilfeldig tallgenerering: En kommentert bibliografi
Linear Congruential Generators post til sci.math
Datamaskinprosjektet "Death of Art" ved Goldstein Technologies LLC, bruker en LCG til å generere 33 554 432 bilder
P. L'Ecuyer og R. Simard, "TestU01: AC Library for Empirical Testing of Random Number Generators" , mai 2006, revidert november 2006, ACM Transactions on Mathematical Software , 33, 4, artikkel 22, august 2007.
Artikkel om en annen måte å knekke LCG

Languages

In other projects