Generování pseudonáhodných čísel

pe25tr

Generování pseudonáhodných čísel
« kdy: 20. 01. 2016, 12:57:42 »
Ahoj, potřeboval bych doporučit vhodný algoritmus generování PRND.

Řeším fyzikální úlohu (proudění) kde se jistý člen řešených rovnic z určitého důvodu trochu pošťouchne náhodnou fluktuací.

Jde o to, že v každé buňce výpočetní sítě je potřeba 50 PRND, výpočetní síť má 1e6 až 1e7 buněk a provádí se 1e4 až 1e5 iterací, tzn. náhodné číslo je potřeba získat 5e11-krát až 5e13-krát.
Výpočetní čas se přitom nesmí zvýšit o více než 20-30% oproti modelu bez náhodných flutuací (dny až týdny).

RAND_MAX stačí 1e3 až 1a4, posloupnost PRND by se (asi) neměla opakovat dříve než po 1e8 realizacích.
Nesmí vadit omp parallel.

Díky

« Poslední změna: 20. 01. 2016, 19:55:26 od Roman Bořánek »


gamer

Re:generování pseudonáhodných čísel
« Odpověď #1 kdy: 20. 01. 2016, 14:13:31 »
http://www.cplusplus.com/reference/random/mt19937/

Je to hodně rychlé s periodou 2^19937-1. Thread safe to nebude, ale vzhledem k periodě by neměl být problém mít instanci generátoru per thread.

k

Re:generování pseudonáhodných čísel
« Odpověď #2 kdy: 20. 01. 2016, 14:55:10 »
Máte-li Broadwell a novější pak máte generátor přímo pod nosem :)
https://github.com/viathefalcon/rdrand_msvc_2010

trubicoid2

Re:generování pseudonáhodných čísel
« Odpověď #3 kdy: 20. 01. 2016, 15:01:25 »
mersene twister je dobrej, matlab ho pouziva jako vychozi: http://www.mathworks.com/help/matlab/ref/randstream.list.html

jinak je mozna uzitecne se zamyslet, jestli pouzivat jen rovnomerne rozlozeny nahodny cisla, nebo spis normalne - gausovsky rozlozeny nahodny cisla, to by pak bylo jako maxwellovo rozdeleni rychlosti ve vzduchu a to mi prijde realnejsi

pe25tr

Re:generování pseudonáhodných čísel
« Odpověď #4 kdy: 20. 01. 2016, 15:29:28 »
http://www.cplusplus.com/reference/random/mt19937/

Je to hodně rychlé s periodou 2^19937-1. Thread safe to nebude, ale vzhledem k periodě by neměl být problém mít instanci generátoru per thread.

mersene twister je dobrej, matlab ho pouziva jako vychozi: http://www.mathworks.com/help/matlab/ref/randstream.list.html

Nakonec asi ano.

Původně jsem myslel na něco takového:
Kód: [Vybrat]
  static uint16_t x=1,y=1;
  uint16_t t=(x^(x<<5));
  x=y;
  return y=(y^(y>>1))^(t^(t>>3));

Máte-li Broadwell a novější pak máte generátor přímo pod nosem :)
https://github.com/viathefalcon/rdrand_msvc_2010
Tak to bohužel nemám...

jinak je mozna uzitecne se zamyslet, jestli pouzivat jen rovnomerne rozlozeny nahodny cisla, nebo spis normalne - gausovsky rozlozeny nahodny cisla, to by pak bylo jako maxwellovo rozdeleni rychlosti ve vzduchu a to mi prijde realnejsi
To už se dá vyrobit transformací z rovnoměrného rozložení...

Díky.


Trubicoid2

Re:generování pseudonáhodných čísel
« Odpověď #5 kdy: 20. 01. 2016, 15:46:16 »
Ano, transformací třebas https://en.wikipedia.org/wiki/Box–Muller_transform
Asi je i 3d varianta

cuda

Re:generování pseudonáhodných čísel
« Odpověď #6 kdy: 20. 01. 2016, 16:30:02 »
grafika od Nvidie, taky pomuze :

./MersenneTwisterGP11213

Throughput = 5.8622 GNumbers/s, Time = 0.00041 s, Size = 2400000 Numbers

Jose

Re:generování pseudonáhodných čísel
« Odpověď #7 kdy: 20. 01. 2016, 17:44:45 »
//http://en.wikipedia.org/wiki/Random_number_generation

void RNG_uint32(uint32 *output)
{
   uint32 res;
   m_z = 36969 * (m_z & 65535) + (m_z >> 16);
   m_w = 18000 * (m_w & 65535) + (m_w >> 16);
   *output = (m_z << 16) + m_w;  /* 32-bit result */
   return 1;
}

void RNG_InitGenerator_uint32(uint32 seed1, uint32 seed2)
{
   m_w = seed1;
   m_z = seed2;
}

vm_lama

Re:generování pseudonáhodných čísel
« Odpověď #8 kdy: 20. 01. 2016, 19:06:23 »
V dnesni dobe stale vede jako nejlepsi PRNG Mersenne Twister (ci jeho lehke upravy - napr. pro vytvoreni CSPRNG), ktery byl vyse zmineny jiz vicekrat. I pres zdanlivou komplikovanost patri mezi ty nejrychlejsi a jeho vlastnosti jsou velice zajimave - proto je pouzity v nastrojich jako Matlab ci CUDA ci v knihovnach programovacich jazyku nebo samotnych implementacich interpretu (napr. DaoVM https://github.com/daokoder/dao pro jazyk Dao).

Re:generování pseudonáhodných čísel
« Odpověď #9 kdy: 20. 01. 2016, 19:49:14 »
int getRandom() {
  // chosen by fair dice roll
  // guarenteed to be random
  return 4;
}