Permutowany generator kongruencji

Permutowany generator kongruencji ( PCG ) to algorytm generowania liczb pseudolosowych opracowany w 2014 roku przez dr ME O'Neilla , który stosuje funkcję permutacji wyjściowej w celu poprawy właściwości statystycznych liniowego generatora kongruencji modulo-2 n . Osiąga doskonałą wydajność statystyczną przy małym i szybkim kodzie oraz małym rozmiarze stanu.

PCG różni się od klasycznego liniowego generatora kongruencji (LCG) na trzy sposoby:

  • moduł i stan LCG jest większy, zwykle dwukrotnie większy od pożądanego wyjścia,
  • wykorzystuje moduł mocy 2 , co skutkuje szczególnie wydajną implementacją z generatorem pełnookresowym i nieobciążonymi bitami wyjściowymi, oraz
  • stan nie jest wyprowadzany bezpośrednio, ale raczej najbardziej znaczące bity stanu są używane do wybierania obrotu bitowego lub przesunięcia, które jest stosowane do stanu w celu wytworzenia wyjścia.

To zmienna rotacja eliminuje problem krótkiego okresu w bitach niskiego rzędu, na który cierpi LCG o mocy 2.

Warianty

Rodzina PCG obejmuje szereg wariantów. Rdzeń LCG jest zdefiniowany dla szerokości od 8 do 128 bitów, chociaż do praktycznego użytku zalecane są tylko 64 i 128 bitów; mniejsze rozmiary służą do testów statystycznych techniki.

Stałą addytywną w LCG można zmieniać, aby uzyskać różne strumienie. Stała jest dowolną nieparzystą liczbą całkowitą, więc nie musi być jawnie przechowywana; adresu samej zmiennej stanu (z ustawionym niskim bitem) .

Zdefiniowano kilka różnych transformacji wyjściowych. Wszystkie działają dobrze, ale niektóre mają większy margines niż inne. Zbudowane są z następujących elementów:

  • RR: Losowa (zależna od danych wejściowych) rotacja, z wyjściem o połowę mniejszym niż wejście. Biorąc pod uwagę 2 bitowe słowo wejściowe, górne b -1 bity są używane do wielkości obrotu, następne najbardziej znaczące 2 b -1 bity są obracane w prawo i używane jako dane wyjściowe, a dolne 2 b -1 + 1− b bitów jest odrzucanych.
  • RS: Przesunięcie losowe (zależne od danych wejściowych) w przypadkach, gdy rotacje są droższe. Ponownie, dane wyjściowe są o połowę mniejsze niż dane wejściowe. Zaczynając od 2- bitowego słowa 2-3-1 wejściowego , górne b -3 bity są używane do przesunięcia, które jest stosowane do następnego najbardziej znaczącego 2- bitowego bitu - 1 + bitów i najmniej znaczącego Wyprowadzane jest 2 b −1 bitów wyniku. Niskie bity 2 b −1 −2 b −3 − b +4 są odrzucane.
  • XSH: Operacja xorshift , x ^= x >> stała . Stała jest wybierana tak, aby była połową bitów, które nie zostaną odrzucone przez następną operację (zaokrąglona w dół).
  • XSL: Uproszczona wersja xorshift, składająca wartość na pół przez XORowanie wysokiej połowy do najniższej. Złożona wartość jest używana do kolejnych obrotów.
  • RXS: Xorshift o losową (zależną od danych wejściowych) kwotę.
  • M: Mnożenie przez ustaloną stałą.

