» »

Vprašanje v zvezi z rand() funkcijo

Vprašanje v zvezi z rand() funkcijo

moose_man ::

Hoj!

Nekaj me bega. Pri raznoraznih simulacijah sem že večkrat uspešno uporabil generator rand(), seveda tako, da sem v programu enkrat samkrat seedal generator z srand(time(NULL)), nato pa klical rand() poljubno mnogokrat. To funkcijo sem uporabljal že mnogokrat (nazadnje par mesecev nazaj) in vedno je delala kot urica (dobival sem števila med 0 in RAND_MAX). Danes, ko sem hotel nekaj trivialnega napisat v C++ in zraven uporabit rand() na zgoraj opisan način, so me pri izpisu treh števil, ki bi morala biti naključna, presenetile številke 16025, 16121 in 16053.

Potem sem pognal programček, ki je naveden kot primer za rand() na cplusplus.com:
http://www.cplusplus.com/reference/cstd...

Ko sem ukazal programu naj izpiše število in program pognal večkrat (in ja, program sem parkrat pognal v časovnih presledkih, daljših od 1s) so rezultati ponovno bili v stilu zgornjih - se pravi neenaka, a vendarle definitivno nenaključna števila.
Tudi, ko sem v Codeblocks (kjer delam vse omenjeno) vklopil C compiler in poskusil zalaufati zadevo, sem dobil števila 19100, 19193 in 19428.

Glede na to, da tudi copypastei programov iz neta ne delajo - kaj je lahko narobe?

Naj to služi kot dokaz da sem rand() funkcijo že uspešno uporabljal - narejen naključni sprehod, kjer so smeri korakov izbrane naključno, dolžine korakov pa porazdeljene potenčno:
 Nakljucni sprehod

Nakljucni sprehod




In ja, uporabil sem google in ne, nisem prebral samo prvega zadetka pri brskanju.
  • spremenilo: moose_man ()

moose_man ::

Update.
Enako kodo sem preizkusil na drugem kompu št. 2 in tukaj dela kot se spodobi - seedanje random generatorja s time(NULL) tu dejansko učinkuje in števila so lepo random razmetana naokoli, kot se spodobi.

Vem da se očitna rešitev kaže v tem, da iz računalnika št. 1, kjer problemi še kar vztrajajo, zbrišem vso dokumentacijo, prevajalnik, urejevalnik, .... in nanovo naložim, ampak nekako se mi tega ne da počet - obstaja kakšna druga rešitev?

Lep pozdrav. :)

technolog ::

presenetile številke 16025, 16121 in 16053.


Zakaj? Mene to nič ne preseneča. A če bi kocko metal, pa bi trikrat padla 5, bi se tudi čudil?

moose_man ::

Verjetnost, da kocka trikrat pade na pet, je, od oka, 0.005.
Verjetnost, da pri naključnem žrebu števil od 0 do 32000 dobiš trikrat zaporedoma cifro med 16000 in recimo 16500 je 0,000004. Če si napišeš programčič, se ti to praktično ne bi smelo dogajat, če pa se ti slučajno že bi, bi se le enkrat v ful ponovitvah. Tudi s semirandom števili (preverjeno).

Programa pa seveda nisem pognal samo trikrat, ampak seveda večkrat, ker sem problem poskusil sam rešit, preden sem šel na križarski pohod po googlu in firbcat na forum. :) In trend pojavljanja podobnih cifer pri zaganjanju programa sem opazil tudi če sem med posamičnimi zaganjanji počakal par sekund. Primer s tremi konkretnimi ciframi sem pa pač dal, da bi se lažje razumelo, kaj je tisto kar me muči.

Sicer sem že našel druge generatorje naključnih števil in ne rabim nasvetov glede alternativ (čeprav ne škodijo nikoli če ima kdo kaj zanimivega za povedat) - zanima pa me, kaj je vzrok temu, da se rand() kljub pravilno spisani kodi, ki dela na enem računalniku, na drugem obnaša, kot se pač obnaša. :)

Zgodovina sprememb…

  • spremenilo: moose_man ()

technolog ::

