Keskustelu: Koodit: C: Teho-random

Satunnaislukujen generointi valmisfunktioilla saattaa joissain tapauksissa olla hidasta. Oheinen funktionpätkä hyödyntää yhden kellojakson bittisiirtoja satunnaislukujen generoimiseen. Jotta sykli rupeaisi toistamaan itseään, funktiokutsun saa toimittaa varovasti arvioiden kaksi potenssiin 32 potenssiin kaksi kertaa. Jos tehokas mööpeli generoisi satamiljoonaa lukua sekunnissa (omalla kannettavallani sadan miljoonan generoimiseen kuluu 1.6 sekuntia), siltikin syklin toistoa saisi odotella likimain 6000 vuotta.

int rnd(void)
{
   static unsigned long r1=1L; /* voi olla mikä tahansa alkuarvo */
   static unsigned long r2=2L; /* voi olla mikä tahansa alkuarvo */
   r1 -= 0x012357bfL; /* 16 bittiä sisältävä alkuluku */
   r2 += 0xfedca201L; /* 16 bittiä sisältävä alkuluku */
   r1 += (r1>>16)^(r2<<16); /* sekoitetaan */
   r2 -= (r1<<16)^(r2>>16); /* sekoitetaan */
   return (int)(r1^r2); /* kerran vielä kiellon päälle */
}

Aivan loistava :o

Pitää kyllä tehdä ohjelma joka tulostaa tuon tuottamia sarjoja :)

Ihan kiva idea, mutta normaaleista satunnaislukugeneraattoreista löytyvä tapa tuntuisi ainakin mun testeissä olevan paljon nopeampi ja tuottavan satunnaisempia lukuja.

unsigned int seed = 0;
int rnd() {
  const unsigned int offset = 12923; //joku alkuluku
  const unsigned int multiplier = 4079; //toinen alkuluku

  seed = seed * multiplier + offset;
  return seed;
}

Muuten hyvä, mutta funktio ei toimi käytännössä, ja pörrää vain yhdellä attraktorilla. Asia on helppo osoittaa graafisesti. Kokeile esimerkiksi seuraavanlaisella koodin pätkällä:

unsigned int seed = 0;
int rnd() {
  const unsigned int offset = 12923; //joku alkuluku
  const unsigned int multiplier = 4079; //toinen alkuluku

  seed = seed * multiplier + offset;
  return seed;
}

void RndTest(HWND hWnd)
{
   int x, y;
   HDC hdc=GetDC(hWnd);
   for (long i=0; i<10000000L; i++)
   {
      x=rnd()%getmaxx(); /* ikkunan leveys */
      y=rnd()%getmaxy(); /* ikkunan korkeus */
      SetPixel(hdc, x, y, RGB(255,255,255));
   }
}

Toinen tapa visualisoida satunnaisuutta on vähän kuin yllä, mutta kun on arvonnut xy-pisteen, lukee pisteen värin ja nostaa pisteen väriä pykälällä. Tähän malliin (allegron grafiikkafunktioita, mutta jokainen varmaan ymmärtää):

void Tayta(void)
{
   do
   {
      x=rand()%screen->w; /* ikkunan leveys */
      y=rand()%screen->h; /* ikkunan korkeus */
      vari = getpixel(screen, x, y);
      vari = vari & 255;
      vari++;
      putpixel(screen, x, y, makecol(vari, vari, vari));
   }
   while (vari < 255);
}

Ohjelma siis nostaa satunnaisesti joka pisteen harmaasävyä pykälällä, kunnes jokin piste saavuttaa tason 255. Olen käyttänyt tuota ja todennut, että gcc:n rand() tekee raidallista jälkeä. Ikään kuin pienimmät bitit eivät olisi kovin tasaisesti jakautuvia. Täytettävän ruudun kokoa kannattaa varioida. Jollain määrätyllä resoluutiolla raidallisuus ei näy, mutta jollain toisella se saattaa näkyä, jos satunnaislukugeneraattori ei ole tarpeeksi satunnainen.

njoo

