[C] generator naključnih števil

živjo.
kako se napiše program v C-ju za generator naključnih števil. Vendar tako, da bo ob vsakem zagonu se zgenerirala neka druga številka.
hvala.

Čarobne besede: seed, [current] time

Nisi Mimogrede, o pravih random generatorjih se niti ne da pogovarjat, vedno gre za pseudo random generatorje, v računalništvu ni naključij...

Rahlo je odvisno na katerem sistemu si, nekateri lovijo entropijo ze sami po sebi (bsd), na drugih se moraš znajti. Če ti portabilnost kode ni problem, priporočam čas + GetTickCount() za seed, ceprav je v osnovi tako da rand funkcija od cja smrdi do nebes. Ce rabis zadevo kaj bolj "random" (nič ni naključje) potem se spravi po netu poiskat ali implementacijo marseine twisterja ali pa si prevedi tole psevdo kodo v c (vzeto iz wiki):

// Create a length 624 array to store the state of the generator
var int[0..623] MT
var int y
// Initialise the generator from a seed
function initialiseGenerator ( 32-bit int seed ) {
MT[0] := seed
for i from 1 to 623 { // loop over each other element
MT[i] := last_32bits_of((69069 * MT[i-1]) + 1)
}
}

// Generate an array of 624 untempered numbers
function generateNumbers() {
for i from 0 to 622 {
y := 32nd_bit_of(MT[i]) + last_31bits_of(MT[i+1])
if y even {
MT[i] := MT[(i + 397) % 624] bitwise xor (right_shift_by_1_bit(y))
} else if y odd {
MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
}
}
y := 32nd_bit_of(MT[623]) + last_31bits_of(MT[0])
if y even {
MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y))
} else if y odd {
MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
}
}

// Extract a tempered pseudorandom number based on the i-th value
function extractNumber(int i) {
y := MT[i]
y := y bitwise_xor (right_shift_by_11_bits(y))
y := y bitwise_xor (left_shift_by_7_bits(y) bitwise_and (2636928640))
y := y bitwise_xor (left_shift_by_15_bits(y) bitwise_and (4022730752))
y := y bitwise_xor (right_shift_by_18_bits(y))
return y
}

Načeloma je bolj "random" kot npr. cjeve funkcije (spet malo odvisno od kompajlerja oz. knjiznice), še toliko bolj če za seed jemljes vrednost, ki je rezultat vseh do tistega trenutka generiranih vrednosti. Še o seedih; odlično je če jih imaš možnost jemati iz okolja, pred leti, sem npr. poslušal "motnje" na vezju od zvočne kartice (za 100 ms) in iz rezultata generiral hash, ga shranjeval v registry in ga uporabil pri generiranju naslednjega hasha. Druga taka luškana varianta je postavi mrežno kartico v "promiskuiteten" (he he obožujem ta izraz) način delovanja in računanje neke vrednosti iz vsega prometa na mreži (spet rahlo odvisno na kakšni mreži si)... seveda je pa tega še precej, lovljenje "kriljenja" z miško, lovljenje tipk, lovljenje imen datotek, ki se odpirajo,... Če se greš pa kaj resnega (npr. loterija), pa ne bo šlo brez igračk kot; http://www.random.org ali pa celo hardwarski random generatorji.

Odkar je RAMa kar prilično, je dober način za random ta, da nekam v spomin (ne maram napisat scrkljane besede "pomnilnik") napišeš 100 milijonov decimalk števila PI in po 3 naenkrat uporabljaš kot random število od 0 do 999. E.g.

Kdo te heca, yeti?

> Zakaj bi bilo to random?

Če ni, se boš vpisal v zgodovino matematike kot tisti, ki je dognal takoimenovano ne-normalnost števila PI.

> Če vzameš tri števila iz neke lokacije v memoriji, ki vsebujejo vnaprej generirano konstanto, bo ta lokacija tako ali tako ista?

Priporočam menjanje lokacije, da ti ne bo stalno vračalo 314.

> Poleg tega je problem zračunati pi na toliko decimalk natančno...

Mogoče bi pogooglal mau. Maš milijardo decimalk na netu ready to DL.

> Ciljaš na tole: http://www.lbl.gov/Science-Articles/Arc... ?

No, tud lahko.

> samo problem je kako boš bral iz random lokacij, da bi dobil random števila

Komot uhka. Lepo se sekvencionalno premikaš in jih jemlješ po bitnih vzorcih 7, 11, 13, 14 ... Če je vzorec 64 biten, imaš več dovolj dobrih random števil, kot jih boš rabu. Vsaj dokler RAMa ne bo precej več na razpolago.

Hja ne. Ti bereš kar po vrsti. 314, 159, ... do konca bitnega stringa.

Potem vzameš bitno mapco 11 decimalno, ali 1011 binarno. Pa spet bereš do konca. (341,192 ...)

Potem vzameš bitno mapco 13 decimalno, ali 1101 binarno. Pa spet bereš do konca.

Zapomniš si pa vedno dve števili, od katerih greš naprej. Lokacijo (offset) in mapco.

Maš robe dost, tako da prvo 3 res komot potratiš.

hvala..

hmm, ne ravno, če bereš po vrsti, sekvenca ne bo random. vedno bo ista, čeprav bo raztegnjena v nedogled. nekje moraš začeti, da je na vsaki mašini drugače, oz. začetni seed mora biti random (cajt, gettickcount,... branje z sound kartica, mreža, premiki miške), ostalo bo pa šlo.

Mersenne twister @ Wikipedia

---

Advantages

As the commonly used variant of Mersenne Twister, MT19937 has e.g. the following desirable properties:

