Author: Reinhard Scharnagl
Date: 14:55:14 10/28/03
Go up one level in this thread
Hi, because 64-bit random numbers mostly will be split into an address-part and a key part, I do not see a need for 64-Bit numbers but concatenate two 32-Bit numbers, using only special generated numbers with an equal bit distribution (because of a better quasi hamming-distance). If you are not interested in a (german language commented) C++ source, you may stop reading here. Regards, Reinhard. A) HEADER-FILE //========================================================== // PROJEKT: Tool.lib //---------------------------------------------------------- // MODUL : CRandom (als SINGLETON gekapselt) // ZWECK : allgemein nützliche statische Zufalls-Funktionen // AUTOREN: RS, Reinhard Scharnagl, München //---------------------------------------------------------- // DETAILS: Diese Klasse umfasst die wichtigsten und ge- // bräuchlichsten Funktionen eines Pseudo-Zufalls- // zahlen-Generators. Konkret handelt es sich hier // um einen binär kongruenten Generator. //---------------------------------------------------------- // CHRONIK: RS, 08-Okt-2003, überarbeitetes Modul begonnen //========================================================== // --- technische Rekursionssperre (Start) --- #ifndef X_RandomH #define X_RandomH //=========================== // Klasse CRandom (Singleton) //=========================== class CRandom { private: // --- geschützte Typen und Informationen --- // Konstanten und Aufzählungen enum ERandom { // die Hälfte möglicher Bits in einem <unsigned> eHASH_BITS = 16, // größte positive Primzahl in einem <unsigned> eMODUL = 0xFFFFFFFB, // ein gut geeigneter Kongruenz-Prim-Faktor eFAKTOR = 0x3FB, // der zu eFAKTOR gehörige Hilfs-Quotient eQUOT = (unsigned)eMODUL / eFAKTOR, // der zu eFAKTOR gehörige Hilfs-Rest eREST = (unsigned)eMODUL % eFAKTOR }; private: // --- geschützte statische Eigenschaften --- // die zuletzt erzeugte interne Zufallszahl static unsigned Seed; public: // --- öffentliche statische Eigenschaften --- // das einzige (konstante) Singleton-Objekt static const CRandom TheRandomBox; private: // --- geschützte Methoden --- // Konstruktoren und Destruktoren CRandom() {}; // wg. Singleton private ~CRandom() {}; // wg. Singleton private public: // --- öffentliche statische Methoden --- // setzt (Zeit-) zufällige Startzahl für Generator static unsigned Randomize(void); // setzt positive <int> Startzahl für Generator static unsigned SetSeed(unsigned _uNewSeed); // holt <unsigned> Zufallszahl aus (0, eMODUL) static unsigned GetRandom(void); // holt <unsigned> Zufallszahl aus [0, uLimit) static unsigned GetRandom(unsigned _uLimit); // holt Fließkommazahl aus [0.0, rLimit) static double GetRandom(double _rLimit); // holt <int> Zufallszahl aus [0, iLimit) inline static int GetRandom(int _iLimit) { return (int)GetRandom( (unsigned)((_iLimit > 0) ? _iLimit : 0)); }; // ermittelt Anzahl gesetzter Bits in <unsigned> Zahl static int CountBits(unsigned _iHash); // liefert positive Spezial-Zufallszahlen für Hashing static int GetHash(void); }; // --- technische Rekursionssperre (Ende) --- #endif B) IMPLEMENTATION-FILE //========================================================== // PROJEKT: Tool.lib // MODUL : CRandom (SINGLETON) // DETAILS: --> Header-Datei //========================================================== // --- technische Optimierung --- #pragma hdrstop // --- System-Includes --- #include <time.h> #include <limits.h> // --- Projekt-Includes --- #include "Random.h" // --- technische Optimierung (Borland) --- #ifdef __BCPLUSPLUS__ #pragma package(smart_init) #endif //=========================== // Klasse CRandom (Singleton) //=========================== // --- statische Klassenvariablen --- /* die zuletzt erzeugte interne Zufallszahl */ unsigned CRandom::Seed = 0; // --- öffentliche statische Eigenschaften --- // das einzige (konstante) Singleton-Objekt const CRandom CRandom::TheRandomBox; // --- öffentliche statische Methoden --- // setzt Startzahl aus (0, eMODUL) für Generator unsigned CRandom::SetSeed(unsigned _uNewSeed) { // auf den Bereich (0, eMODUL) bringen while (!_uNewSeed || _uNewSeed >= (unsigned)eMODUL) { _uNewSeed -= (unsigned)eMODUL; } // und übergreifend abspeichern im Seed return (Seed = _uNewSeed); } // setzt (Zeit-) zufällige Startzahl für Generator unsigned CRandom::Randomize(void) { // ermittle eine Startzahl aus der Systemzeit time_t lSecondsFrom1970; time(&lSecondsFrom1970); // setze deren <unsigned>-Teil als Startwert ein return SetSeed((unsigned)lSecondsFrom1970); } // holt <unsigned> Zufallszahl aus (0, eMODUL) unsigned CRandom::GetRandom(void) { unsigned uNew, uDiv, uMod; // Overflow-vermeidendes Errechnen von: // iSeed := (eFAKTOR * iSeed) mod eMODUL, // wobei ein Zero-Seed geliftet wird. uNew = (Seed != 0) ? Seed : (unsigned)eMODUL; uDiv = uNew / eQUOT; uMod = uNew % eQUOT; uNew = eFAKTOR * uMod - eREST * uDiv; // neue interne Zufallszahl merken return SetSeed(uNew); } // holt <unsigned> Zufallszahl aus [0, uLimit) unsigned CRandom::GetRandom(unsigned _uLimit) { // unmögliche Forderungen ignorieren if (_uLimit <= 1 || _uLimit >= eMODUL) return 0; // iterative gleichverteilte Erzeugung for (;;) { // neuen Kandidaten testen unsigned uAntwort = GetRandom(); // Gleichverteilung sicherstellen if (uAntwort < (eMODUL - (eMODUL-1) % _uLimit)) return uAntwort % _uLimit; } } // holt Fließkommazahl aus [0.0, rLimit) double CRandom::GetRandom(double _rLimit) { // unmögliche Forderungen ignorieren if (_rLimit <= 0.0) return 0.0; // transformiere auf gewünschtes Intervall return (double)((GetRandom()-1)>>1) * _rLimit / INT_MAX; } // ermittelt Anzahl gesetzter Bits in <int> Zahl int CRandom::CountBits(unsigned _uHash) { // initialisiere Bit-Zaehler int iBitCount = 0; // verarbeite von unten her alle Testzahl-Bits do { // zaehle den Wert des letzten Bits und iBitCount += (int)(_uHash & 1); // schifte, bis kein gesetztes Bit mehr da ist } while (_uHash >>= 1); // antworte mit gefundener Bit-Anzahl return iBitCount; } // liefert positive Spezial-Zufallszahlen für Hashing: // liefert eine positive Zufallszahl, die als Binärzahl // genau eHASH_BITS Einsen hat (für XOR Overlay Zahlen) int CRandom::GetHash(void) { int iAntwort; // erzeuge positive Zufallszahl do { iAntwort = (int)GetRandom(); // negative Zufallszahl erhalten? if (iAntwort < 0) { // dann eben komplementieren iAntwort = ~iAntwort; } // bis deren Bit-Anzahl exakt stimmt } while (CountBits((unsigned)iAntwort) != eHASH_BITS); return iAntwort; }
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.