Są one łączone w następujące zalecane przekształcenia wyjściowe, zilustrowane tutaj w ich najczęstszych rozmiarach:

  • XSH-RR: Xorshift miksuje niektóre bity wyższego rzędu, a następnie bity 63–59 wybierają wielkość obrotu, która ma zostać zastosowana do bitów 27–58.
    (64→32 bity) liczba = (int)(x >> 59); x ^= x >> 18; return rotr32((uint32_t)(x >> 27), liczba); .
  • XSH-RS: Podobne, ale mniej bitów wybiera wielkość przesunięcia.
    (64→32 bity) liczba = (int)(x >> 61); x ^= x >> 22; return (uint32_t)(x >> (29 - liczba)); .
  • XSL-RR: Uproszczona wersja XSH-RR, zoptymalizowana pod kątem stanów 128-bitowych zaimplementowanych przy użyciu dwóch słów na maszynach 64-bitowych.
    (128→64 bity) liczba = (int)(x >> 122); x64 = (uint64_t)(x ^ (x >> 64)); return rotr64(x64, liczba);
  • RXS-M-XS: Najwolniejsza i najsilniejsza transformacja wyjściowa, gdy jest używana do generowania wyjścia o połowę, staje się najsłabsza, gdy jest używana zgodnie z przeznaczeniem, do generowania wyjścia o takim samym rozmiarze jak stan. Do użycia, gdy rozmiar stanu musi być ograniczony do 32 lub 64 bitów.
    (32→32 bity) liczba=(int)(x >> 28); x ^= x >> (4 + liczba); x *= 277803737u; powrót x ^ (x >> 22);
    (64→64 bity) liczba=(int)(x >> 59); x ^= x >> (5 + liczba); x *= 12605985483714917081u; powrót x ^ (x >> 43);
  • XSL-RR-RR: Podobnie jak poprzednio, zamienia 128 bitów stanu na 128 bitów danych wyjściowych, gdy aplikacja tego wymaga.
    (128→128 bitów) liczba = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), liczba); wysoki64 = rotr64((uint64_t)(x >> 64), niski64 i 63); powrót (uint128_t)high64 << 64 | niski64;

Każdy krok tych transformacji wyjściowych jest albo odwracalny (a więc jeden do jednego ) albo obcięty, więc ich skład odwzorowuje tę samą stałą liczbę stanów wejściowych na każdą wartość wyjściową. Zachowuje to równomierną dystrybucję bazowego LCG.

Wreszcie, jeśli wymagana jest długość cyklu większa niż 2 128 , generator można rozszerzyć o szereg podgeneratorów. Jeden jest wybierany (w rotacji) do dodania do wyjścia głównego generatora, a za każdym razem, gdy stan głównego generatora osiąga zero, podgeneratory są przełączane zgodnie ze wzorem, który zapewnia okres wykładniczy w całkowitym rozmiarze stanu.

Przykładowy kod