rand()%100;
/* on eri kuin */
(double)rand()/RAND_MAX*100;

pilk.nus. ei se oo gcc:n rand vaa glibc:n rand ;)
toisaalta imo jos ei ole tekemässä jotain huippusalakirjotuskonetta niin glibc:n rand() antaa riittävän satunnaista jälkeä.

int RandNumber {
Return 3;
}

<3

Pitäisi olla teoriaa ja todellisia satunnaistestejä eikä vain omasta päästä kaivettuja kaavoja.

Viimeaikaisesta keskustelusta inspiroituneena tutkin hieman lisää tätä funktiota. Tekijähän väitti aikanaan toisessa keskustelussa, että ”teho-random poukkoilee kaoottisesti likimain 10 potenssiin 19 eri attraktorilla”, mitä sitten nämä selittäjän attraktorit tarkoittavatkaan. Koodin kuvauksessa myös väitetään, että sykli olisi ”kaksi potenssiin 32 potenssiin kaksi” eli 2^64, mikä olisi jo periaatteessa mahdollista mutta ei ole totta. (Vai tarkoittiko kirjoittaja 2^(32^2) eli 2^1024? Tämä olisi jo aivan absurdia.)

Koodi oli 32-bittiselle koneelle tarkoitettu tuohon aikaan, eli yksi long on 32-bittinen eikä nykyinen 64-bittinen. Näin ollen generaattorin koko tila on 64-bittinen.

Totuus syklin pituudesta on kaukana väitteestä. Funktiossa nimittäin alkaa (näillä alkuarvoilla) jo 44202814360 kierroksen jälkeen jakso, joka käsittää 183902521870 lukua. Tässä jaksossa esimerkiksi luvun viimeisenä bittinä on nolla 91951169495 kertaa ja ykkönen 91951352375 kertaa, eroa näillä siis 182880 ykkösten hyväksi. Eli ainakaan tämä funktio ei läpäise purkkaviritelmätestiä nollan ja ykkösen vaihtelusta vaan jää pian pysyvästi ykkösen puolelle.

Tässä on vielä testikoodi nykyaikaisella tietokoneella käytettäväksi. Koodi näyttää jakson alun ja lopun ja tilastot tuotettujen lukujen viimeisistä kolmesta bitistä.

#include <stdio.h>

struct R {
	unsigned int r1, r2; // Sisäinen tila.
	unsigned int value;  // Palautettava arvo.
	unsigned long n;     // Kierrosmäärä.
	unsigned long t[8];  // Tilasto, t[value % 8]++.
};

static R step(R a) {
	a.n += 1;
	a.r1 -= 0x012357bf;
	a.r2 += 0xfedca201;
	a.r1 += (a.r1 >> 16) ^ (a.r2 << 16);
	a.r2 -= (a.r1 << 16) ^ (a.r2 >> 16);
	a.value = a.r1 ^ a.r2;
	a.t[a.value % 8] += 1;
	return a;
}

int main(void) {
	unsigned long period_start = 44202814361L;
	unsigned long period_size = 183902521870L;
	R a = {1, 2};

	// Ajetaan generaattorin jakson alkuun asti.
	printf("[%12lu] = { %#010x, %#010x }\n", a.n, a.r1, a.r2);
	for (long m = period_start - 1; m--; a = step(a));
	printf("[%12lu] = { %#010x, %#010x }\n", a.n, a.r1, a.r2);

	// Tilastot rnd % 8.
	printf("pre-loop rnd % 8: { %lu, %lu, %lu, %lu, %lu, %lu, %lu, %lu }\n\n",
	a.t[0], a.t[1], a.t[2], a.t[3], a.t[4], a.t[5], a.t[6], a.t[7]);

	// Nollataan tilastot.
	a = (R){.r1 = a.r1, .r2 = a.r2, .n = a.n};

	// Ajetaan generaattorin jakso.
	a = step(a);
	printf("[%12lu] = { %#010x, %#010x }\n", a.n, a.r1, a.r2);

	for (long m = period_size - 1; m--; a = step(a));
	printf("[%12lu] = { %#010x, %#010x }\n", a.n, a.r1, a.r2);

	// Tilastot rnd % 8.
	printf("periodic rnd % 8: { %lu, %lu, %lu, %lu, %lu, %lu, %lu, %lu }\n\n",
	a.t[0], a.t[1], a.t[2], a.t[3], a.t[4], a.t[5], a.t[6], a.t[7]);

	// Näytetään, että lopuksi tulee sama tila kuin jakson alussa.
	a = step(a);
	printf("[%12lu] = { %#010x, %#010x }\n", a.n, a.r1, a.r2);
	return 0;
}

