Random numbers

[jtillnes]

Er det mulig å lage en helt random generator i c/c++?

 

jeg har prøvd dette:

 

int test;

srand(time(0));

test = rand();

cout << test;

 

JEg har altså brukt klokka til en random seed... men når jeg kjører

programmet får jeg f.eks. 33133... så avslutter jeg programmet og kjører det igjen og får 33153... Jeg gjør det igjen og får 33173 osv...

 

Skjønner dere problemet mitt? Det blir liksom ikke helt random når resultatet bare øker med 20 hver gang....

 

Det jeg vil ha er å ha et nytt random nummer mellom 1 og 100 skrives opp på skjermen hvert sekund (ikke i stigende rekkefølge!). Eks: 56 12 39 81 9 osv...

 

Dette er utrolig enkelt å få til i Visual Basic f.eks... Nekter å tro at det er umulig i c++.

 

PS! Jeg lager kun console-programmer foreløpig, så ingen GUI-løsninger ønskes enda takk!

 

JT

[daysleper]

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

using namespace std;

int main()
{
int test;
srand(time(0));
test = rand();
cout << test << endl;
return(0);
}

 

 

lars@blackbox tests $ ./test3

528763107

lars@blackbox tests $ ./test3

1677840852

lars@blackbox tests $ ./test3

769260778

lars@blackbox tests $ ./test3

2014242563

lars@blackbox tests $ ./test3

21232793

lars@blackbox tests $ ./test3

951449038

lars@blackbox tests $ ./test3

809094422

lars@blackbox tests $

 

 

...ser da ut til å bli tilfeldig her; åssen plattform (OS) kjører du det her på?

[daysleper]

..og videre kan du jo legge dette i en fil random.hh f.eks.:

 

#ifndef _OXYMORA_RANDOM_HH_
#define _OXYMORA_RANDOM_HH_

#include <cstdlib> // eventuellt stdlib.h, for rand()
#include <time.h>

namespace Oxymora {

template<typename T>
class Random
{
public:
 Random(T min_, T max_)
 	:_min(min_),
   _max(max_)
 {
 	srand(time(0));
 	_delta = RAND_MAX / (_max - _min);
 }
 
 T operator()(T min_, T max_)
 {
 	_min = min_;
 	_max = max_;
 	_delta = RAND_MAX / (_max - _min);
 	return(operator()());
 }
 
 T operator()()
 {
 	return((rand() / _delta) + _min);  	
 }
 
private:
 T _min, _max;	
 T _delta;
}; // class Random

} // namespace Oxymora

#endif //#define _OXYMORA_RANDOM_HH_

 

..og lage en test.cpp fil der du bruker klassen Random slik:

 

#include "random.hh"
#include <iostream>

using namespace Oxymora;
using namespace std;


int main()
{
Random<float> randFloat(-10, -20);

cerr << "5 tilfeldige flytetall mellom -10 og -20: ";
for(int i = 0; i < 5; i++) {
 cerr <<  fixed << randFloat() << " ";
}
cerr << endl;


randFloat(-100, 100);

cerr << "5 tilfeldige flytetall mellom -100 og 100: ";
for(int i = 0; i < 5; i++) {
 cerr <<  fixed << randFloat() << " ";
}
cerr << endl;


Random<int> randInt(20000, 10000);

cerr << "5 tilfeldige heltall mellom 20000 og 10000: ";
for(int i = 0; i < 5; i++) {
 cerr <<  fixed << randInt() << " ";
}
cerr << endl;

randInt(-10, 10);

cerr << "5 tilfeldige heltall mellom -10 og 10: ";
for(int i = 0; i < 5; i++) {
 cerr <<  fixed << randInt() << " ";
}
cerr << endl;

return(0);
}

[gspr]

For øvrig er spørsmålet "Random numbers, en umulighet?" et ganske interessant et. Datamaskiner kan i seg selv ikke generere helt tilfeldige tall. De er såkalte "pseudo-random" (rett på meg hvis jeg tar feil), dvs. de er omtrent tilfeldige, men ikke helt. Jo bedre tilfeldighet, jo bedre krypteringssystemer kan man utvikle.

I naturen finner vi svært tilfeldige hendelser, som kan høstes av datamaskiner hvis man trenger ekstremt god tilfeldighet. Et eksempel på dette er spontanfisjon av ustabile atomkjerner. En enkelt kjerne av et ustabilt atom vil på et tilfeldig tidspunkt fisjoneres. Problemet er bare at man som oftest har "litt flere" enn bare én kjerne, og at man dermed kan forutse når det i stoffet man har, statistisk sett, vil skje en eller annen fisjon.

Kvantefysikk er et område man ser på for komplett tilfeldighet.

