RANDU

Tredimensionell plot med 100 000 värden genererade med RANDU. Varje punkt representerar 3 på varandra följande pseudoslumpvärden. Det är tydligt att punkterna faller i 15 tvådimensionella plan .

RANDU är en linjär kongruentiell pseudoslumptalsgenerator (LCG) av typen Park-Miller, som användes främst på 1960- och 1970-talen. Det definieras av återkommande :

$V_{j+1}=65539\cdot V_{j}\,{\bmod {\,}}2^{31}\,$

med det initiala startnumret, $V_{0}$ som ett udda tal . Den genererar pseudoslumpmässiga heltal $V_{j}$ som är likformigt fördelade i intervallet [1, 2 ³¹ − 1] , men i praktiska tillämpningar mappas ofta till pseudoslumpmässiga rationaler $X_{j}$ i intervallet (0, 1) , med formeln:

$X_{j}={\frac {V_{j}}{2^{31}}}$ .

IBM:s RANDU anses allmänt vara en av de mest ogenomtänkta slumptalsgeneratorerna som någonsin designats, och beskrevs som "verkligen hemsk" av Donald Knuth . Den klarar spektraltestet dåligt för dimensioner större än 2 som kommer att ses nedan.

$) {\displaystyle ( {\text{ie, }}2^{16}+3)}$ bitars heltalsordstorlek, aritmetiken för mod 2 ³¹ och $65539$ beräkningar kunde göras snabbt med hjälp av bitvisa operatorer i hårdvara, men värdena valdes för beräkningsbekvämlighet, inte statistisk kvalitet.

Problem med multiplikator och modul

För alla linjära kongruentialgeneratorer med modul m som används för att generera punkter i n -dimensionellt rymd, faller punkterna inte in mer än $(n!\times m)^{1/n}$ parallella hyperplan. Detta indikerar att LCG:er med låg modul är olämpliga för högdimensionell Monte Carlo-simulering . För m = 2^31 och n = 3 kan en LCG ha upp till 2344 plan, teoretiskt maximum. En mycket snävare övre gräns bevisas i samma Marsaglia-tidning vara summan av de absoluta värdena för alla koefficienter för hyperplanen i standardform. Det vill säga, om hyperplanen har formen Ax1 + Bx2 + Cx3 = något heltal som 0, 1, 2 etc, då är det maximala antalet plan |A|+|B|+|C|.

Nu undersöker vi värdena för multiplikator 65539 och modul 2 ³¹ som valts för RANDU. Betrakta följande beräkning där varje term ska tas mod 2 ³¹ . Börja med att skriva den rekursiva relationen som:

$x_{k+2}=(2^{16}+3)x_{k+1} =(2^{16}+3)^{2}x_{k}\,$

vilket blir, efter att ha utökat den kvadratiska faktorn:

${\displaystyle x_{k+2}=(2^{32}+ 6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}\,} eftersom$

2 32 ^mod 2 ³¹ = 0

och låter oss visa korrelationen mellan tre punkter som:

$x_{k+2}=6x_{k+1}-9x_{k}\,$

Genom att summera koefficienternas absoluta värden får vi inte mer än 16 plan i 3D, vilket blir bara 15 plan vid närmare granskning som visas i diagrammet ovan. Även med LCGs standarder visar detta att RANDU är fruktansvärt: att använda RANDU för att sampla en enhetskub kommer bara att sampla 15 parallella plan, inte ens nära den övre gränsen på 2344 plan.

Som ett resultat av den omfattande användningen av RANDU i början av 1970-talet ses många resultat från den tiden som misstänkta. Detta felaktiga beteende upptäcktes redan 1963 på en 36-bitars dator och omimplementerades omsorgsfullt [ på 32-bitars IBM System/360 . Den troddes ha rensats i stor utsträckning i början av 1990-talet men det fanns fortfarande FORTRAN-kompilatorer som använde den så sent som 1999.

Provutgång

Starten av RANDU:s utgångsperiod för det initiala fröet $V_{0}=1$ är:

1, 65539, 393225, 1769499, 7077969, 26542323, … (sekvens A096555 i OEIS )