Narobe razmišljaš. Verjetnost, da so števila, naključno izbrana iz intervala [0, 32.000] razmaknjena za manj kot 500 je še kar velika, cirka 0,1%.

Tebe preseneča to, da so števila preveč skupaj, ne da so med 16000 in 16500. Jasno je verjetnost, da števila ležijo v točno specifičnem majhnem intervalu dosti manjša, kot če gledaš verjetnost, da ležijo v kateremkoli majhenm intervalu.

5100, 5200, 5321 bi te tudi presenetilo, pa 7812, 7912, 8123 tudi. Verjetnost, da boš ta tak način presenečen je cirka 0.1%. In to se ti jasno komot zgodi v povprečju na vsakih 500 pogonov programa. Funkcija rand() deluje ok.

Zgodovina sprememb…

moose_man ::

technolog je izjavil:

Narobe razmišljaš. Verjetnost, da so števila, naključno izbrana iz intervala [0, 32.000] razmaknjena za manj kot 500 je še kar velika, cirka 0,1%.

Tebe preseneča to, da so števila preveč skupaj, ne sa so med 16000 in 16500.


Verjetnost da izbereš eno določeno število iz tega intervala: 1/32000

Verjetnost,da izbereš enega izmed 500 števil iz tega intervala:
16000 ALI 16001 ALI ... ALI 16500
1/32000 + 1/32000 + ... + 1/32000 = 500/32000
Verjetnost, da ponovno izbereš enega izmed teh 500 števil pri naslednjem žrebu:
enega izmed 500 števil moraš zadeti:
prvič IN drugič IN tretjič
500/32000 * 500/32000 * 500/32000 = 0.0000038

Me pa definitivno preseneča to, da so števila skupaj, ja. ;) In valda štekam, da se pri eni cifri mora začet algoritem za random števila in da ni point v tem ali so številke blizu skupaj pri 19000 ali pri 16000 ... konkretne primere sem dal samo zaradi tega da bi se lažje razumelo kaj me muči in da ne bi bilo odgovorov v stilu "ne seedaj v loop zanki ampak samo enkrat", ipd.

Zgodovina sprememb…

  • spremenilo: moose_man ()

technolog ::

Ti se moraš vprašat, kolikšna je verjetnost, da me program preseneti s števili, preblizu skupaj?

Matematično je ta verjetnost cirka 0,07%, kar pojasnjuje tudi to, da se ti je to pripetilo dvakrat na računalniku X in nobenkrat na računalniku Y.

Izračun te verjetnosti je še kar kompliciran, če želiš dobit točno številko.

p.s.: Lahko pa v seed daš 16025 in potem še dvakrat pokličeš rand() in boš dobil 16121 in 16053, praviloma na obeh računalnikih (privzemam da imata iste knjižnice).

Zgodovina sprememb…

moose_man ::

Jop, malo me je zaneslo ko sem se fiksiral samo na en interval ne pa na katerokoli petstotko. :)

Glede ostalega pa, zgoraj sem napisal:

moose_man je izjavil:


Programa pa seveda nisem pognal samo trikrat, ampak seveda večkrat, ker sem problem poskusil sam rešit, preden sem šel na križarski pohod po googlu in firbcat na forum. :) In trend pojavljanja podobnih cifer pri zaganjanju programa sem opazil tudi če sem med posamičnimi zaganjanji počakal par sekund. Primer s tremi konkretnimi ciframi sem pa pač dal, da bi se lažje razumelo, kaj je tisto kar me muči.


Pač, ne da se mi zdej dokazovat da to ne dela kot bi moglo - program sem velikokrat spremenil ter dobival rezultate opisane zgoraj in ga pognal večkrat kot samo dvakrat, no in tudi če bi bila verjetnost za tak rezultat 10% bi moral biti orng naivnež da bi verjel, da imam tako srečo, da se mi je to zgodilo tolikokrat.

Smurf ::

rand() je znan potem, da je zelo slab RNG in lahko dejansko ponagaja v dolocenih situacijah (zal tehnicnih podrobnosti zakaj se to zgodi nisem nikoli raziskal). Mislim, da se tvojemu problemu, da izogniti, ce vrzes stran nekaj prvih cifer.