Nå babler jeg, husker ikke hva tråden handlet om engang.

[daysleper]

Tilfeldige tall *er* interssant ja.

 

Er naturen, alt i hele universet; datamaskinen også, egentlig noen gang tilfeldig eller er det bare vi eller en maskin vi har laget, som ikke "ser" det på riktig måte eller oppdager systemet i det vi ser? Er universet diskret/digitalt og kan derfor da representeres ved hjelp av regler eller programmer? Eller er det analog og "ujevnt"?

 

Jeg tror ingenting er tilfeldig, altså sånn egentlig når vi ser nærme nok på det, og at alt derfor kan representeres digitalt.

 

Tenk på dette med cellular automata. Enkle regler som en ikke skulle tro genererte tilfeldigheter eller noe som helst, spruter ut intrikate, rekursive mønstre og andre ganger tilsynelatende tilfeldig støy.

 

Ta en titt på bildene, 30_* og 90_* (klikk på linkene i Rev. kollonnen):

http://scm.nostdal.net/cgi-bin/viewcvs.cgi/tests/tests/

 

Her er noen direkte linker til noen av bildene:

http://scm.nostdal.net/cgi-bin/viewcvs.cgi....viewcvs-markup

http://scm.nostdal.net/cgi-bin/viewcvs.cgi....viewcvs-markup

 

 

Koden ligger i cellular.cpp og programmet brukes slik:

./cellular 01011010

 

Der 01011010 er CA-regelen du vil den skal generere. Som du sikkert gjetter er regelen representert ved hjelp av 8 binære bits. Det finnes med andre ord 256 forskjellige regler her.

 

Juster konstantene PAUSE og WIDTH i koden!

 

