Kirjautuminen

Haku

Tehtävät

Keskustelu: Koodit näytille: C: Teho-random

Sivu 1 / 1

Sivun loppuun

JoinTuanJanohon [17.11.2005 15:50:42]

#

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 */
}

msdos464 [25.11.2005 22:18:18]

#

Aivan loistava :o

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

FooBat [26.11.2005 23:03:03]

#

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;
}

JoinTuanJanohon [27.11.2005 14:42:26]

#

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));
   }
}

jutti [12.01.2006 11:30:57]

#

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.

phadej [12.04.2006 23:28:46]

#

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

Newb [17.02.2007 20:47:32]

#

int RandNumber {
Return 3;
}

<3

Metabolix [24.01.2008 18:31:22]

#

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

Metabolix [11.06.2019 12:19:06]

#

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 }
*/

Grez [11.06.2019 13:06:06]

#

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

jone2712 [11.06.2019 22:28:40]

#

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.

Grez [12.06.2019 10:59:28]

#

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.

jone2712 [29.06.2019 16:01:49]

#

// Päivitys JoinTuanJanohon rnd-funktioon. Funktio on nyt
// 64-bittinen.

#include <math.h>
#include <stdio.h>

// Määritellään uint64 64-bittiseksi etumerkittömäksi luvuksi.
// Jos kääntäjäsi on 64-bittinen, sitten riittää määrittely:
// typedef unsigned uint64;
typedef unsigned __int64 uint64;

// Loogiset totuusarvot.
#define TRUE 1
#define FALSE 0

// alkuluku-funktion ohjausparametrit.
#define INC 3
#define UUSI 7
#define JATKO 9

// rnd64-luokka arpoo 64-bittisen random-luvun aina, kun
// kutsutaan rnd64-luokan rnd-funktiota.
class rnd64
{
   public:

   rnd64(void);
   ~rnd64(void);
   uint64 rnd(void);

   private:

   int alkuluku(int);
   uint64 next(void);

   int status;
   uint64 dx;
   uint64 dy;
   uint64 end;
   uint64 x, y;
   uint64 R16A;
   uint64 R16B;
   uint64 lisaysA;
   uint64 lisaysB;
   uint64 Z[2], W;
};

// Asetetaan alkuarvot, jotka ovat samantyyppiset kuin
// JoinTuanJanohon alkuperäisessä rnd-funktiossa.
rnd64::rnd64(void)
{
   dx=0xfedca201L;
   dy=0x012357bfL;
   R16A=(uint64)1;
   R16B=(uint64)2;
   x=5; y=3; end=2;
   Z[0]=Z[1]=0; W=0x00;
   lisaysA=0x012357bfL;
   lisaysB=0xfedca201L;
}

rnd64::~rnd64(void)
{
}

// Jokaisella rnd-funktion kutsulla kokeillaan nopeasti yhdellä
// askeleella, onko nykyinen x alkuluku vai ei. Ellei x ole alkuluku,
// funktio alkaa etsimään uutta alkulukua (INC) kaksi askelta suuremmalla
// luvulla, muutoin jatkaa nykyisen x:n tutkimista.
int rnd64::alkuluku(int st)
{
   if (st == INC)
   {
      x+=2; y=3;
      if (x>=(1<<16)) x=5;
      end=unsigned(sqrt(double(x)+0.25));
      return JATKO;
   }
   else
   {
      if (!(x%y)) return FALSE;
      if ((y+=2)>end) return TRUE;
      return JATKO;
   }
}

// uabs-funktio palauttaa itseisarvon.
inline uint64 uabs(uint64 &a, uint64 &b)
{
   return a>b? a-b: b-a;
}

// Vaihdetaan muuttujien arvot.
inline void swap(uint64 &a, uint64 &b)
{
   uint64 c=a; a=b; b=c;
}

// next-funktio palauttaa seuraavan satunnaisluvun. Funktio on
// olion private-osassa, joten funktiota ei voi kutsua muualta
// kuin olion sisäisellä funktiolla.
uint64 rnd64::next(void)
{
   status=alkuluku(UUSI);
   if (status == TRUE)
   {
      lisaysB-=lisaysA;
      lisaysA+=x;
      alkuluku(INC);
   }
   else if (status == FALSE)
   {
      alkuluku(INC);
   }

   R16A -= lisaysA; lisaysA-=dx;
   R16B += lisaysB; lisaysB+=dy;

   if (status==TRUE)
   swap(R16A, R16B);

   R16A += (R16A>>32)^(R16B<<32);
   R16B -= (R16A<<32)^(R16B>>32);

   return R16A^R16B;
}

// Aina silloin, kun status on TRUE, rnd-funktio yrittää tasata parittomien
// ja parillisten lukujen määrää (kaaottisesti). Korjaus on vain deltan
// suuruinen - eli hyvin pieni, eikä tasausyritys välttämättä edes onnistu,
// jolloin tasausyritys ei vaikuta satunnaislukujen jakaumaan.
uint64 rnd64::rnd(void)
{
   uint64 p1=next();
   if (status==TRUE)
   {
      uint64 a[2], b[2];
      uint64 p2=next();
      a[0]=b[0] = Z[0];
      a[1]=b[1] = Z[1];
      ++a[unsigned(p1%2)];
      ++b[unsigned(p2%2)];
      uint64 A=uabs(a[0], a[1]);
      uint64 B=uabs(b[0], b[1]);

      if (Z[0] == Z[1])
      {
         if (unsigned(next()%2))
         {
            A=1; B=0;
         }
         else
         {
            A=0; B=1;
         }
      }

      if (A < B)
      {
         ++Z[unsigned(p1%2)];
         return p1;
      }
      else
      {
         ++Z[unsigned(p2%2)];
         return p2;
      }
   }
   else
   {
      ++Z[unsigned(p1%2)];
      return p1;
   }
}

// Testifunktio, miten parillisten ja parittomien lukujen tila vaihtuu.
void main(void)
{
   rnd64 R;
   int st=0;
   uint64 bit[2];
   bit[0]=bit[1]=0x00;

   for (;;)
   {
      uint64 P=R.rnd();
      ++bit[unsigned(P%2)];
      if (st==0 && bit[1]>bit[0])
      {
         printf("%d", bit[0]>bit[1]? 1: 0);
         st=1;
      }
      else if (st==1 && bit[0]>bit[1])
      {
         printf("%d", bit[0]>bit[1]? 1: 0);
         st=0;
      }
   }
}

HannuTapio [29.06.2019 20:02:03]

#

Hei,

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

Koodit poistettu.

Grez [29.06.2019 20:16:05]

#

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

Metabolix [29.06.2019 23:46:33]

#

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

jone2712 [30.06.2019 00:18:00]

#

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.

0xffffffff [30.06.2019 12:07:04]

#

Newb kirjoitti:

int RandNumber {
Return 3;
}

<3

Tulee mieleen Doomin satunnaislukugeneraattori.

vesikuusi [30.06.2019 12:07:04]

#

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?

jone2712 [30.06.2019 15:22:55]

#

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;
}

Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta