Author: Robert Hyatt
Date: 06:44:48 10/30/03
Go up one level in this thread
On October 29, 2003 at 13:39:03, Vincent Diepeveen wrote: >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! In general, it works _perfectly_. This is not hard to prove mathematically. Particularly when we need less than 1000 random numbers for Zobrist hashing. > >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. Not for 1000 numbers, again. Do the test. _then_ report the results. I have done this. Several of us tested our random numbers a few years ago. The RNG from Numerical Recipes that I use is _very_ good. Particularly when I need less than 2000 32-bit values to make less than 1000 64 bit numbers. I've run _real_ tests using my random numbers. You can find my results, Bruce's results, and John Stanback's results posted on r.g.c.c several years ago. I saw less than one collision per 3 hours of searching. That can be ignored easily. > >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 :) I have _always_ cited my RNG as an adequate solution to the problem. It is an "average RNG" that was published in the book "Numerical Recipes" 20+ years ago. > >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 :) Eh? _every_ program you write has goto's. (aka jumps). They are not bad. In fact, they are _unavoidable_. > >>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.