1. It was designed to have a colossal period of 2^19937 − 1 (the creators of the algorithm proved this property). In practice, there is little reason to use larger ones, as most applications do not require 2^19937 unique combinations.
2. It has a very high order of dimensional equidistribution (see linear congruential generator). Note that this means, by default, that there is negligible serial correlation between successive values in the output sequence.
3. It is faster than all but the most statistically unsound generators.
4. It passes numerous tests for statistical randomness, including the stringent Diehard tests.

> Težava je tudi v tem, da nam takih števil lahko slej ko prej zmanjka.

Če se boš držal mojega navodila zgoraj, ti ne bo zmanjkalo teh števil do leta 2012, pa če jih rabiš milijon na sekundo.

Potem me spet vprašaj.

Thomas, pa si prepričan da je tisti "tvoj" generator dovolj kvaliteten in kaj boljši od ANSI C generatorja?

Denimo, da je bitna maska .....101. Naslednja bitna maska je potem .....110. Če po tem vzorcu jemljemo cifre iz števila pi, pomeni, da se pri naslednji iteraciji spremeni le zadnji (least significant) del števila.

Mene tak generator ne bi prepričal, raje bi vzel kaj bolj preizkušenega

Moram biti nekoliko natančnejši.

Za en prehod se strinjava, da je dovolj random?

Jah četudi bi letelo name, noben problem, bi ne zameril.

Itak ob tem, ko se usajam na temle forumu, konstruiram eno milijone vrstic veliko kodo. Tako da sem, kar se štorastosti tiče, guilty as charged.

Samo ne bi o detajlih.

Ne morem nič rečt. Samo povem, da se na takele bizarne načine lotevam stvari. Da če bi rabu dober random, bi ga naredil na takle način.

yeti: ok, podal si statistične teste za decimalke števila pi.

Vsi psevdonaključni generatorji, ki se na široko uporabljajo, so na tak način testirani. Tako lahko eliminirano tiste generatorje, ki so slabi.

Thomas: recimo, da se za en prehod strinjava. Ampak to je premalo. Kako naprej?

In zakaj bi torej uporabljal velike količine pomnilnika za decimalke števila pi, ko pa obstajajo generatorji, ki delujejo hitro, imajo dolge periode in prav tako prestanejo statistične teste. (če gledamo širše, v marsikaterem mikroračunalniku oz. mikroprocesorju nimamo na razpolago več kot nekaj registrov, tam zato shranjevanje 100M cifer števila pi sploh ne pride v poštev).

No, res je kar pravi Thomas: skupine decimalk števila PI uporabljene kot zaloga semen za kak klasičen (iterativni) random-generator bodo dajale odlične rezultate - pod pogojem, da se jih izbira na težko ponovljiv način To s ponovljivostjo je ključnega pomena in tukaj s PIjem takoj nastopi problem, da je sam postopek več kot očitno popolnoma determinističen, računanje vedno novih decimalk pa je milorečeno... algoritmično neperspektivno.

Kot je že nekdo omenil zgoraj, je karkoli na osnovi realnega časa je, primitivno in naivnokot se sliši, zelo učinkovito in enostavno sredstvo za povečevanje entropije generatorja. Namreč, enkrat ko bo tako, časovno odvisno generirano psevdo-naključno število dobila v roke neobveščena stranka, ji bo zelo težko ugotoviti, kdaj točno je bil postopek izveden.

Jasno, YMMV, ampak saj potencialno je tak postopek boljši od kateregakoli "šprudlanja" bitov, ker deter. kombiniranje NE more povečati entropije, saj kolikor je znano.

Glede "kvantnih kartic", karkoli že počnejo pa .. prihranite denar. Zgenerirajte si čisto pravo pravcato naključno število po mojem receptu z navadno zvočno kartico! Hecam se, recept ni moj, je bil pa že dejansko uporabljen in je popolnoma primeren za samogradnjo. Gre pa v osnovi takole: dobite si radijski sprejemnik in ga nastavite da bo lovil t.i. atmosferski beli šum, nakar pridno samplajte in voila, čisto prava pravcata entropija iz globin vesolja ;) Jee!

Kot rečeno, ne boste prvi gl. http://www.random.org, odlično branje mimogrede!

"Zgenerirajte si čisto pravo pravcato naključno število po mojem receptu z navadno zvočno kartico! Hecam se, recept ni moj, je bil pa že dejansko uporabljen in je popolnoma primeren za samogradnjo. Gre pa v osnovi takole: dobite si radijski sprejemnik in ga nastavite da bo lovil t.i. atmosferski beli šum, nakar pridno samplajte in voila, čisto prava pravcata entropija iz globin vesolja ;)"

Ne rabiš. Odpreš kanal na sb v kar se da dobri kvaliteti zapisa in dobil boš dovolj prasketanja in pokanja. Prednost imajo slabše kartice Tudi brez mikrofona. Sprobano in deluje.

"Implementacije so zelo verjetno različne, samo načeloma naj bi zajemala entropijo na osnovi hardvera tvojega stroja... po mojem na osnovi cajta spet."

Ne samo na osnovi časa. ne morem posplošit, vendar v osnovi; čas + mrežni promet + keyboard + dodatno; odvisno kaj imaš (sound kartica, miška).

Tkole bom reku.

Decimalke števila PI so tako dober random, kot je intergalaktični vakuum dober. Namreč obojega zaenkrat nobena mašina (vakuuma ali magari hardware generator) ne delata na tako visokem nivoju.

Samo po intergalaktični vakuum ne morš, da bi ga potem nekam filov. Po decimalke števila PI greš pa lahko.

Je pa po drugi strani čisto res, da PI je od človeka narejena mašina. No more, no less!