Se boljsa resitev pa je verjetno uporaba c++11 headerja < random >, ki naj bi deloval bolje.

technolog ::

rand() je itak platform dependent. Tako da ne govorit na splošno. Če ma slučajno nek problem na platformi X, ga na Y nima.

Kar jaz trdim je ravno to, da se mora zgoditi od časa do časa, da so tri zaporedne številke tako skupaj. Ravno če se to ne bi dogajalo, bi bil problem.

darkkk ::

Tole je približno podoben problem, kot da imata vsaj dva v skupini 30 ljudi rojstni dan na isti dan (ki je precej velika :)). Če pa fiksiraš dan je verjetnost, da mata dva na določen dan ~0.

Tko da, meni se zdi to, da dobiš v nekem intervalu nekaj zaporednih z verjetnostnega vidika "normalno".

Smurf ::

technolog je izjavil:

rand() je itak platform dependent. Tako da ne govorit na splošno. Če ma slučajno nek problem na platformi X, ga na Y nima.

Kar jaz trdim je ravno to, da se mora zgoditi od časa do časa, da so tri zaporedne številke tako skupaj. Ravno če se to ne bi dogajalo, bi bil problem.

Da, ampak ce sem jaz OPja pravilno razumel se mu je na dolocenem racunalniku to vsakic zgodilo, kar pa je znan problem rand() na "dolocenih platformah" (happy ;p?).

Oz. z drugimi besedami, ce bos program zagnal 1000x in bo vsakic izbral 3 stevila iz istega ranga, je vecja verjetno, da gre za rand issue (se posebej, ker je ta issue znan), kot napacna interpretacija randoma.

Randomness ::

Verjetnost, da leži n "izžrebanih" števil znotraj nekega intervala je trivialno izračunati.
P(n,N,d) = \prod_{i=2}^n d/N
Formula velja seveda, ko je porazdelitev enakomerna in ko so r.v. porazdeljene i.i.d.

P(n=3, N=RAND_MAX+1=2147483648, d=1000000) = 2.17e-7
P(n=3, N=RAND_MAX+1=2147483648, d=500) = 5.42e-14

Poskusi pognati tole in napiši rezultat (moral bi biti blizu vrednosti 2.17e-7). Lahko poskusiš tudi za druge vrednosti d.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#define d 1000000
#define N (1 << 29)

int main() {
    uint a, b, c, i, n = 0;

    srand(time(NULL));

    a = rand();
    b = rand();

    for (i = 0; i < N; ++i) {
        c = rand();
        if (b >= a && c >= a && b - a < d && c - a < d) {
            ++n;
        }
        a = b;
        b = c;
    }

    printf("%u/%u\n", n, N);

    return 0;
}

moose_man ::

Randomness je izjavil:


Poskusi pognati tole in napiši rezultat (moral bi biti blizu vrednosti 2.17e-7). Lahko poskusiš tudi za druge vrednosti d.


Ko sem copypasteal kodo in pognal program sem dobil rezultat 0.3333.

Zgodovina sprememb…

  • spremenilo: moose_man ()

Randomness ::

Verjetno je implementacija rand funkcije, ki jo uporabljaš, res slaba.

"man rand" razlaga takole:
The versions of rand() and srand() in the Linux C Library use the same random number generator as random(3) and srandom(3), so the lower-order bits should be as random as the higher-order bits. However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)

Zgodovina sprememb…

moose_man ::

Windows 7 Professional. Compiler ki ga uporabljam je GNU GCC. Še enkrat, na enakem kompu je pol leta nazaj to delalo kot bi moralo (pa vmes nisem na novo nalagal operacijskega sistema, Codeblocksov, dokumentacije ...).

Še konkreten primer. Program, ki generira 4 naključna števila. Poganjal sem ga v zamikih nekaj sekund.
Pognal prvič:
13556
7
11577
30925

Pognal drugič:

13637
6574
32198
9916

Pognal tretjič:

13745
823
31891
17573

Zgodovina sprememb…

  • spremenilo: moose_man ()

Smurf ::

Ja, problem je v prvi stevilki.

