Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: 64-Bit random numbers

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