» »

[C] generator naključnih števil

[C] generator naključnih števil

KtMw ::

ž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.
  • spremenilo: snow ()

jernejl ::

Generatorju moraš nastaviti seme s funkcijo srand(unsigned int seed), navadno se za seme uporabi kar trenutni čas.

Primer je tukaj.

OwcA ::

Čarobne besede: seed, [current] time
Otroška radovednost - gonilo napredka.

IceIceBaby ::

Nisem ravno programer, zato verjetno moja rešitev ni idealna. Amapk jaz sem problem rešil tako, da sem ukaz za generiranje random števila dal recimo v while zanko (ali pa enostavno dodaš pogojni stavek). Zadevo ponavljaš toliko časa, dokler ni generirano število različno od prejšnjega.

ups, sem bil prepozen, pa še čudno rešitev sem podal :)

Zgodovina sprememb…

yeti ::

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

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.

Zgodovina sprememb…

  • vrnilo v prejšnje stanje: OwcA ()

yeti ::

Ravno sem gledal pri kolegu eno tistih kamerc brez ohišij za drobiž... odlična je, toliko ima šuma, da bi jo lahko uporabil za generirat entropijo :D

Thomas ::

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.
Man muss immer generalisieren - Carl Jacobi

yeti ::

???? ne me hecat :(

Thomas ::

Kdo te heca, yeti?
Man muss immer generalisieren - Carl Jacobi

yeti ::

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

Zakaj bi bilo to random? Če vzameš tri števila iz neke lokacije v memoriji, ki vsebujejo vnaprej generirano konstanto, bo ta lokacija tako ali tako ista? Poleg tega je problem zračunati pi na toliko decimalk natančno... na kaj bi se pri tem opiral, na napako pri zaokroževanju? Tako ali tako bi se (teoreticno vsaj) ta napaka pri vsakem računanju decimalk propagirati na enak način in rezultat bi bil spet vedno enak. Ciljaš na tole: http://www.lbl.gov/Science-Articles/Arc... ? Tudi če dobiš neponavljajoče se decimalke pija ostaja še vedno problem, da bi jih moral pobirati iz random lokacije v memoriji, za kar spet rabiš random generator. Catch-22?

Zgodovina sprememb…

  • spremenil: yeti ()

Thomas ::

> 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.
Man muss immer generalisieren - Carl Jacobi

yeti ::

Ne čakaj, čakaj... vem kam ciljaš z pi, samo problem je kako boš bral iz random lokacij, da bi dobil random števila; če greš vedno po istem postopku skozi memorijo, boš vedno dobil enaka "random" števila. Temu je namenjen seed. Z decimalko pi, dobiš samo razpšenost števil, ne dobiš pa naključnosti, to ti lahko imho zagotavlja samo naključen seed (ali v tvojem primeru lokacija prvega števila v memoriji) in za isti seed boš vedno dobil ista števila. Problem pri naključnosti je naključno izbrati seed sicer bi lahko teoretično bral katerikoli dovolj velik fajl, magari raran (da se znebiš ponavljanj) gothic 3 :D. Ravno iz tega razloga sem se mučil z dobivanjem entropije iz raznih možnih virov od networka do sound kartice (npr; hash od npr. wava iz SB uporabiš za seed (magari pri pi) in vsako "generirano" random število spet hashaš z njim, vsak rezultat pa zapišeš npr. v fajl in ga ob ponovni inicializaciji spet uporabiš (wav => hash + shranjen hash = new seed).

Thomas ::

> 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.
Man muss immer generalisieren - Carl Jacobi

yeti ::

Ne vem če se razumeva; če boš za prvi indeks v memoriji vzel npr. pozicijo 1 na kateri boš našel 141, in boš na kakršenkoli način iz 141 (!) izračunal (!) naslednji index, boš pri idx = 1vedno dobil ven isto zaporedje števil. lahko si sicer zadnjega generiranega shraniš, samo gre vedno za uganljivo sekvenco, če veš koliko jih je bilo že generiranih... čeprav v bistvu imaš prav, če si zadni uporabljeni index shranjuješ, za rezultat dobiš random vrednost, jaz pa sem zašel v probleme z inicializacijsko vrednostjo seeda...

Zgodovina sprememb…

  • spremenil: yeti ()

Thomas ::

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š. ;)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> [Ta odgovor je spremenil yeti dne 02.11.2006 ob 11:00:09.]

Good. Se strinjava. Welcome na tale forum, BTW.
Man muss immer generalisieren - Carl Jacobi

yeti ::

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.

Zgodovina sprememb…

  • spremenil: yeti ()

Thomas ::

> začetni seed mora biti random (cajt, gettickcount,... branje z sound kartica, mreža, premiki miške)

Jasno. Ampak to se razume samo po sebi. Z vsemi algoritmi za pseudorandom števila je tako.

Jaz sem samo nadomestil niz kode z (enostavnim) nizom kode, ki bere predizračunan PI.

Je manj computing požrešno in še zelo dobro dela.

Boljše rešitve ne poznam.
Man muss immer generalisieren - Carl Jacobi

yeti ::

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.

jernejl ::

yeti, zakaj pa meniš, da je tisti tvoj psevdokod bolj "random" od c-jevskega pseudorandom generatorja? Kaj sploh pomeni "bolj random" ?

Vsak algoritem, ki ne vsebuje nekega izvora naključnosti, je psevdonaključen. Tudi tisti tvoj algoritem je determinističen. Razlike med različnimi algoritmi generiranja psevdonaključnih števil pa so v tem, da nekateri generatorji generirajo števila, ki so bolj enakomerno porazdeljena. Nekateri generatorji znajo generirati daljša zaporedja psevdonaključnih števil (zelo pomembno, če takih števil potrebujemo zelo veliko). Prav tako se lahko generatorji "izrodijo" (od neke točke naprej začnejo npr. zmeraj vračati zaporedje a,b,a,b,...).

Značilnost generatorjev, ki generirajo nova števila iz več poprej generiranih (in ne samo iz enega), je v tem, da je njihova perioda daljša (zmožni so generirati daljše zaporedje števil, preden se le-ta začnejo ponavljati). Kot že omenjeno, je to pomembno, če takih števil potrebujemo zelo veliko.

Ena možnost je že bila omenjena: če izhajamo iz števila pi ali e. Težava je v tem, da če zadeva ni vnaprej izračunana, je proces izračunavanja relativno dolg in pomnilniško potraten. (ideja z vnaprej izračunanimi števili je sicer možna... take variante so uporabljali nekoč, ko števil še niso mogli računalniško generirati. Težava je tudi v tem, da nam takih števil lahko slej ko prej zmanjka. Take metode so se uporabljale okrog 50 let nazaj. Rand corp. je tako leta 1955 izdala knjigo z milijon naključnimi števili, dobljenimi z metodo opazovanja rulete. Več informacij tukaj.)

Ostale možnosti so pa različne vrste generatorjev, ki števila sproti izračunavajo: linearni kongruentni generatorji, generatorji z rezanjem robnih cifer,...
Linearni kongruentni generatorji naprimer, delujejo po naslednji formuli:

X := a X + b (mod m)

Novo število torej dobimo tako, da staro pomnožimo z neko konstanto a, prištejemo konstanto b, ter vzamemo ostanek pri deljenju s konstanto m. Začetno število poda uporabnik generatorju v obliki semena.
Za generator ANSI C (ki ga uporabljamo, ko kličemo funkcijo rand()), velja:

a=1103515245
b=12345
m=2^31


Pa, da avtorja te teme preveč ne prestrašimo, za nezahtevna opravila je dovolj uporabiti primer, ki sem ga podal v mojem prvem odgovoru.

Thomas ::

> 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.
Man muss immer generalisieren - Carl Jacobi

yeti ::

jernejl: Saj ne mislim da je kaj bolj random, samo dal sem marsenne twister kot možnost, ker je znan kot eden bolj uporabljanih generatorjev nakljucnih števil in tudi temeljito je stestiran, kar se pa vnaprej generiranih števil tiče, je pa zame neuporabno. kar se mene tiče pri softwarskih generatorjih vse stoji na seedu.

"Pa, da avtorja te teme preveč ne prestrašimo, za nezahtevna opravila je dovolj uporabiti primer, ki sem ga podal v mojem prvem odgovoru."

ja. ostalo je samo zanimiva debata.

jernejl ::

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 :P

Thomas ::

Jah, če boš našel statistično luknjo v tem generatorju, si najpomembnejši matematik od Vege naprej, na naših tleh.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Moram biti nekoliko natančnejši.

Za en prehod se strinjava, da je dovolj random?
Man muss immer generalisieren - Carl Jacobi

yeti ::

jernejl; http://home.versatel.nl/galien8/pirando...

je pa ta metoda tako ekstremno štorasta (thomas; ne leti nate), da mi na kraj pameti ne pade da bi jo kadarkoli uporabil...

Thomas ::

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.
Man muss immer generalisieren - Carl Jacobi

t909 ::

OT: kaj pa delas Thomas?

Thomas ::

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.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Hehe .. v glavnem NIČ kar bi povzročilo Singularnost. ;)

