Author: Tony Werten
Date: 02:50:43 10/29/03
Go up one level in this thread
On October 28, 2003 at 23:03:31, Robert Hyatt wrote:
>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.
Doubtfull. I can't do the math but it should be worse. Else a 4 x 16 bit would
be just as good, or 8x8,.. or 64x1
Tony
>
>>
>>>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.