To se zgodi zato, ker klices srand() kmalu drugega za drugim in je posledicno prvotni seed zelo podoben. Funkcija rand() pa zgolj izvede mnozenja na danem seedu (z omejevanjem na RAND_MAX) s cemer se dobi (prvo) stevilko in nov seed. Z vsakim ponovnim klicem rand() se ponovi tudi mnozenje, na novem seedu, ki se ze bolj razlikuje zato pride tudi 2. stevilka vsakic precej bolj drugacna.

Makes sense?

moose_man ::

Makes sense.
Ampak tisto kar doesn't make sense to me pa je to, zakaj preverjen seed odpove. :\

Smurf ::

Saj ne odpove. Treba je vedeti, da je rand() samo f(x) kjer je x=seed, f pa funkcija, ki dela mnozenja, sestevanja, div itd. (se mi zdi). Ce imas zelo podoben x bo tudi rezultat podoben. In v tvojem primeru je x podoben (ker je odvisen od casa, cas pa je podoben, ker si zagnal srand v casu sekunde).

Poskusi ponoviti vaju z 1 minutnim zamikom pa povej ce bo kaj vecja razlika :).

Ce je pa problem v tem, da dobis naenkrat (v istem programu) 3 enake rezultate gre pa za drugo zadeve (tako sem jaz prvotno razumel tvoj post).

Zgodovina sprememb…

  • spremenil: Smurf ()

moose_man ::

Prvi stolpec označuje čas, drugi pa vrednost ki jo vrne rand() ko ga v programu kličem prvič:

12:32:06 20190
12:32:31 20965
12:32:45 21027
12:33:19 21125
12:34:44 21396
12:39:13 22249

Na drugem kompu je bila razlika ogromna že če sem program pognal v zamiku sekunde ali dveh.

Ne vem ali sem prvi post naredil premalo razumljiv, ampak glavni problem je to, da pri večkratnem poganjanju programa rand() za prvo cifro vrže podobno vrednost kot par sekund prej in to se ne bi smelo dogajat. Očitno je nekaj narobe pri seedanju, ampak to s time(NULL) povsod oznanjujejo kot preverjeno metodo ... in ne vem kaj bi lahko bil vzrok. :]

Zgodovina sprememb…

  • spremenilo: moose_man ()

Randomness ::

Mislim, da ne gre za to. Če sta dva seeda po numerični vrednosti blizu skupaj, še ne pomeni, da bodo tudi generirane vrednosti "podobne". Generiranje psevdo-naključnih števil si lahko predstavljaš kot branje iz ring bufferja (brez brisanja elementov), ki ima v našem primeru RAND_MAX + 1 elementov, medtem ko seed pomeni, na katerem mestu začnemo. Če začnemo na dveh mestih, ki sta blizu skupaj, to še ne pomeni, da bomo prebrali podobne številke.

Sklepam, da uporabljaš implementacijo rand funkcije iz knjižnice msvcrt. Jaz bi na tvojem mestu najprej preveril, katero verzijo te knjižnice uporabljaš in pogooglaš, če je s to verzijo kaj narobe. Kot sicer malo verjetno vidim možnost, da ti je nekdo (beri: zlobna koda TM), v sistem podtaknil kak backdoor.

driver_x ::

Tudi jaz sem pomislil, da imaš pohekan random generator. Kakšen pa pride histogram vrednsoti, če ga narediš na obeh računalnikih?

Hayabusa ::

Če bi rad izumil pravi rand generator, potem odmisli included one in naj raje uporabnik z miško prestavlja kurzor po ekranu (tako kot pri truecrypt).

Randomness ::

Lahko poženeš tole:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>

#define n 10
#define N (1 << 30)

static int random_in_range(unsigned int min, unsigned int max);

int main() {
    uint x, i;
    time_t seed;
    uint f[n];

    memset(f, 0, n * sizeof(uint));
    seed = time(NULL);
    srand(seed);

    printf("seed= %zu\n", seed);

    for (i = 0; i < N; ++i) {
        x = random_in_range(0, 10);
        f[x]++;
    }

    for (i = 0; i < n; ++i) {
        printf("%02d: %g\n", i, (double)f[i] / N);
    }

    return 0;
}

