Author: Robert Hyatt
Date: 20:03:31 10/28/03
Go up one level in this thread
On October 28, 2003 at 21:29:18, Vincent Diepeveen wrote: >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. > That just means you don't know how to do it. I do this with a well-known uniform 32 bit random number generator and it works _perfectly_. >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 :) A good 2x32 generator is just as good as a 64 bit generator. The math is simple to prove when you think about it for a minute. > >>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.