KISS (Zufallszahlengenerator)

KISS i​st ein Zufallszahlengenerator, d​er von George Marsaglia entwickelt wurde.[1]

Sein Name rührt v​om KISS-Prinzip her, d​er Generator i​st eine Kombination a​us drei einfachen Zufallszahlengeneratoren:

Jeder dieser Generatoren für s​ich alleine besteht praktisch k​eine Tests a​uf Zufälligkeit. Die Kombination i​n Form d​es KISS-Generators besteht jedoch a​lle statistischen Tests a​us dem BigCrush-Test d​er TestU01-Bibliothek.[2]

Eigenschaften
  • Periodenlänge:
    • größer als 2124 ≈ 2,12 · 1037 (32-Bit-Version)
    • größer als 2247 ≈ 2,26 · 1074 (64-Bit-Version)[3]
  • kleiner Zustandsvektor: 4 Werte zu je 32 bzw. 64 Bit
  • benutzt nur einfache Rechenoperationen: Shift, Addition, Multiplikation
  • einfache Implementierung

Implementierung in C
32 Bit64 Bit
#include <stdint.h>

// interner Zustand
static uint32_t x = 123456789; // seed beliebig,
static uint32_t y = 362436000; // aber y != 0 und
static uint32_t z = 521288629; // z,c nicht beide 0
static uint32_t c = 7654321;

uint32_t KISS() {
   uint64_t t;

   // Linearer Kongruenzgenerator
   x = 69069 * x + 12345;

   // Xorshift
   y ^= y << 13;
   y ^= y >> 17;
   y ^= y << 5;

   // Multiply-with-carry
   t = (uint64_t)698769069 * z + c;
   c = t >> 32;
   z = (uint32_t) t;

   return x + y + z;
}

#include <stdint.h>

// interner Zustand
static uint64_t x = 1066149217761810ULL;
static uint64_t y = 362436362436362436ULL;
static uint64_t z = 1234567890987654321ULL;
static uint64_t c = 123456123456123456ULL;

uint64_t KISS64() {
   uint64_t t;

   // Linearer Kongruenzgenerator
   x = 6906969069ULL * x + 1234567;

   // Xorshift
   y ^= y << 13;
   y ^= y >> 17;
   y ^= y << 43;

   // Multiply-with-carry
   t = (z << 58) + c;
   c = z >> 6;
   z += t;
   c += z < t;

   return x + y + z;
}

Siehe auch

Einzelnachweise
  1. Journal Of Modern Applied Statistical Methods, May, 2003, Vol. 2 (PDF; 9,5 MB)
  2. Pierre L’Ecuyer, Richard Simard: TestU01: A C library for empirical testing of random number generators. In: ACM Transactions on Mathematical Software, Volume 33, Issue 4, August 2007
  3. https://www.thecodingforums.com/threads/64-bit-kiss-rngs.673657/
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.