/* semi-open interval [min, max) */
int random_in_range (unsigned int min, unsigned int max)
{
    int base_random = rand(); /* in [0, RAND_MAX] */
    if (RAND_MAX == base_random) return random_in_range(min, max);
    /* now guaranteed to be in [0, RAND_MAX) */
    int range       = max - min,
        remainder   = RAND_MAX % range,
        bucket      = RAND_MAX / range;
    /* There are range buckets, plus one smaller interval
     *      within remainder of RAND_MAX */
    if (base_random < RAND_MAX - remainder) {
        return min + base_random/bucket;
    } else {
        return random_in_range (min, max);
    }
}

technolog ::

Randomness je izjavil:

Verjetnost, da leži n "izžrebanih" števil znotraj nekega intervala je trivialno izračunati.
P(n,N,d) = \prod_{i=2}^n d/N
Formula velja seveda, ko je porazdelitev enakomerna in ko so r.v. porazdeljene i.i.d.


Narobe. Če že bi moglo bit 2d/N, ker če maš izbrano recimo število x, bo veljavna izbira za naslednje x-d do x+d, se pravi dvakratni interval. Pa še to je samo približek.

Recimo da: n=2, N=10, d=3:

Po tvoji formuli je 3/10, pravilno pa je 39/100.

Se pa strinjam z ostalim, Smurf pa se moti. Funkcija rand() redko uporablja deljenja, ponavadi so kake bitne operacije. In ne, rezultat ni nujno podoben seedu oz. prejšnjemu številu.

@Potok: To se ne bi smelo dogajat. Daj košček kode.

Zgodovina sprememb…

Smurf ::

@Randomness
Imas kaksen link, kjer pise da seed pove lokacijo v bufferju in ne zacetno vrednost oz. to kar si napisal, ocitno vecina googlovih zadetkov pa ocitno zavaja (oz. prevec poenostavlja) , v vecina primerov je omenjeno da seed predstavlja prvo stevilo iz katere se racuna random.

@technolog
Sej deljenje je bitna operacija :). Ampak zelo mozno, da se motim. Pac tako sem enkrat prebral, nisem pa se nikoli spuscal v podrobnosti. Se pa strinjamo, da bo isti seed vedno vrnil ven isto vrednost?

edit2:
Ce kdorkoli najde dobro razlago srand-a in rand-a za ta primer naj prosim nalima link.

Zgodovina sprememb…

  • spremenil: Smurf ()

technolog ::

Seveda, saj to je seed. Seed je prvo število, tako da je prvi klic funkcije v bistvu drugo. To pa še ne pomeni, da bo to generirano število blizu seedu. Razčisti si dejtva.

Deljenje je bitna operacija? Deljenje s potencami števila dva že, ostalo pa ne, pa še to samo celoštevilsko.

20 / 8 je isto kot 20 >> 3.

Se strinjamo. Če nimamo nobenega drugega vira naključnosti v sistemu, potem vsekakor.

Zgodovina sprememb…

Randomness ::

@technolog: Moja formula je že pravilna, če jo pravilno bereš. Jaz sem definiral dolžino celotnega podintervala kot d in ne 2*d+1 (kot si jo definiral ti). Z n sem definiral dolžino niza - to pomeni, da je pri n=1 verjetnost 1, ker je vseeno, kam "pade" prva vrednost. Res pa je, da sem zanemaril primere, ki ležijo na koncu intervala [0,N).

moose_man ::

driver_x je izjavil:

Tudi jaz sem pomislil, da imaš pohekan random generator. Kakšen pa pride histogram vrednsoti, če ga narediš na obeh računalnikih?


Histogram ne pokaže, da bi bile prisotne težave:
 null

null


(seveda je pri predalčku 30000-35000 manjša vrednost, ker nad RAND_MAX ni števil)

technolog ::

To si res zanemaril, pa ne samo to, zanemaril si še nekaj. Izbira tretjega števila je odvisna od prvih dveh, in tako naprej.

Recimo da sta prvi dve števili:

enaki: 100 100, v tem primeru je možnih vrednosti za tretje število še vedno dvakrat interval
za d različni: 100, 100+d, potem je možnih vrednosti samo še za en interval

vmes pa neka interpolacija.

Zgodovina sprememb…

