Dotaz: C++ zvyseni RAND_MAX

[Michal Reynolds]

Zdravim, potreboval bych generovat v C (pseudo)nahodna cisla z intervalu 0 - 4294967295, ale funkce rand() je generuje pouze do konstanty RANDMAX, coz je 2147483647. Jde toto nejakym zpusobem obejit?

Odpovědi

[AraxoN]

Buď môžeš rovno čítať 4 bajty z /dev/urandom, alebo volať rand() dvakrát, čím dostaneš 62 pseudonáhodných bitov a z nich si potom vybrať tých 32 (napr. prvých 16 z prvého volania, druhých 16 z druhého).

[l4m4]

Volat random() dvakrát bych -- pokud nejsou k disposici knihovny s lepšími generátory (MT, Tausworthe, MWC, ISAAC, ...), což běžně jsou -- asi doporučil, nevadí-li snížení efektivity dané nutností generovat dvě čísla. Rozhodně spíš než nějaké matlání lineárních kongruentních generátorů (s příšenými vlastnostmi), o kterých píší níže jiní. Není-li rychlost klíčová, tak to nevadí.

Je-li rychlost klíčová, tak jednak se dá napsat wrapper, který ten to druhé náhodné číslo, z nějž je zapotřebí jen jeden bit, cacheuje a používá z něj bity postupně. Ale spíš je pak zapotřebí používat jiné generátory než systémový random(), umožnit inlinovat kód generování náhodnného čísla, ...

[Šangala]

Pokud na tom nezáleží tak třeba:

#include <iostream>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <iomanip>

int main()
{
  srand(time(NULL));
  std::cout << " RAND_MAX: "  << RAND_MAX << std::endl;
  uint32_t r = rand() % 2147483648;
  r += rand() % 2147483648;
  std::cout << " 31bit: "<< std::setw(10) << std::hex <<  r << std::endl;
  r = ((rand() % 256) << 24) | ((rand() % 256) << 16) | ((rand() % 256) << 8) | ((rand() % 256)) ;
  std::cout << "  8bit: " << std::setw(10) << std::hex<<  r << std::endl;
  return 0;
}

[:::]

Příloha:

• dist.JPG (23625 bytů)

vim ze pises "pokud na tom nezalezi", ale i tak bych upozornil ze hlavne ten prvni zpusob je hodne spatnej. Problem je ze cisla priblizne uprostred intervalu se daji ziskat vice zpusoby nez cisla na kraji. Napr 0 ziskam jenom jednim zpusobem: 0+0, ale 100 ziskam hodne zpusobama 0+100, 1+99, 2+98, ...

zkousel jsem kod

#include <iostream>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <iomanip>
 
int main()
{
        int cnt[256] = {0, };

        for (int i = 0; i < 100000; ++i)
        {
                uint32_t r = rand() % 128;
                r += rand() % 128;
                ++cnt[r];
        }
        
        for (int i = 0; i < 256; ++i)
        {
                std::cout << cnt[i] << "\n";
        }
}

a dava to distribuci co je v priloze.

Ten druhej zpusob je lepsi, nekde jsem ale cetl ze u "linear congruential generatoru" (kterej je predpokladam pouzitej v rand()) maji spodni bity kratsi periodu nez horni, proto by mozna bylo lepsi pouzit deleni misto modula.

Puvodnimu autorovy bych doporucil:

- pokud potrebujes "cryptographically secure" generator tak pouzi /dev/random

- pokud ne tak se podivej na generatory v c++11

- pokud nemuzes pouzit c++11 tak naprogramuj vlastni linear congruential generator. Navod treba tady: http://en.wikipedia.org/wiki/Linear_congruential_generator. Z tabulky vem hodnoty pro 64 bit. Celkove to budou asi 3 radky kodu...

[Šangala]

Napsal jsem tam „pokud na tom nezáleží“, protože vím, že to není „bezpečné“ řešení, ale je to jednoduché a rychlé. Na bezpečné řešení se dá použít třeba i openssl.