/*
t[0]                          = {        0x1,        0x2 }
t[44202814360]                = { 0x055a5e45, 0x48d15dff }
pre-loop rnd % 8 = {5525324342, 5525348828, 5525407077, 5525433466, 5525227437, 5525249165, 5525372289, 5525451756}

t[44202814361]                = { 0x04370abd, 0x3cf0b852 }
t[44202814361 + 183902521869] = { 0x055b5e44, 0x48d15dfe }
periodic rnd % 8 = {22987681150, 22987911446, 22987738857, 22987674359, 22987886927, 22987982821, 22987862561, 22987783749}

t[44202814361 + 183902521870] = { 0x04370abd, 0x3cf0b852 }
*/

Metabolix kirjoitti:

(Vai tarkoittiko kirjoittaja 2^(32^2) eli 2^1024? Tämä olisi jo aivan absurdia.)

Siinähän oli kerrottu että 100MHz taajuudella kestäisi 6000 vuotta, eli melko suoraan voi todeta että 2^64 oli luku jota tarkoitettiin.

Itseäni hieman huvittaa tuo "varovainen arvio". Kun tilatietoa on 64-bittiä niin teoreettinen maksimi syklin pituudelle juurikin se 2^64, niin miten tuo suurin teoreettinen voi olla varovainen arvio. Vähän kuin sanoisi että varovainen arvioni on, että elän 200 vuotiaaksi.

Sinänsä olisi mielenkiintoista tietää paljonko se sykli olisi, jos nuo longit olisikin 64-bittisiä.

Olen muokannut tuosta funktiosta 64-bittisen, ja siinä on sama ongelma, että jämähtää tiettyyn tilaan. Ts. ykköset ja nollat eivät ole tasaisesti jakautuneet.

Tuohon samaan ongelmaan sortuu myös kirjastosta käytetty valmis-random. Ei random-testini ole mikään purkkaviritelmä, vaan syntynyt ajan kanssa, kun olen randomeita tutkinut.

Kaikki vaatimukset ovat seuraavat:

a) Tutkittaessa esimerkiksi bittien 0 ja 1 esiintymistä, niiden välillä tila pitää vaihtua taajaan, eikä jämähtää jompaan kumpaan päiviksi.

b) Tutkittavat random-numerot ajetaan taulukkoon, ja toistoa ei saa tulla (1<<27) jaksolla.

c) Lopuksi graafinen tarkastelu. Näytölle pitää piirtyä random-mössöä. (Eilen esittämäsi testin a läpäisevä random ei läpäisisi testejä b ja c.

jone2712 kirjoitti:

Ei random-testini ole mikään purkkaviritelmä

Edelleen mielestäni jos olen ymmärtänyt a-testin oikein (eli kertoo onko arvoituissa luvuissa kulloinkin enemmän parillisia vai parittomia lukuja), on aidolla satunnaisuudella täysin mahdollista, että testi jämähtää pysyvästi tai pitkäksi aikaa nollaan tai ykköseen.

Mielestäni ei ole kovin hyvä satunnaisuustesti, jos aito satunnaisuus silloin tällöin antaa tuloksen että "huonoa satunnaisuutta"

Kaiken kaikkiaan testi, joka todella helposti antaa virheellisesti tiedon että "hyvää satunnaisuutta" ja lisäksi usein antaa virheellisesti tiedon että "huonoa satunnaisuutta" niin testi ei ole kovin hyödyllinen - varsinkin kun toimivampiakin testejä on olemassa.

Hei,

Minulla on minun lautapeliohjelmassa seuraava randomi, tämä on ihan oma :).