moose_man ::

Em, nočem bit tečen, ampak a bi lahko bla tale tema posvečena diagnozi mojega problema in ne za računanje verjetnosti, prosim? Izračuni, ki jih delam na praksi te dni, so vezani na ene programčke, ki sem jih naredil že nekoč prej in res mi ni do tega, da bi moral kopat po njih in nadomeščat rand() s čim drugim. :(

technolog je izjavil:


@Potok: To se ne bi smelo dogajat. Daj košček kode.


No s tole kodo sem prišel do zgornjih rezultatov.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>


using namespace std;

int main() {

    srand(time(NULL));
    int c;
    for (int i = 0; i < 4; ++i) {
        c = rand();
        cout<<c<<endl;
    }
    return 0;
}

Zgodovina sprememb…

  • spremenilo: moose_man ()

Smurf ::

technolog je izjavil:

Seveda, saj to je seed. Seed je prvo število, tako da je prvi klic funkcije v bistvu drugo. To pa še ne pomeni, da bo to generirano število blizu seedu. Razčisti si dejtva.

Moja trditev je bila nekoliko drugacna.

Ce imamo 2 zagona programa, z seed1 kjer dobimo ven random_cifra_1 in seed2 kjer dobimo ven random_cifra_2. V primeru, da sta si seed1 in seed2 zelo podobna (recimo primer 20 mestne cifre, kjer se razlikujeta za 1-2 mesti), bi si lahko bili tudi random_cifra_1 in random_cifra_2 blizu.

technolog je izjavil:


Deljenje je bitna operacija? Deljenje s potencami števila dva že, ostalo pa ne, pa še to samo celoštevilsko.
20 / 8 je isto kot 20 >> 3.

Eh programerji, obesate se na vsako podrobost :). Moral bi obdrzati mnozino (bitne operacije), kot si ti napisal v prvotnem postu :). Pac deljenje s 3 se da naresti z bitnimi operacijami. Ampak niti ni pomembno tole.

technolog je izjavil:


Se strinjamo. Če nimamo nobenega drugega vira naključnosti v sistemu, potem vsekakor.

Kul :).

Me pa sedaj dejansko zanima kako je s tem.

Randomness ::

@Smurf: Sem se malo nerodno izrazil. Seed ne pomeni lokacije (indeksa v r ring bufferju), ampak le "definira" začetno pozicijo branja iz ring bufferja. To pomeni, da lahko vrednosti seeda, ki ležita blizu (npr. 1 in 2), definirata začetni poziciji v ring bufferju, ki sta "daleč" narazen.

Randomness ::

To si res zanemaril, pa ne samo to, zanemaril si še nekaj. Izbira tretjega števila je odvisna od prvih dveh, in tako naprej.

Recimo da sta prvi dve števili:

enaki: 100 100, v tem primeru je možnih vrednosti za tretje število še vedno dvakrat interval
za d različni: 100, 100+d, potem je možnih vrednosti samo še za en interval

vmes pa neka interpolacija.

Od kje pa tole? Izbira tretjega števila pač ni odvisna od prvih dveh.

Randomness ::

moose_man je izjavil:

