Multiplicera-med-bär pseudoslumptalsgenerator

Inom datavetenskap är multiplicera-med-bära (MWC) en metod som uppfanns av George Marsaglia för att generera sekvenser av slumpmässiga heltal baserat på en initial uppsättning från två till många tusen slumpmässigt valda frövärden. De främsta fördelarna med MWC-metoden är att den åberopar enkel datorheltalsaritmetik och leder till mycket snabb generering av sekvenser av slumptal med enorma perioder, från cirka 2 $\displaystyle 2^{60}}$ till $2^{2000000}$ .

Som med alla pseudoslumptalsgeneratorer är de resulterande sekvenserna funktioner av de angivna frövärdena.

Allmän teori

En MWC-generator är en speciell form av Lehmer-slumptalsgenerator $x_{n}=bx_{n-1}{\bmod {p}}$ som möjliggör effektiv implementering av en primtalsmodulen $p$ mycket större än maskinordsstorleken.

Normala Lehmer-generatorimplementationer väljer en modul nära maskinordstorleken. En MWC-generator bibehåller istället sitt tillstånd i bas $b$ , så att multiplicera med $b$ görs implicit genom att skifta ett ord. Basen $b$ är vanligtvis vald för att vara lika med datorns ordstorlek, eftersom detta gör aritmetik modulo $b$ trivial. Detta kan variera från $b=2^{8}$ för en mikrokontroller till $b=2^{64}$ . (Den här artikeln använder $b=2^{32}$ som exempel.)

Värdena för initialtillstånd ("frö") är godtyckliga, förutom att de inte får vara alla noll, inte heller alla vid de högsta tillåtna värdena ( $x_{0}=b-1$ och $c_{0}=a-1$ ). (Detta görs vanligtvis genom att välja $c_{0}$ mellan 1 och ${\displaystyle a-2} .$ ). MWC-sekvensen är då en sekvens av par $x_{n},c_{n}$ bestämd av