Everyday zadeve.
Man muss immer generalisieren - Carl Jacobi

jernejl ::

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

Thomas ::

> Vsi psevdonaključni generatorji, ki se na široko uporabljajo, so na tak način testirani.

Hja, klinc. Sej si vidu na uni strani, ki jo je dal yeti. PI je bolj random kot daje "kvantna kartica". Zdrži 36 od 38 testov PI, KK pa samo 16 od 21. Tam nekje.



Drug prehod?

Narediš na prešprudlan bitni string.

Kako prešprudlaš? Ponucaš 1K bitov za šprudl mašino in zavržeš tisti K.

Bo?
Man muss immer generalisieren - Carl Jacobi

Matako ::

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!
/\/\.K.

Zgodovina sprememb…

  • spremenil: Matako ()

Matako ::

Aja drugače pa na večini unixoidnih sistemov imaš precej soliden random generator tudi enostavno v obliki naprave konkretno /dev/random - enostavno bereš ta fajl in to je to!

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

Zgodovina sprememb…

  • spremenil: Matako ()

yeti ::

"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 :D 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).

Zgodovina sprememb…

  • spremenil: yeti ()

Matako ::

@yeti: Hvala! Po pravici povedano sem šele sedaj prebral tvoj prvi post pod kodo - dodal malo redundance pač ;)

No saj itak v splošnem pa je tudi zelo pomembno za kaj sploh rabiš takale (psevdo)naključna števila. Za kriptografijo sigurno od viška glava ne boli, za vse ostalo, se pa človeški možgančki itak tako hitro zmedejo, da se jim zdi marsikaj čista zbrka ;)
/\/\.K.

Zgodovina sprememb…

  • spremenil: Matako ()

Thomas ::

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!
Man muss immer generalisieren - Carl Jacobi


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Vprašanje v zvezi z rand() funkcijo

Oddelek: Programiranje
494177 (3367) fireice
»

Varnost generatorjev naključnih števil

Oddelek: Novice / Varnost
485621 (5620) Thomas
»

Random le ni tako zelo naključen?

Oddelek: Znanost in tehnologija
91186 (1186) gumby
»

Colour (3,14.......) noise

Oddelek: Znanost in tehnologija
122030 (1636) Thomas
»

Ustavljivost linearno omejenih avtomatov (strani: 1 2 )

Oddelek: Znanost in tehnologija
843955 (3469) Matevžk

Več podobnih tem