Em, nočem bit tečen, ampak a bi lahko bla tale tema posvečena diagnozi mojega problema in ne za računanje verjetnosti, prosim? Izračuni, ki jih delam na praksi te dni, so vezani na ene programčke, ki sem jih naredil že nekoč prej in res mi ni do tega, da bi moral kopat po njih in nadomeščat rand() s čim drugim. :(

Saj smo ti že svetovali; Preveri verzije knjižnice, v kateri se skriva implementacija rand, ki jo uporabljaš (mislim, da gre v tvojem primeru za msvcrt). Poskusi prevesti v debug in release načinu in primerjaj. Isto verzijo gcc-ja in po možnosti msvcrt-ja instaliraj še na kak drug računalnik (mogoče v navidezni stroj). In tako naprej ...

technolog ::

Em, nočem bit tečen, ampak a bi lahko bla tale tema posvečena diagnozi mojega problema in ne za računanje verjetnosti, prosim?


Potok, tvoj originalni problem smo rešil, sedaj rešujemo že ta drugega. In ravno z verjetnostjo sem ti dokazal, da se nimaš kaj sekirat glede orignalnega.

Daj si z neta potegni neko spodobno rand() implementacijo, sem ti že povedal, da to ni kul, da je tako, kot ti program deluje. Seveda je določen procent šanse, da nas vesolje vleče za nos, in smo mel samo grozno nesrečo, da ti vsak primer deluje tako slabo.

@Randomness: Seveda je pomembno. Recimo, da je N=10, n=3, d=3.

Če sta prvi dve števili 5, 6, so za tretje število možnosti: 3,4,5,6,7,8 da bodo števila za največ 3 narazen.
Če sta prvi dve števili 5, 7, so za tretje število možnosti: 4,5,6,7,8, se pravi brez 3, ker

3,5,7 se za 4 razlikujejo.

Zgodovina sprememb…

Randomness ::

@technolog: Ja seveda, ampak "trik" je v tem, da ti sešteješ vse te možnosti, ki si jih naštel. Malo razmisli, pa boš videl, da ti prvo izžrebano število definira interval za vsa ostala žrebanja in stvar postane trivialna.

technolog ::

Nope, ni res. Prvo žrebanje ti ne definira intervala.

Če je prvo število izžrebano recimo 10, potem so veljavni intervali [7,10], [8,11], [9,12], [10, 13] (štirje, ne en). Kateri izmed teh je finalni, pa ti lahko določi katera koli od naslednjih števil. Lahko že prva pade 13, potem že ona fiksira interval za vse ostale. Če pa pade recimo 12, pa ostaneta še [9,12] in [10,13], da ju fiksira bodisi prihodnja 13 ali pa 9.

Če ne verjameš, naredi računalniško simulacijo, da se izogneš problemom s robovoma intervala, pa postavi prvo število nekam na sredino.

Se pa strinjam, da je problem zelo zanimiv. Zato ga dajva predelat v ekvivalentno obliko.

Izžrebamo n števil iz intervala [0,1]. Kolikšna je verjetnost, da bodo ležali na intervalu z močjo L, 0 <= L <= 1.

Zgodovina sprememb…

Randomness ::

Res je, tukaj se strinjam s tabo. Problem je bil že od začetka preveč ohlapno definiran. Jaz sem se osredotočil v resnici na podproblem, ko morata biti drugi dve števili večji od prvega (v tvojem primeru je to interval [10,13]).

technolog ::

Ja, jaz sem ga zastopil kot:

žrebamo n celih števil na nekem intervalu. Koliknša je verjetnost, da se nobeni dve ne bosta razlikovali za več kot d. (to implicira, da je pokritje z intervalom dolgo največ d).

Ti imaš pa neko svojo različico, dokaj pametno sicer, s čemer si naredil dogodke neodvisne, da lahko enostavno množiš. V mojem primeru ne moreš. Če je padla prej 9, potem 13ka ne sme.

Zgodovina sprememb…

Randomness ::

technolog je izjavil:

Se pa strinjam, da je problem zelo zanimiv. Zato ga dajva predelat v ekvivalentno obliko.

Izžrebamo n števil iz intervala [0,1]. Kolikšna je verjetnost, da bodo ležali na intervalu z močjo L, 0 <= L <= 1.

Postavlja se mi vprašanje: je problem analitično rešljiv? Domnevam, da je - gre sicer za n-terni integral.

Zgodovina sprememb…

MaFijec ::

Če rabiš nekaj, nad čemer boš imel kontrolo, je nalažje, da implementiraš varianto
Mersenne twisterja.
Kar nekaj literature najdeš na Wikipediji in na tej
strani.

Na voljo je tudi že množica implementacij v različnih programskih jezikih.

Drugače pa je to dobro znan problem:
beri

Mislim, da se temu reče "zero-excess initial state recovery."
Najbrž pa se implementacija randoma razlikuje med sistemi, kjer stvari preizkusaš. Čeprav misliš, da bi morala biti ista.

technolog ::

Jaz se tud sprašujem, sploh ker nama še meje nagajajo. Sicer se včasih da zelo lepo poenostavit tud n-terne integrale v nekaj, kar je dejansko izračunljivo.

Ampak tukaj so posamezna žrebanja odvisni dogodki, tako da dvomim.

Randomness ::

@Potok: Problem vidim v dveh stvareh: a) slaba implementacija random generatora; b) majhen razpon generiranih števil (RAND_MAX je v tvojem primeru le 2^15-1; nisem prepričan, da je tako na vseh 32-bitnih sistemih; ne vidim razloga, zakaj ni tudi na 32-bitnih sistemih 2^32-1). Skratka, najdi (glej predloge ostalih) boljšo implementacijo naključnega generatorja - za kake bolj resne stvari je to itak samo po sebi umevno.

