Author: Vincent Diepeveen
Date: 18:29:18 10/28/03
Go up one level in this thread
On October 28, 2003 at 17:55:14, Reinhard Scharnagl wrote:
>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).
Wrong, i had very bad experiences combining 2 numbers of 32 bits when i had
programmed in a check how many collissions that gave, it exponentially became
more collissions each x million nodes when i did this very buggy combination.
I might be running again a collission test at the supercomputer at 64 processors
or so, if i find the time and even more important figure out a way how to test
collissions in parallel as that's not so easy because there is a continues
overwriting of the same entries by more than a few processors :)
A real 64 bits number generator solves all the problems though, it did for me :)
>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.02 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.