x_{n}=(ax_{n-1}+ c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\vänster\lgolv {\frac {ax_{n-1}+c_{n-1}}{b} }\höger\rgolv

Detta kallas en lag-1 MWC-sekvens. Ibland föredras en udda bas, i vilket fall $b=2^{k}-1$ kan användas, vilket är nästan lika enkelt att implementera. En lag- $r$ -sekvens är en generalisering av lag-1-sekvensen som tillåter längre perioder. Lag- $r$ MWC-sekvensen är då en sekvens av par $x_{n},c_{n}$ (för ${\displaystyle n>r} )$ bestäms av

x_{n}=(ax_{nr}+c_{ n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{nr}+c_{n-1}}{b}}\right\ rfloor

och MWC-generatorns utgång är sekvensen av $x$ ,

x_{r},x_{r+1},x_{r+2},...

I det här fallet får initialtillståndsvärdena ("seed") inte bara vara noll eller $x_{0}=b-1$ och $c_{ r-1}=a-1$ .

MWC-multiplikatorn $a$ och eftersläpning $r$ bestämmer modulen $p=ab^{r}-1$ . I praktiken väljs ${\displaystyle a} så att modulen är primtal och sekvensen har lång period.$ Om modulen är primtal, är perioden för en lag- $r$ MWC-generator i storleksordningen $b$ i den multiplikativa gruppen av tal modulo $p$ . Även om det är teoretiskt möjligt att välja en icke-primmodul, eliminerar en primemodul möjligheten att det initiala fröet delar en gemensam divisor med modulen, vilket skulle minska generatorns period.

Eftersom 2 är en kvadratisk rest av tal av formen $8k\pm 1$ , kan $b=2^{k}$ inte vara en primitiv rot av $p=ab^{r}-1$ . Därför har MWC-generatorer med bas $2^{k}$ sina parametrar valda så att deras period är ( ab ^r −1)/2. Detta är en av svårigheterna som användningen av b = 2 ^k − 1 övervinner.

Den grundläggande formen av en MWC-generator har parametrarna a , b och r , och r +1 tillståndsord. Tillståndet består av r rester modulo b

₀ 0 ≤ x , x ₁ , x ₂ ,..., x _{r −1} < b,

och a carry c _{r −1} < a .

Även om teorin för MWC-generatorer tillåter a > b , väljs a nästan alltid mindre för att underlätta implementeringen.

Tillståndstransformationsfunktionen för en MWC-generator är ett steg i Montgomery- reduktionsmodulo p . Tillståndet är ett stort heltal med det mest signifikanta ordet c _{n −1} och det minst signifikanta ordet x _{n − r} . Varje steg, x _{n − r} ·( ab ^r −1) läggs till detta heltal. Detta görs i två delar: −1· x _{n − r} läggs till x _{n − r} , vilket resulterar i ett minst signifikanta ord på noll. Och för det andra a · x _{n − r} till bäraren. Detta gör heltalet ett ord längre, vilket ger två nya mest signifikanta ord x _n och c _n .

Hittills har detta helt enkelt lagt till en multipel av p till tillståndet, vilket resulterar i en annan representant för samma restklass modulo p . Men till sist flyttas staten ned ett ord, dividerat med b . Detta förkastar det minst signifikanta ordet noll (som i praktiken aldrig beräknas alls) och multiplicerar effektivt tillståndet med b ⁻¹ (mod p ).

är en multiplicera-med-bär-generator en Lehmer-generator med modul p och multiplikator b ⁻¹ (mod p ). Detta är samma sak som en generator med multiplikator b , men som producerar utdata i omvänd ordning, vilket inte påverkar kvaliteten på de resulterande pseudoslumptalen.

Couture och L'Ecuyer har bevisat det överraskande resultatet att gittret som är associerat med en multiplicera-med-bär-generator är mycket nära det gitter som är associerat med Lehmer-generatorn som den simulerar. Således kan de matematiska tekniker som utvecklats för Lehmer-generatorer (såsom spektraltestet) tillämpas på multiplicera-med-bära-generatorer.

Effektivitet

En linjär kongruentialgenerator med bas b = 2 ³² implementeras som

x_{n+1}=(ax_{n}+c)\ {\bmod {\,}}2^{32},

där c är en konstant. Om a ≡ 1 (mod 4) och c är udda, kommer den resulterande bas-2 ³² kongruentialsekvensen att ha period 2 ³² .

Detta kan beräknas med endast de låga 32 bitarna av produkten av a och det aktuella x . Men många mikroprocessorer kan beräkna en fullständig 64-bitars produkt på nästan samma tid som de låga 32 bitarna. Faktum är att många beräknar 64-bitarsprodukten och ignorerar sedan den övre halvan.

En lag-1 multiplicera-med-bär-generator tillåter oss att göra perioden till nästan 2 ⁶³ genom att använda nästan samma datoroperationer, förutom att den övre halvan av 64-bitarsprodukten inte ignoreras efter att produkten har beräknats. Istället beräknas en 64-bitars summa och den övre halvan används som ett nytt bärvärde c snarare än den fasta additiva konstanten för standardkongruentialsekvensen: Beräkna ax + c i 64 bitar, använd sedan den övre halvan som den nya c , och nedre halvan som det nya x .

Val av multiplikator

Med multiplikator en specificerad, omvandlas varje par av ingångsvärden x , c till ett nytt par,

x\leftarrow (ax+c)\,{\bmod {\,}}2^{32},\ \ c\leftarrow \left\lfloor {\frac {ax+c}{2^{32} }}\höger\rgolv .

Om x och c inte båda är noll, kommer perioden för den resulterande multiplicera-med-bär-sekvensen att vara i storleksordningen b = 2 ³² i den multiplikativa gruppen av rester modulo ab ^r − 1 , det vill säga den minsta n så att b ⁿ ≡ 1 (mod ab ^r − 1).

Om p = ab ^r − 1 är primtal, så garanterar Fermats lilla teorem att ordningen för vilket element som helst måste dela p − 1 = ab ^r − 2, så ett sätt att säkerställa en stor ordning är att välja a så att p är en " säkert primtal ", det vill säga både p och ( p − 1)/2 = ab ^r /2 − 1 är primtal. I ett sådant fall, för b = 2 ³² och r = 1, kommer perioden att vara ab ^r /2 − 1, närmar sig 2 ⁶³ , vilket i praktiken kan vara en acceptabelt stor delmängd av antalet möjliga 32-bitarspar ( x , c ).

Närmare bestämt, i ett sådant fall delar ordningen för alla element p − 1, och det finns bara fyra möjliga divisorer: 1, 2, ab ^r /2 − 1 eller ab ^r − 2. De två första gäller endast för element 1 och −1, och kvadratiska ömsesidighetsargument visar att det fjärde alternativet inte kan tillämpas på b , så bara det tredje alternativet finns kvar.

Följande är några maximala värden för a för datorapplikationer som uppfyller ovanstående säkra primära villkor, för lag-1-generatorer:

Bitar i en	b	Maximalt a så att ab −1 är ett säkert primtal	Period
15	2 ¹⁶	2 ¹⁵ −50 = 32,718	1,072,103,423
16	2 ¹⁶	2 ¹⁶ −352 = 65,184	2,135,949,311
31	2 ³²	2 ³¹ −563 = 2 147 483 085	4,611,684,809,394,094,079
32	2 ³²	2 ³² −178 = 4,294,967,118	9,223,371,654,602,686,463
64	2 ⁶⁴	2 ⁶⁴ −742 = 18,446,744,073,709,550,874	2 ⁶³ (2 ⁶⁴ −742)−1 ≈ 1,701 × 10 ^ ³⁸
128	2 ¹²⁸	2 ¹²⁸ -10 408	2 ¹²⁷ (2 ¹²⁸ −10 408)−1 ≈ 5,790 × 10 ^ ⁷⁶
256	2 ²⁵⁶	2 ²⁵⁶ −9166	2 ²⁵⁵ (2 ²⁵⁶ −9166)−1 ≈ 6,704 × 10 ^ ¹⁵³
512	2 ⁵¹²	2 ⁵¹² -150 736	2 ⁵¹¹ (2 ⁵¹² −150 736)−1 ≈ 8,988 × 10 ^ ³⁰⁷

Medan ett säkert primtal säkerställer att nästan alla element i gruppen har en stor order, är perioden för generatorn specifikt storleksordningen b . För små moduler kan mer beräkningsmässigt dyra metoder användas för att hitta multiplikatorer a där perioden är ab /2 − 1. Följande är återigen maxvärden för a av olika storlekar.

Bitar i en	b ^r	Maximalt a så att b har ordningen ab ^r /2−1	Period
8	2 ⁸	2 ⁸ −7 = 249	31,871
8	(2 ⁸ ) ² = 2 ¹⁶	2 ⁸ −32 = 224	7,340,031
15	2 ¹⁶	2 ¹⁵ −29 = 32,739	1 072 791 551
16	2 ¹⁶	2 ¹⁶ −22 = 65 514	2,146,762,751
8	(2 ⁸ ) ⁴ = 2 ³²	2 ⁸ −64 = 192	412,316,860,415
15	(2 ¹⁶ ) ² = 2 ³²	2 ¹⁵ −26 = 32,742	70,312,909,602,815
16	(2 ¹⁶ ) ² = 2 ³²	2 ¹⁶ −2 = 65 534	140,733,193,388,031
31	2 ³²	2 ³¹ -68 = 2 147 483 580	4,611,685,872,398,499,839
32	2 ³²	2 ³² −76 = 4,294,967,220	9,223,371,873,646,018,559
8	(2 ⁸ ) ⁸ = 2 ⁶⁴	2 ⁸ −41 = 215	2 ⁶³ (2 ⁸ −41)−1 ≈ 1,983 × 10 ^ ²¹
15	(2 ¹⁶ ) ⁴ = 2 ⁶⁴	2 ¹⁵ −50 = 32,718	2 ⁶³ (2 ¹⁵ −50)−1 ≈ 3,018 × 10 ^ ²³
16	(2 ¹⁶ ) ⁴ = 2 ⁶⁴	2 ¹⁶ −56 = 65 480	2 ⁶³ (2 ¹⁶ −56)−1 ≈ 6,039 × 10 ^ ²³
31	(2 ³² ) ² = 2 ⁶⁴	2 ³¹ -38 = 2 147 483 610	2 ⁶³ (2 ³¹ −38)−1 ≈ 1,981 × 10 ^ ²⁸
32	(2 ³² ) ² = 2 ⁶⁴	2 ³² −43 = 4,294,967,253	2 ⁶³ (2 ³² −43)−1 ≈ 3,961 × 10 ^ ²⁸
63	2 ⁶⁴	2 ⁶³ −140 = 9 223 372 036 854 775 668	2 ⁶³ (2 ⁶³ −140)−1 ≈ 8,507 × 10 ^ ³⁷
64	2 ⁶⁴	2 ⁶⁴ −116 = 18 446 744 073 709 551 500	2 ⁶³ (2 ⁶⁴ −116)−1 ≈ 1,701 × 10 ^ ³⁸

MWC-generatorer som upprepade decimaler

Utsignalen från en multiplicera-med-bär-generator är ekvivalent med radix - b expansionen av en bråkdel med nämnaren p = ab ^r − 1. Här är ett exempel för det enkla fallet med b = 10 och r = 1, så resultatet är en återkommande decimal .

Börjar med ${\textstyle c_{0}=1,x_{0}=0}$ , MWC-sekvensen

x_{n}=(7x_{n-1} +c_{n-1})\,{\bmod {\,}}10,\ c_{n}=\vänster\lgolv {\frac {7x_{n-1}+c_{n-1}}{10 }}\höger\rgolv ,

producerar denna sekvens av tillstånd:

10,01,07,49,67,55,40,04,28,58,61,13,22,16,43,25,37,52,19,64,34,31, 10,01,07, ...

med period 22. Betrakta bara sekvensen av x _i :

0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4,1, 0,1,7, 9,7,5,0,...

Observera att om dessa upprepade segment av x -värden sätts i omvänd ordning :

1449275\cdots 9710\,1449275\cdots 9710\,144\cdots

vi får expansionen j /( ab −1) med a =7, b =10, j=10 :

{\frac {10}{69}}=0,1449275362318840579710\,14493275362}