Edit: vidim, da je že MaFijec ponudil boljši odgovor.

Zgodovina sprememb…

Smurf ::

Glede na link od MaFijca bi rekel, da gre ravno za to kar sem omenil jaz. Slab generator, ki daje ob podobnem seedu podoben rezultat.

Ce se obrnem na enega izmed komentarjev:

rand() function in VS2008 returns this: return ((current_value = current_value * 214013 + 2531011) >> 16) & 0x7fff;. This current_value you set with srand. This function is such that it will return similar pseudo random numbers for similar seeds, and there is no help about it. The problem is that those bits that are the most random in first call are eaten up with >> 16 part.


Verjetno gre za kaj podobnega tudi v primeru OP. Za popolno razjasnitev pa bi moral OP pastati kodo njegove rand funkcije. Pri tej definiciji je tudi prvotna cifra=seedu kot sem na zacetku trdil jaz (so pa verjetno v novejsih in popravljenih funkcijah spremenili v nekaj takega kot omenja @Randomness).

@OP: Najdi rand f-jo in jo nam nalimi pa bo verjetno resen problem.

moose_man ::

Hvala za odgovore.

Smurf je izjavil:

G
@OP: Najdi rand f-jo in jo nam nalimi pa bo verjetno resen problem.


Gre za rand() funkcijo, definirano v stdlib.h. Kaj naj bi točno nalepil?

Zgodovina sprememb…

  • spremenilo: moose_man ()

technolog ::

To, kar smo ti že vsi trije predlagali. Napiši / prekopiraj / začaraj funkcijo rand2() in jo kliči namesto rand().

ERGY ::

Zgodovina sprememb…

  • spremenilo: ERGY ()

Smurf ::

@Potok
Ja, moral bi najti source od stdlib (stdlib.c).

Z malo googlanja sem nasel stdlib.c, verjetno je tudi pri tebi tako.

void srand(unsigned int seed) {
  holdrand = (long) seed;
}

int rand() {
  return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}


Se pravi se enkrat odgovor.

1.) Zakaj dobis tak rezulatat:
Podoben seed bo dal prvi podoben rezultat (zaradi shiftanja 16 bitov). Na drugem racunalniku pa imas verjetno novejso razlicico randoma, zaradi cesar dela bolje.

2.) Kako popraviti kodo za tvoj specificen problem:
Uporabi boljsi random. Ali bos napisal funkcijo, ali pa uporabil ze obstojeco knjiznico je tvoja izbira, predloge za eno in drugo imas zgoraj.

fireice ::

Ce gre za kaksno zadevo, kjer je kljucen dober random, bi se jaz izogibal rand() na dalec. Drugace pa samo parkrat klici rand(), preden zacnes uporabljati vrnjene vrednosti.

Vsekakor pa predlagam, da si malo pogledas C++11 random knjiznjico, ki je res enostavna za uporabo. Plus, imas ze definirane razne distribucije.

Recimo:

http://en.cppreference.com/w/cpp/numeri...
http://www.hongliangjie.com/2011/09/16/...


Vredno ogleda ...

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

[C++] Generiranje naključnih števil tipa double

Oddelek: Programiranje
81738 (1647) mn
»

C++

Oddelek: Programiranje
121190 (926) BALAST
»

[C] Random funkcija

Oddelek: Programiranje
92211 (2042) primozsu
»

[C] random do poljubne številke

Oddelek: Programiranje
172078 (1745) napsy
»

srand in program v Cju???

Oddelek: Programiranje
131516 (1386) nuclear

Več podobnih tem