Koodit poistettu.

HannuTapio kirjoitti:

tämä on ihan oma :).

No siltä tosiaan näyttää, kasa turhaa paskaa.

Tavallaan olis ihan kiva tietää mitä olet tavoittellut tuolla (muuta kuin turhaa muistin kulutusta) mutta ehkä mielenterveyden kannalta parempi ettei kysy :D

jone2712 kirjoitti:

Päivitys JoinTuanJanohon rnd-funktioon. – class rnd64

Olisi jännä kuulla, millaisen ongelman nuo alkuluvut mielestäsi ratkaisevat.

Ehdottomasti plussaa olisi, jos koodi edes kääntyisi nykyaikaisella standardeja noudattavalla kääntäjällä eli olisi int main ja tietotyyppinä joko uint64_t (stdint.h-otsikosta) tai unsigned long long.

HannuTapio kirjoitti:

tämä on ihan oma :).

Ehdin nähdä koodin. Ei ole kovin satunnaista (eikä varsinkaan liity satunnaislukujen generointiin), että joukko satunnaislukuja ohjelmointikielen tavallisesta satunnaislukugeneraattorista tallennetaan taulukkoon ja samaa taulukkoa sitten toistetaan hieman eri järjestyksissä.

Alkuluvut tuovat random-funktioon kaoottisuutta. Saman asian ajaisi Fibonaccin lukujono, mutta ongelmana on, että se lukujono on kovin lyhyt.

Olen tutkinut pesudo-satunnaisten lukujen generointia pitkään, ja oheinen on kaikista vaihtoehdoista keskimäärin melko hyvä versio.

Käytän vielä tänäkin päivänä tosi vanhaa kääntäjää. BC5.02 on peräisi 90 luvulta. Kääntäjässä ei edes ole stdint.h-otsikkotiedostoa.

Olisin kyllä valmis siirtymään uudempaan kääntäjään, jos sellainen löytyisi. On vain niin köyhä, että lisensoitu hieno kääntäjä ei taida tulla kysymykseen.

Newb kirjoitti:

int RandNumber {
Return 3;
}

<3

Tulee mieleen Doomin satunnaislukugeneraattori.

jone2712 kirjoitti:

Olisin kyllä valmis siirtymään uudempaan kääntäjään, jos sellainen löytyisi. On vain niin köyhä, että lisensoitu hieno kääntäjä ei taida tulla kysymykseen.

Onko tässä nyt jotain mitä en tajua vai miksi GCC ei kelpaa?

Oheisella funktiolla voi testata, kuinka pitkiä sarjoja bitit tuottavat, pääsin nollan 45 perättäiseen sarjaan, kunnes sammutin testifunktion.

Koska perättäisen sarjan maksimi on suunnilleen ehkä 64 bittiä, alkulukujen käyttö rnd64-luokassa ei pitäisi vaikuttaa pseudosatunnaislukujen jakaumaan.

// Testifunktio, jolla voi tutkia, kuinka pitkissä sarjoissa bitit esiintyy.
int main(void)
{
   rnd64 R;
   int st=0;

   int lkm[2]={0, 0};
   int max[2]={0, 0};

   for (uint64 loop=1; loop; loop++)
   {
      int bit=int(R.rnd()%2);
      if (bit==st) ++lkm[st];
      else
      {
         if (lkm[!bit] > max[!bit])
         {
            max[!bit]=lkm[!bit];
            if ((!bit) == 0)
            {
               printf("bitti %d esiintyi %2d kertaa perakkain\n",
               !bit, max[!bit]);
            }
            else
            {
               printf("                                       ");
               printf("bitti %d esiintyi %2d kertaa perakkain\n",
               !bit, max[!bit]);
            }
         }
         lkm[0]=0;
         lkm[1]=0;
         st=bit;
      }
   }
   return 0;
}