Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: pe25tr 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
-
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.
-
Máte-li Broadwell a novější pak máte generátor přímo pod nosem :)
https://github.com/viathefalcon/rdrand_msvc_2010
-
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
-
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:
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.
-
Ano, transformací třebas https://en.wikipedia.org/wiki/Box–Muller_transform
Asi je i 3d varianta
-
grafika od Nvidie, taky pomuze :
./MersenneTwisterGP11213
Throughput = 5.8622 GNumbers/s, Time = 0.00041 s, Size = 2400000 Numbers
-
//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;
}
-
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).
-
int getRandom() {
// chosen by fair dice roll
// guarenteed to be random
return 4;
}