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.03 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.