Author: Vincent Diepeveen
Date: 10:39:03 10/29/03
Go up one level in this thread
On October 28, 2003 at 23:03:31, Robert Hyatt wrote:
In general combining 2x32 goes wrong, so you shouldn't give this tip to him Bob!
If generalized over the average 32 bits PRNG and generate 64 bits hash numbers
with it like this, then you end up with multilineair connection and many
collissions.
Now i'm sure you will show up with something that doesn't have multilineair
connection, but that's not what i call the 'average' 32 bits RNG :)
It's like saying using 'goto' is ok in a programming environment. Where this is
certainly true, it should not be a policy to do so :)
>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.