Generatorem zalecanym dla większości użytkowników jest PCG-XSH-RR z 64-bitowym stanem i 32-bitowym wyjściem. Może być zaimplementowany jako:

 
               		
     
      	

     
 #include  <stdint.h>  static  stan  uint64_t  =  0x4d595df4d0f33173  ;  // Lub coś zależnego od nasion  static  uint64_t  const  mnożnik  =  6364136223846793005u  ;  static  uint64_t  const  increment  =  1442695040888963407u  ;  // Lub dowolna stała nieparzysta  static  uint32_t  rotr32  (  uint32_t  x  ,  unsigned  r  )  { 
	         


 

	   
	     		

	      
	 zwróć  x  >>  r  |  x  <<  (  -  r  &  31  );  }  uint32_t  pcg32  (  nieważne  )  {  uint64_t  x  =  stan  ;  liczba  bez znaku  =  (  bez znaku  )(  x  >>  59  );  // 59 = 64 - 5  stan  =  x  *  mnożnik  +  przyrost  ;  X     								
	    	


  

	    
	
 ^=  x  >>  18  ;  // 18 = (64 - 27)/2  return  rotr32  ((  uint32_t  )(  x  >>  27  ),  count  );  // 27 = 32 - 5  }  void  pcg32_init  (  uint64_t  materiał siewny  )  {  stan  =  materiał siewny  +  przyrost  ;  (  nieważne  )  pcg32  ();  }

Generator stosuje transformację wyjściową do stanu początkowego , a nie końcowego , aby zwiększyć dostępną równoległość na poziomie instrukcji i zmaksymalizować wydajność nowoczesnych procesorów superskalarnych .

Nieco szybsza wersja eliminuje przyrost, redukując LCG do generatora multiplikatywnego ( w stylu Lehmera ) z okresem tylko 2 62 i wykorzystuje słabszą funkcję wyjściową XSH-RS: 

    	
     

 

	   
	     	

	    static  uint64_t  mcg_state  =  0xcafef00dd15ea5e5u  ;  // Musi być nieparzysta  static  uint64_t  const  mnożnik  =  6364136223846793005u  ;  uint32_t  pcg32_fast  (  nieważne  )  {  uint64_t  x  =  mcg_state  ;  liczba  bez znaku  =  (  bez znaku  )(  x  >>  61  );  // 61 = 64 - 3  stan_mcg  =  x  *  
	    
	     	


  

	    
	
 mnożnik  ;  x  ^=  x  >>  22  ;  return  (  uint32_t  )(  x  >>  (  22  +  liczba  ));  // 22 = 32 - 3 - 7  }  void  pcg32_fast_init  (  uint64_t  materiał siewny  )  {  stan_mcg  =  2  *  materiał siewny  +  1  ;  (  nieważne  )  pcg32_fast  ();  }

Oszczędność czasu jest minimalna, ponieważ pozostaje najdroższa operacja (mnożenie 64 × 64-bitowe), więc normalna wersja jest preferowana, z wyjątkiem sytuacji ekstremalnych . Mimo to ta szybsza wersja przechodzi również testy statystyczne.

Podczas wykonywania na procesorze 32-bitowym mnożenie 64 × 64-bitowe należy zaimplementować przy użyciu trzech operacji mnożenia 32 × 32 → 64-bitowego. Aby zredukować to do dwóch, istnieją mnożniki 32-bitowe, które działają prawie tak dobrze jak mnożniki 64-bitowe, takie jak 0xf13283ad, 0xffffffff0e703b65 lub 0xf2fc5985.

Porównanie z innymi generatorami liczb pseudolosowych

Melissa O'Neill proponuje przetestowanie PRNG poprzez zastosowanie testów statystycznych do ich wariantów o zmniejszonym rozmiarze i określenie minimalnej liczby bitów stanu wewnętrznego wymaganych do przejścia. TestU01's BigCrush bada wystarczającą ilość danych, aby wykryć okres 2 35 , więc nawet idealny generator wymaga 36 bitów stanu, aby go przejść. Niektóre bardzo słabe generatory mogą przejść, jeśli otrzymają wystarczająco duży stan; przejście pomimo małego stanu jest miarą jakości algorytmu i pokazuje, jak duży margines bezpieczeństwa istnieje między tą dolną granicą a rozmiarem stanu używanym w praktycznych zastosowaniach.

PCG-RXS-M-XS (z wyjściem 32-bitowym) przechodzi BigCrush z 36 bitami stanu (minimum możliwe), PCG-XSH-RR ( pcg32() powyżej) wymaga 39, a PCG-XSH-RS ( pcg32_fast() powyżej) wymaga 49 bitów stanu. Dla porównania, xorshift* , jedna z najlepszych alternatyw, wymaga 40 bitów stanu, a Mersenne twister zawodzi pomimo 19937 bitów stanu.

Przewidywanie i odzyskiwanie nasion

Wykazano, że jest praktycznie możliwe (przy dużych obliczeniach) odzyskanie ziarna generatora pseudolosowego przy danych 512 kolejnych bajtach wyjściowych. Oznacza to, że praktycznie możliwe jest przewidzenie reszty strumienia pseudolosowego, biorąc pod uwagę 512 bajtów.

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Permuted_congruential_generator&oldid=1136326070 ”