Detta är sant i allmänhet: Sekvensen av x s som produceras av en fördröjnings MWC -generator:

x_{n}=(ax_{nr}+c_ {n-1}){\bmod {\,}}b\,,\ \ c_{n}=\vänster\lgolv {\frac {ax_{nr}+c_{n-1}}{b}}\ höger\rgolv ,

när den sätts i omvänd ordning, kommer det att vara radix- b expansionen av en bråkdel j /( ab ^r − 1) för ungefär 0 < j < ab ^r .

Ekvivalens till linjär kongruentialgenerator

Om vi fortsätter med exemplet ovan, om vi börjar med ${\textstil x_{0}=34}$ och genererar den vanliga kongruentialsekvensen

x_{n}=7x_{n-1}\,{\bmod {\,}}69

,

vi får period 22-sekvensen

31,10,1,7,49,67,55,40,4,28,58,61,13,22,16,43,25,37,52,19,64,34, 31,10,1, 7,...

och den sekvensen, reducerad mod 10, är

1,0,1,7,9,7,5,0,4,8,8,1,3,2,6,3,5,7,2,9,4,4, 1,0,1, 7,9,7,5,0,...

samma sekvens av x som resulterar från MWC-sekvensen.

Detta är sant i allmänhet (men tydligen bara för lag-1 MWC-sekvenser [ ^{citat behövs] )} :

