Author: Vincent Lejeune
Date: 04:04:09 10/29/03
Go up one level in this thread
On October 29, 2003 at 05:50:43, Tony Werten wrote:
>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
just Before seeing your post, I would add to Bob's one, 64x(1 bit random
generator) is as good as 1x64
I don't see why you think the opposite ...
>
>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 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.