Den fungerer slik at den for hver linje går fra kolonne til kolonne og tegner et tegn (#) eller space avhengig om om punktene ovenfor er tomme eller fyllt inn med tegn. Hvis vi tenker oss regel 90, så kan den representeres slik:

 

000

  0

 

001

  1

 

010

  0

 

011

  1

 

100

  1

 

101

  0

 

110

  1

 

111

  0

 

Når programmet kjøres byttes 0 ut med space, og 1 med tegnet #.

 

Den sjekker altså de tre punktene i kolonnene til linjen ovenfor og fyller inn 1 eller 0 i den aktuelle kollonen under ettersom hvordan regelen ovenfor matcher. Det er disse utrolig enkle reglene som danner det "avanserte" mønstret til regel 90!

 

Hvis du "snur" litt på regelen jeg siterer ovenfor ser du at den matcher det du sender som parameter når du kjører programmet; 01011010.

 

Noen interssange regler er:

- Regel 30: 00011110

- Regel 90: 01011010

- Regel 110: 01101110

 

Det er flere som mener at de noen ganger (tilsynelatende?) tilfeldige og andre ganger rekursive mønstrene vi ser i naturen er et resultat av lignende enkle regler. Programmet her genererer mønstre i 1 dimensjon, men man kan også bruke tilsvarende enkle regler for å generere mønstre i 2, 3 eller flere dimensjoner. Man kan tenkes at det hele "eksploderer" i et big bang og rare, men systematiske ting skjer. Man kan også tenke seg at dette representerer det som skjer "etter" big bang; at materie (atomer) "klumper" eller sammler seg, og legger seg i bestemte systematiske mønstre (snøkrystaller, is, planeter?).

 

Tenk hvis du bare så det som skjedde i kolonnen på f.eks. midten av bildet? Ville ikke det du så virket tilfeldig da? På samme måten som om man bare kunne se 4-ruter av et sjakk-brett om gangen. Universet er kanskje et sjakk-spill, og vi ser, foreløpig, bare 4-ruter av gangen; så visse ting virker tilfeldig.

 

Vi kan tenke oss vi bare ser en liten del av noe stort; vi tar en avis og river et hull i midten og plasserer avisen med hullet forran TV'n og det vi ser virker tilsynelatende totalt tilfeldig og uten noen form for system. Hadde vi sett hele bildet, altså hele sammspillet i universet; hadde ikke tilfeldigheter eksistert tror jeg.

 

Stephen Wolfram brukte CA i de tidlige versjonene av Mathematica for å generere tilfeldige tall. Igjen, snedig at det går; tilfeldigheter oppstår av enkle faste regler.

 

Det ideelle hadde forresten vært om konsollet hadde "evig" bredde. Dette at konsollet ikke har "evig" bredde skaper i visse tilfeller, eller for visse regler, problemer og "ødlegger" dem litt. Kunne laget en OpenGL-versjon i stedet med "zoom-funksjon" kanskje.

 

Finner masse info om cellular automata v.h.a. google, noe annet en kan søke på er "computable universes".

Ta også en titt her: http://en2.wikipedia.org/wiki/A_New_Kind_of_Science_(book)

[Vaughn]

Merk imidlertid at hvis du bruker Linux, kan du lese tilfeldige tall fra /dev/random - og disse er virkelig tilfeldige.

 

OSet bruker de nederste tre desimalene fra timingen på tastaturbruk, musbruk, harddiskavbrudd o.l. for å skaffe tilfeldige tall - mer tilfeldig blir det ikke uten å hashe brownske bevegelser eller noe.

 

Det er imidlertid begrenset forsyning; regn med at den begynner å blokkere etter lesing av et par hundre byte, i beste fall, inntil Linux har skaffet mer tilfeldige data. Er dette et problem vil /dec/urandom bytte til en PRNG når det blir nødvendig, men /dev/random blir fortsatt tømt - og programmer som SSHD og GnuPG er avhengig av denne. (= du kan ikke logge inn via SSH når /dev/random er tom!)

 

Disse tallkildene bør du imidlertid bare bruke dersom du virkelig *trenger* det, dvs. for kryptografi og lignende. PRNG-generatoren i glibc er svært god, og gir essensielt tilfeldige tall så lenge ingen *prøver* å forutsi den.

[gspr]

Daysleper: Utrolig fascinerende! Jeg er virkelig fascinert av slike fenomener, selv om jeg nok ikke har tilstrekkelige mattekunnskaper for å forstå det helt. Jeg også liker ideen om at alt i universet er fundamentalt enkelt, og at alt som er tilsynelatende komplekst og tilfeldig, kan brytes ned til mange langt enklere fenomener. *Tester programmet nå*.

 

Vaughn: /dev/urandom er et artig leketøy ja, men hvis det nå er slik daysleper nevner (at ingenting er tilfeldig, men at alt er fundamentalt enkelt - hvis jeg har forstått ham rett), så er jo menneskets handlinger (tastetrykk osv.) ikke tilfeldige, men et produkt av grunnleggende enkle fenomener som igjen danner vårt komplekse sinn.

[daysleper]

Kanskje jeg skulle skrevet en litt "off-beat" guide/artikkel på sourcecode.no om dette?

 

Synes slikt er utrolig interessant ja!

 

Edit: har forresten lagt til et par setninger til i posten ovenfor nuh..

 

Edit2:

Jeg har bestemt meg for å ta en pause med artikkel-skrivingen siden jeg har litt annet jeg må få unna først. Blandt annet en bok jeg -må- få lest ferdig, noe kode jeg må få pusset på, og så er det jul+nyttårsfeiringer straks også. Hadde uansett blitt en interessant artikkel tror jeg - så skal se om jeg får rota sammen noe tekst og noen stilige bilder+ muligens en OpenGL-versjon av koden litt siden!

[daysleper]

men et produkt av grunnleggende enkle fenomener som igjen danner vårt komplekse sinn

..og har vi da egentlig fri vilje?

 

Edit:

Nå snør det forresten ute her; snøkrystallene ligner utrolig på visse 3-dimensjonale Cellular Automata -bilder!

[gspr]

..og har vi da egentlig fri vilje?

Hva er da "fri" vilje? Vi kan jo tenke oss at "fri" er et høynivåkonsept som har liten eller ingen betydning på det elementære nivå.

Ang. artikkel: Ja, det hadde vært fett!

[daysleper]

10100101 var forresten også stilig!

 

Tester ut mange forskjellige her nå

 

Edit:

Ok -- skal kanskje prøve å se om jeg får til det her i OpenGL først. Da kan vi jo teste ut 2-dimensjonale og 3-dimensjonale CA også.

[gspr]

10100101 var forresten også stilig!

 

Tester ut mange forskjellige her nå

Ja, ligner på et strikkemønster til en sånn turistgenser.

01111110 ligner litt på 90'en, og er også stilig.

Endret 13. desember 2003 av gspr

[daysleper]

Vi kan jo tenke oss at "fri" er et høynivåkonsept som har liten eller ingen betydning på det elementære nivå.

 

..men så er jo alt som er "høynivå" i bunn og grunn egentlig basert eller representert av noe som er "lavnivå" eller elementært, tror jeg.

 

På samme måten som i forskjellige programmerings-språk; alt blir til slutt i bunn og grunn representert med 0 og 1.

 

Man kan (kanskje, mulig jeg roter her) sammenligne den enkle regelen med "lavnivå", og det kompliserte resultatet eller mønsteret med "høynivå".

 

 

Edit:

I CA'en som brukes her er også ting representert som 0 og 1; men man kan tenke seg at man har flere muligheter (0 til 9 f.eks.) og disse blir representert v.h.a. farger. Men ting er fortsatt "digitalt" eller diskret!

[gspr]

Vi kan jo tenke oss at "fri" er et høynivåkonsept som har liten eller ingen betydning på det elementære nivå.

 

..men så er jo alt som er "høynivå" i bunn og grunn egentlig basert eller representert av noe som er "lavnivå" eller elementært, tror jeg.

Ja, var litt uklar der. Begynner å bli trøtt.

Tror jeg tar kvelden nå, og leser videre om dette i morgen. Har i hvertfall satt hjernen min kraftig i spinn!!

[jtillnes]

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

using namespace std;

int main()
{
int test;
srand(time(0));
test = rand();
cout << test << endl;
return(0);
}

 

 

lars@blackbox tests $ ./test3

528763107

lars@blackbox tests $ ./test3

1677840852

lars@blackbox tests $ ./test3

769260778

lars@blackbox tests $ ./test3

2014242563

lars@blackbox tests $ ./test3

21232793

lars@blackbox tests $ ./test3

951449038

lars@blackbox tests $ ./test3

809094422

lars@blackbox tests $

 

 

...ser da ut til å bli tilfeldig her; åssen plattform (OS) kjører du det her på?

Dette var jo merkelig.. min kode er lik din, men får bare stigende verdier.. ikke random.. bruker Visual C++ på Windows 2000..... har ikke testet å kompilere med Borland.. men regner med samme resultat....

 

how strange... mer forskning må til...

 

fant forresten en bra side med noe random number classes som jeg kanskje kan bruke: http://www.robertnz.net/

 

JT

[daysleper]

jtillnes:

Tok å testet under Windows med MinGW-compileren, og da fikk jeg samme resultat som deg; ikke-tilfeldige tall.

 

Skulle tro dette var noe som fungerte uavhengig av plattform sånn egentlig.

 

Spørs om det blir til at du må bruke ekstere biblioteker da ja; det finnes mange på Internett og på http://www.sourceforge.net, blandt annet Blitz++ (hjemmeside).

 

..eller du kan jo altids skifte til Linux..

 

 

Edit:

Fannt ut noe! Det er bare det første tallet som ikke blir tilfeldig.

 

Test dette, og følg med på tallene etter det første ved hver kjøring:

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;


int main()
{
   srand(time(0));

   for (int i = 0; i < 5; i++)
       cout << rand() << endl;

   return 0;
}

 

Dette kan du løse ved å lage en klasse der du genererer det første (ikke tilfeldige tallet) i constructoren!

 

Altså random.hh fra posten ovenfor blir da slik:

 

#ifndef _OXYMORA_RANDOM_HH_
#define _OXYMORA_RANDOM_HH_

#include <cstdlib> // eventuellt stdlib.h, for rand()
#include <time.h>

namespace Oxymora {

template<typename T>
class Random
{
public:
Random(T min_, T max_)
 :_min(min_),
  _max(max_)
{
 srand(time(0));
  rand(); // ** Her altså **
 _delta = RAND_MAX / (_max - _min);
}

T operator()(T min_, T max_)
{
 _min = min_;
 _max = max_;
 _delta = RAND_MAX / (_max - _min);
 return(operator()());
}

T operator()()
{
 return((rand() / _delta) + _min);  
}

private:
T _min, _max;
T _delta;
}; // class Random

} // namespace Oxymora

#endif //#define _OXYMORA_RANDOM_HH_

 

 

Edit2:

Det er mulig det kan være lurt å kjøre rand() et par ganger, altså mer enn én gang i constructoren, for å øke "tilfeldigheten".

 

Edit3:

Tok å "ryddet opp i" koden og endret litt (rettet noen feil, og MSB er nå til venstre) på cellular.cpp for dere som er interesserte.

[daysleper]

Videre, relatert til dette med C.A.:

 

Ett annet, kanskje ennå snedigere fenomen oppstår hvis vi starter med tallet 1 og for hvert skritt multipliserer tallet med 3:

 

n->3n

 

1 * 3 = 3

3 * 3 = 9

9 * 3 = 27

27 * 3 = 81

81 * 3 = 243

243 * 3 = 729

...osv...

 

Hvis vi viser svarene vi får nedover i binærform i stedet for vanlig desimalform som ovenfor får vi også (hvis vi holder på en stund) et tilsynelatende tilfeldig system!

 

 

..ble ikke så bra dette bildet som de i linkene ovenfor, men hvis man holder på lenge nok blir det et tilsynelatende tilfeldig system eller mønster av det.

[gspr]

[kattemat]

http://www.lavarnd.org/

 

Noe av det mere interessante innen kost-effektiv random generering.

 

Ellers er det et _meget_ insteressant tema - både teknisk og filosofisk sett.