Givet initialvärden $x_{0},c_{0}$ , sekvensen $x_{1},x_{2},\ldots$ som härrör från fördröjningen- 1 MWC-sekvens

x_{n}=(ax_{n-1}+ c_{n-1})\,{\bmod {b}}\,,\ \ c_{n}=\vänster\lgolv {\frac {ax_{n-1}+c_{n-1}}{b }}\höger\rgolv

är exakt Lehmer slumptalsgeneratorns utgångssekvens y _n = ay _{n − 1} mod ( ab − 1), reducerad modulo b .

₀ Att välja ett annat initialvärde y roterar bara cykeln av x .

Kompletterande-multiplicera-med-bär-generatorer

Att fastställa perioden för en lag- r MWC-generator innebär vanligtvis att man väljer multiplikator a så att p = ab ^r − 1 är primtal. Sedan måste p − 1 faktoriseras för att hitta ordningen för b mod p . Om p är ett säkert primtal är detta enkelt, och ordningen för b blir antingen p − 1 eller ( p − 1)/2. I andra fall p − 1 vara svårt att faktorisera.

Algoritmen tillåter emellertid också en negativ multiplikator. Detta leder till en liten modifiering av MWC-proceduren och ger en modul p = | − ab ^r − 1 | = ab ^r + 1. Detta gör p − 1 = ab ^r lätt att faktorisera, vilket gör det praktiskt att fastställa perioden för mycket stora generatorer.

Den modifierade proceduren kallas komplementär-multiplicera-med-bära (CMWC), och inställningen är densamma som för lag- r MWC: multiplikator a , bas b och r + 1 frön,

₀ x , x ₁ , x ₂_{−1 ,} ..., xr och c _{r −1} .

Modifieringen är till generering av ett nytt par ( x , c ). Om du arrangerar om beräkningen för att undvika negativa tal, kompletteras det nya x- värdet genom att subtrahera det från b − 1:

x_{n}=(b-1)-(ax_{nr}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor { \frac {ax_{nr}+c_{n-1}}{b}}\höger\rgolv .

Den resulterande sekvensen av x : n som produceras av CMWC RNG kommer att ha period i storleksordningen b i den multiplikativa gruppen av rester modulo ab ^r +1, och de utgående x : en, i omvänd ordning, kommer att bilda basen b expansionen av j /( ab ^r +1) för några 0 < j < ab ^r .

Användning av lag- r CMWC gör det mycket lättare att hitta perioder för r så stora som 512, 1024, 2048, etc. (Att göra r till en potens av 2 gör det något enklare att komma åt element i arrayen som innehåller den r senaste x s .)

En annan fördel med denna modifierade procedur är att perioden är en multipel av b , så utmatningen är exakt likafördelad mod b . (Den ordinarie MWC producerar under hela sin period varje möjlig utdata lika många gånger förutom att noll produceras en gång mindre, en bias som är försumbar om perioden är tillräckligt lång.)

En nackdel med CMWC-konstruktionen är att, med en tvåkraftsbas, är den maximalt uppnåbara perioden mindre än för en MWC-generator av liknande storlek; du förlorar flera bitar. Således är en MWC-generator vanligtvis att föredra för små fördröjningar. Detta kan åtgärdas genom att använda b = 2 ^k −1, eller välja en fördröjning ett ord längre för att kompensera.

Några exempel: Med b = 2 ³² och a = 109111 eller 108798 eller 108517, perioden för lag-1024 CMWC

x_{n}=(b-1)-(ax_{n-1024}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\ lgolv {\frac {ax_{n-1024}+c_{n-1}}{b}}\höger\rgolv .

kommer att vara en ·2 ³²⁷⁶² = ab ¹⁰²⁴ /64, cirka 10 ⁹⁸⁶⁷ .

Med b = 2 ³² och a = 3636507990 är p = ab ¹³⁵⁹ − 1 ett säkert primtal, så MWC-sekvensen baserad på det a har perioden 3636507990·2 ⁴³⁴⁸⁷ ≈ 10 ¹³¹⁰¹ .

Med b = 2 ³² kan en CMWC RNG med nära rekordperiod baseras på primtal p = 15455296 b ⁴²⁶⁵⁸ + 1. Ordningen på b för det primtal är 241489·2 ^1365056 ≈ 10 ⁴¹⁰⁹²⁸ .

Mer allmänna moduler

MWC-modulen för ab ^r −1 är vald för att göra beräkningen särskilt enkel, men för med sig vissa nackdelar, särskilt att perioden är högst halva modulen. Det finns flera sätt att generalisera detta, till priset av fler multiplikationer per iteration.

Först är det möjligt att lägga till ytterligare termer till produkten, vilket ger en modul av formen a _r b ^r + a _s b ^s −1. Detta kräver beräkning av c _n b + x _n = a _r x _{n − r} + a _s x _{n − s} . (Bären är begränsad till ett ord om a _r + a _s ≤ b .)

₀₀₀₀ Detta löser dock inte periodproblemet, som beror på modulens låga bitar. Lyckligtvis tillåter Montgomery-reduktionsalgoritmen andra moduler, så länge de är relativt prime till basen b , och detta kan tillämpas för att tillåta en modul av formen a _r b ^r − a , för ett brett spektrum av värden a . Goresky och Klapper utvecklade teorin om dessa generaliserade multiplicera-med-bär-generatorer, och bevisade särskilt att om man väljer ett negativt a och a _r – a < b är bärvärdet alltid mindre än b , vilket gör implementeringen effektiv. Den mer allmänna formen av modulen förbättrar också kvaliteten på generatorn, även om man inte alltid kan få full period.

För att implementera en Goresky-Klapper-generator förberäknar man a ^-1
₀ (mod b ), och ändrar iterationen enligt följande:

t=c_{n-1}+\sum _{1}^{r}a_{i}x_{ni},\ x_{n}=a_{0}^{-1}t{\bmod {b}},\ c_{n}=\left\lfloor {\frac {t-a_{0}x_{n}}{b}}\right\rfloor .

I det vanliga fallet att b = 2 ^{k måste} a vara udda för att inversen ska existera . ₀

Genomförande

Följande är en implementering av CMWC-algoritmen i programmeringsspråket C. Dessutom ingår i programmet ett exempel på initieringsfunktion. I denna implementering är basen 2 ³² −1 och eftersläpning r =4096. Perioden för den resulterande generatorn är cirka $2^{131104}$ .


 
 
 
 

















  
	 
	 	
	 



 

	   
              
              
	 



      

	        
	    0    
		  
	
		  
	   
	    



     

	    	
	    	
	 
	 

	        
	      
	
	    
	    
	    
		
		
	
	     


 

	  
	    

	 
	 
 // C99 Komplementär multiplicera med bärgenerator  #include  <stdint.h>  #include  <stdio.h>  #include  <stdlib.h>  #include  <time.h>  // Hur många bitar i rand()?  // https://stackoverflow.com/a/27593398  #define LOG_1(n) (((n) >= 2) ? 1 : 0)  #define LOG_2(n) (((n) >= 1<<2 ) ? (2 + LOG_1((n)>>2)) : LOG_1(n))  #define LOG_4(n) (((n) >= 1<<4) ? (4 + LOG_2((n)>> 4)) : LOG_2(n))  #define LOG_8(n) (((n) >= 1<<8) ? (8 + LOG_4((n)>>8)) : LOG_4(n)) #define  LOG (n) (((n) >= 1<<16) ? (16 + LOG_8((n)>>16)) : LOG_8(n)) #define BITS_TO_REPRESENT(n) (LOG(n) + !!  ( (n) & ((n) - 1)))  #if ((RAND_MAX | (RAND_MAX >> 1)) != RAND_MAX)  #error "förväntade ett RAND_MAX som är 2^n - 1!"  #endif  #define RAND_BITS BITS_TO_REPRESENT(RAND_MAX)  //  CMWC  -  arbetsdelar  #define CMWC_CYCLE 4096  // som Marsaglia rekommenderar  #define CMWC_C_MAX 809430660  //  som Marsaglia rekommenderar  struct  Q  uint32_W_Ct  ;  uint32_t  c  ;  // måste begränsas med CMWC_C_MAX  osignerad  i  ;  };  // Samla 32 bitar av rand(). Du uppmuntras att använda en bättre källa istället.   uint32_t  rand32  (  void  )  {  uint32_t  resultat  =  rand  ();  för  (  int  bits  =  RAND_BITS  ;  bitar  <  32  ;  bitar  +=  RAND_BITS  )  resultat  =  resultat  <<  RAND_BITS  |  rand  ();  returnera  resultat  ;  }  // Initiera tillståndet med seed  void  initCMWC  (  struct  cmwc_state  *  state  ,  unsigned  int  seed  )  {  srand  (  seed  );  för  (  int  i  =  ;  i  <  CMWC_CYCLE  ;  i  ++  )  tillstånd  ->  Q  [  i  ]  =  rand32  ();  gör  state  ->  c  =  rand32  ();  while  (  tillstånd  ->  c  >=  CMWC_C_MAX  );  state  ->  i  =  CMWC_CYCLE  -  1  ;  }  // CMWC-motor  uint32_t  randCMWC  (  struct  cmwc_state  *  state  )  //EDITED parameter * state saknades  {  uint64_t  const  a  =  18782  ;  // som Marsaglia rekommenderar  uint32_t  const  m  =  0xfffffffe  ;  // som Marsaglia rekommenderar  uint64_t  t  ;  uint32_t  x  ;  tillstånd  ->  i  =  (  tillstånd  ->  i  +  1  )  &  (  CMWC_CYCLE  -  1  );  t  =  a  *  tillstånd  ->  Q  [  tillstånd  ->  i  ]  +  tillstånd  ->  c  ;  /* Låt c = t / 0xffffffff, x = t mod 0xffffffff */  state  ->  c  =  t  >>  32  ;  x  =  t  +  tillstånd  ->  c  ;  if  (  x  <  tillstånd  ->  c  )  {  x  ++  ;  tillstånd  ->  c  ++  ;  }  returnera  tillstånd  ->  Q  [  tillstånd  ->  i  ]  =  m  -  x  ;  }  int  main  ()  {  struct  cmwc_state  cmwc  ;  unsigned  int  seed  =  tid  (  NULL  );  initCMWC  (  &  cmwc  ,  frö  );  printf  (  "Slumpmässig CMWC: %u  \n  "  ,  randCMWC  (  &  cmwc  ));  }

Följande är implementeringar av småtillstånd MWC-generatorer med 64-bitars utgång med 128-bitars multiplikationer.






    



   
            
        
       
 // C99 + __uint128_t MWC, 128 bitar av tillstånd, period ca. 2^127   /* Tillståndet får varken vara noll, eller x = 2^64 - 1, c = MWC_A1 -  1. Villkoret 0 < c < MWC_A1 - 1 är alltså tillräckligt. */   uint64_t  x  ,  c  =  1  ;  #define MWC_A1 0xff3a275c007b8ee6  uint64_t  inline  next  ()  {  const  __uint128_t  t  =  MWC_A1  *  (  __uint128_t  )  x  +  c  ;  c  =  t  >>  64  ;  returnera  x  =  t  ;  }






      



   
            
      
      
        
       
 // C99 + __uint128_t MWC, 256 bitar av tillstånd, period ca. 2^255   /* Tillståndet får varken vara noll, eller x = y = z = 2^64 - 1, c =  MWC_A3 - 1. Villkoret 0 < c < MWC_A3 - 1 är alltså tillräckligt. */   uint64_t  x  ,  y  ,  z  ,  c  =  1  ;  #define MWC_A3 0xff377e26f82da74a  uint64_t  inline  next  ()  {  const  __uint128_t  t  =  MWC_A3  *  (  __uint128_t  )  x  +  c  ;  x  =  y  ;  y  =  z  ;  c  =  t  >>  64  ;  returnera  z  =  t  ;  }

Följande är implementeringar av småtillstånd Goresky-Klappers generaliserade MWC-generatorer med 64-bitars utdata med 128-bitars multiplikationer.







   0   





   
            
        
            
     
 // C99 + __uint128_t Goresky-Klapper GMWC, 128 bitar av tillstånd, period ca. 2^127   /* Tillståndet får varken vara noll eller x = 2^64 - 1, c = GMWC_A1 +  GMWC_MINUS_A0. Villkoret 0 < c < GMWC_A1 + GMWC_MINUS_A0 är således   tillräckligt. */   uint64_t  x  =  ,  c  =  1  ;  #define GMWC_MINUSA0 0x7d084a4d80885f  #define  GMWC_A0INV 0x9b1eea3792a42c61 #define   GMWC_A1  0xff002aae7d81a646  uint64_t  inline  _GM_1  (  A  __t  inline  _  __t  )  __uint128_t  )  x  +  c  ;  x  =  GMWC_A0INV  *  (  uint64_t  )  t  ;  c  =  (  t  +  GMWC_MINUSA0  *  (  __uint128_t  )  x  )  >>  64  ;  returnera  x  ;  }







       





   
            
      
      
        
            
     
 // C99 + __uint128_t Goresky-Klapper GMWC, 256 bitar av tillstånd, period ca. 2^255   /* Tillståndet får varken vara noll, eller x = y = z = 2^64 - 1, c =  GMWC_A3 + GMWC_MINUS_A0. Villkoret 0 < c < GMWC_A3 + GMWC_MINUS_A0   är således tillräckligt. */   uint64_t  x  ,  y  ,  z  ,  c  =  1  ;  /* Tillståndet kan seedas med vilken uppsättning värden som helst, inte alla nollor. */   #define  GMWC_MINUSA0  0x54c3da46afb70f  #define  GMWC_A0INV  0xbbf397e9a69da811  #define  GMWC_A3  0xff963a86efd088a2  uint64_t  inline  nästa  (  )  _A_GM  int128_t  )  x  +  c  ;  x  =  y  ;  y  =  z  ;  z  =  GMWC_A0INV  *  (  uint64_t  )  t  ;  c  =  (  t  +  GMWC_MINUSA0  *  (  __uint128_t  )  z  )  >>  64  ;  returnera  z  ;  }

Användande

På grund av enkelheten och hastigheten är CMWC känt för att användas i spelutveckling, särskilt i moderna roguelike -spel. Det är informellt känt som Mother of All PRNGs, ett namn som ursprungligen myntades av Marsaglia själv. I libtcod ersatte CMWC4096 MT19937 som standard PRNG.

Se även

Marsaglia, George (4 juli 2003). "Xorshift RNGs" . Journal of Statistical Software . 8 (14): 1–6. doi : 10.18637/jss.v008.i14 .
Marsaglia, George (oktober 2005). "Om slumpmässigheten hos Pi och andra decimalexpansioner" . Interstat . CiteSeerX 10.1.1.694.4783 .
Press, William H. ; Teukolsky, Saul A. ; Vetterling, William T.; Flannery, Brian P. (2007). "Avsnitt 7.1.2.B Multiplicera med bär (MWC)" . Numeriska recept: The Art of Scientific Computing (3:e upplagan). New York: Cambridge University Press. ISBN 978-0-521-88068-8 .