Page 1 of 1

Einfacher Pseudo-Random-Generator

Posted: Tue Mar 29, 2011 11:20 am
by Octopus
Hier stelle ich meinen einfachen Zufallszahlen-Generator vor (C++),
dessen BalancedKey Funktion erzeugt die Zobrist Basis Vektoren.

Code: Select all

// (C) 2011 R.Scharnagl, 80992 München, Deutschland 

#include <ctime> 
#include <climits> 

#pragma hdrstop 

#include "Tool.h" 

// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// --- SPEICHER --- 

// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// zuletzt erzeugten Zufallszahl, lokal 
U32 Tool::seed = 0; 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// --- METHODEN (RANDOM) --- 

// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// setzt positive Startzahl für Generator 
U32 Tool::SetSeed(U32 newSeed) 
{ 
  // den Seed neu festlegen 
  seed = newSeed; 

  // technisch geswapped ausgeben 
  return (newSeed << 16) ^ (newSeed >> 16); 
} 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// setzt (Zeit-) zufällige Generator-Startzahl 
U32 Tool::Randomize(void) 
{ 
  using namespace std; 

  // Zeitpuffer 
  time_t thisMoment; 

  // ermittle eine Startzahl aus der Systemzeit 
  time(&thisMoment); 

  return SetSeed(MAGIC * (U32)thisMoment); 
} 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// holt <unsigned> Zufallszahl 
U32 Tool::Random(void) 
{ 
  // neue interne Zufallszahl merken 
  return SetSeed(seed * 87641 + 98731); 
} 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// holt <unsigned> Zufallszahl aus [0, Limit) 
U32 Tool::RangedRandom(U32 limit) 
{ 
  // Ergebnis und anzupassende Obergrenze 
  U32 answer, limValid; 

  // bestimme ersten ungültigen Treffer, 
  // um Ungleichverteilung zu unterbinden 
  limValid = UINT_MAX - UINT_MAX % limit; 

  // iterative gleichverteilte Erzeugung 
  for (;;) { 
    // solange neue Kandidaten testen 
    answer = Random(); 
    // bis Gleichverteilung sichergestellt 
    if (answer < limValid) 
      return answer % limit; 
  } 
} 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

// liefert positive Zufallszahl, die als Binärzahl 
// genau 50% Einsen hat (für XOR Overlay) 
U32 Tool::BalancedKey(void) 
{ 
  int bitDifference; 
  U32 answer; 

  // selektiere ideale Hash-Kandidaten 
  do { 
    // Prüfinstrumente 
    U32 oneBit = (U32)INT_MIN; 
    bitDifference = 0; 

    // bilde Zufallszahlen 
    answer = Random(); 

    // bis Gleichverteilung vorliegt 
    do { 
      if (answer & oneBit) { 
        ++bitDifference; 
      } else { 
        --bitDifference; 
      } 
    } while ((oneBit >>= 1) != 0L); 

  } while (bitDifference != 0); 

  return answer; 
} 
// - - - - - - - - - - - - - - - - - - - - - - - - - - - 

Re: Einfacher Pseudo-Random-Generator

Posted: Wed Mar 30, 2011 5:32 pm
by Octopus
Nun mit einer kleinen Verbesserung für die "echte" Randomisierung:

Code: Select all

// (C) 2011 R.Scharnagl, 80992 München, Deutschland
// --- 30.Apr.2011: Funktion Randomize() verbessert  

#include <ctime>
#include <climits>

#pragma hdrstop

#include "Tool.h"

// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// --- SPEICHER ---

// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// zuletzt erzeugte Roh-Zufallszahl, lokal
U32 Tool::seed = 0;
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// --- METHODEN (RANDOM) ---

// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// setzt positive Startzahl für Generator
U32 Tool::SetSeed(U32 newSeed)
{
  // den Seed neu festlegen
  seed = newSeed;

  // technisch geswapped ausgeben
  return (newSeed << 16) ^ (newSeed >> 16);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// setzt (Zeit-) zufällige Generator-Startzahl
U32 Tool::Randomize(void)
{
  using namespace std;

  // Zeitpuffer
  time_t thisMoment;

  // ermittle eine Startzahl aus der Systemzeit
  time(&thisMoment);

  // abhängig von Zeit und altem Seed-Zustand
  return SetSeed(Random() ^ (U32)thisMoment);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// holt <unsigned> Zufallszahl
U32 Tool::Random(void)
{
  // neue interne Zufallszahl merken
  return SetSeed(seed * 87641 + 98731);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// holt <unsigned> Zufallszahl aus [0, Limit)
U32 Tool::RangedRandom(U32 limit)
{
  // Ergebnis und anzupassende Obergrenze
  U32 answer, limValid;

  // bestimme ersten ungültigen Treffer,
  // um Ungleichverteilung zu unterbinden
  limValid = UINT_MAX - UINT_MAX % limit;

  // iterative gleichverteilte Erzeugung
  for (;;) {
    // solange neue Kandidaten testen
    answer = Random();
    // bis Gleichverteilung sichergestellt
    if (answer < limValid)
      return answer % limit;
  }
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// liefert positive Zufallszahl, die als Binärzahl
// genau 50% Einsen hat (für XOR Overlay)
U32 Tool::BalancedKey(void)
{
  int bitDifference;
  U32 answer;

  // selektiere ideale Hash-Kandidaten
  do {
    // Prüfinstrumente
    U32 oneBit = (U32)INT_MIN;
    bitDifference = 0;

    // bilde Zufallszahlen
    answer = Random();

    // bis Gleichverteilung vorliegt
    do {
      if (answer & oneBit) {
        ++bitDifference;
      } else {
        --bitDifference;
      }
    } while ((oneBit >>= 1) != 0L);

  } while (bitDifference != 0);

  return answer;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -