Generare numero casuale

[xsatellitex]

Come si realizza una funzione che restituisce un numero casuale ?
Ovviamente senza utilizzare le funzioni gia belle e pronte.

Il linguaggio di programmazione non è importante, voglio solo capire il ragionamento :stordita:

[gugoXX]

Si puo' utilizzare un generatore pseudocasuale, come un LCG
http://en.wikipedia.org/wiki/Linear_congruential_generator

Oppure puoi basarti sul tempo di sistema se la risoluzione e' molto piu' alta del tuo campionamento e se il tuo campionamento non e' periodico.

Oppure buoi estrarre un UUID, praticamente presente su tutte le piattaforme di programmazione moderne (sotto le piattaforme Microsoft e' noto come GUID). Nella sua implementazione piu' comune l'algoritmo del UUID contiene una parte di cifratura di dati simile ad uno dei passi dell'LCD, e i tra i dati c'e' anche il tempo di sistema con risoluzione a 100 nanosecondi. In pratica metteresti insieme i due concetti.
Un UUID e' un numero a 16 byte. Ti bastera' calcolare il modulo di tale numero per il massimo del tuo range.
Quindi se il tuo massimo e' sensibilmente piu' basso di un numero a 16byte (e nella stragrande maggioranza dei casi e' cosi') e se il tuo campionamento non e' mai inferiore a 100ns (e nella maggioranza dei casi e' cosi'), allora questo metodo e' semplice e funzionale.

[xsatellitex]

Grazie penso che le combinerò tutte insieme :stordita:

[PGI-Bis]

Puoi anche mettere un microfono fuori dalla finestra e catturare il rumore di fondo. Non è crittogaficamente sicuro ma si riescono a tirar fuori delle belle sequenze. Il problema è che non sono ripetibili.

[Ikon O'Cluster]

Se vuoi saperne di più sulla generazione di sequenze pseudo casuali ti consiglio:

Menezes, van Oorschot, Vanstone - Handbook of applied cryptography

E' un ottimo libro free online della CRC Press. Si usa a livello universitario. Comunque il principio è quello di avere una fonte di "entropia". L'entropia è un concetto che torna in molte discipline ed è puramente astratto, cioè è un modo per dire "qualcosa che non esiste". In pratica il generatore di entropia pura genera bit 0 o 1 con probabilità 0.5. Esistono aggeggi che approssimano questo comportamento, generalmente ottenuto per mezzo di strumenti hardware o x mezzo di misurazioni quali il ritmo con cui batti tasti sulla tastiera, il rumore di un microfono, ecc... Oppure combinando tutte queste cose. A questo punto hai una sequenza molto "sicura", generalmente troppo sicura per i nostri semplici scopi, quindi si usa un generatore di numeri pseudocasuali (PRNG) che prende in ingresso una sequenza di N bit detta seme e ne produce una non periodica di M bit (dove M è molto più grande di N) detta pseudocasuale. Ovviamente gli M-N bit aggiunti sono calcolati in funzione degli N bit iniziali (quelli sicuri) secondo una formula (se lineare hai un generatore lineare). Ovviamente il prodotto di un generatore pseudocasuale sarà facilmente prevedibile in quanto avendo una sequenza finita in ingresso produrrà una sequenza infinita in uscita, che sarà infinita solo perchè ad un certo punto comincerà a ripetersi. Un generatore del genere è utile per scopi non crittografici: nel caso della crittografia non si può utilizzare perchè se qualcuno "registrasse" per molto tempo la sequenza arriverebbe a determinare il seme potendone prevedere il comportamento futuro!

[fero86]

Un UUID e' un numero a 16 byte. Ti bastera' calcolare il modulo di tale numero per il massimo del tuo range. supponiamo che un UUID sia crittograficamente sicuro; cosa ti fa pensare che lo sia anche il suo modulo N, per qualche N?
lo stesso vale per qualunque altra proprietá utile di un UUID, come la distribuzione uniforme (non so se ce l'hanno, dico per fare un esempio).
a questo punto seriamente tanto vale mettere il microfono fuori dalla finestra.

[gugoXX]

supponiamo che un UUID sia crittograficamente sicuro; cosa ti fa pensare che lo sia anche il suo modulo N, per qualche N?
lo stesso vale per qualunque altra proprietá utile di un UUID, come la distribuzione uniforme (non so se ce l'hanno, dico per fare un esempio).
a questo punto seriamente tanto vale mettere il microfono fuori dalla finestra.

Relativamente agli UUID Microsoft, ovvero i GUID, non servono tanto per la crittografia (sono addirittura sconsigliati, quindi il presupposto sarebbe errato), quanto piu' per la loro caratteristica di univocita' che li rende utili laddove si conti di creare identificativi univoci (Database, riferimenti, etc.)


V4 GUIDs use the later algorithm, which is a pseudo-random number. These have a "4" in the same position, for example {38a52be4-9352-453e-af97-5c3b448652f0}. More specifically, the 'data3' bit pattern would be 0001xxxxxxxxxxxx in the first case, and 0100xxxxxxxxxxxx in the second. Cryptanalysis of the WinAPI GUID generator shows that, since the sequence of V4 GUIDs is pseudo-random, given the initial state one can predict up to next 250 000 GUIDs returned by the function UuidCreate[1]. This is why GUIDs should not be used in cryptography, e. g., as random keys.

Per la natura dell'algoritmo usato quindi una sequenza di GUID e' una sequenza pseudo-casuale, avra' quindi anche la distribuzione uniforme, e andrebbe bene per quanto richiesto.

Diciamo che occorrerebbe anche dimostrare il teorema:
Sia Sn una successione di valori casuali, allora anche Sn%M (La successione dei valori in modulo M) e' una successione di valori casuali.
Lascio al lettore la facile dimostrazione
(Ho sempre sognato di poterlo dire...)

[Ikon O'Cluster]

Ma perché usare:

/dev/urandom
/dev/random

fa schifo? O non è su linux?

[xsatellitex]

intanto scarico anche il libro :stordita:

[Ikon O'Cluster]

xsatellitex ma nello specifico cosa devi fare? Questo aiuterebbe a capire che tipo di generatore ti serve.

[xsatellitex]

No volevo solo capire come vengono realizzati i generatori di numeri casuali che di solito si trovano come funzioni built-in in molti linguaggi di programmazione ;)

[Ikon O'Cluster]

Quelli che trovi, ad esempio in C/C++ sono generatori lineari congruenziali. Non li trovi nel libro che ti ho detto io, ma se cerchi su google si.

[fero86]

Diciamo che occorrerebbe anche dimostrare il teorema:
Sia Sn una successione di valori casuali, allora anche Sn%M (La successione dei valori in modulo M) e' una successione di valori casuali. 1. chiarisci "casuale";
2. i computers non memorizzano numeri arbitrariamente grandi, chiarisci l'intervallo dei suddetti valori;
3. perché la successione si chiama Sn? i valori sono in numero di n?


Lascio al lettore la facile dimostrazione
(Ho sempre sognato di poterlo dire...) meno sogni e piu fatti, cosi é troppo comodo; fuori la facile dimostrazione, e mi raccomando rigore, grazie :)

[Ikon O'Cluster]

Scusate la deformaziona ingegneristica... a cosa serve la dimostrazione??? Lasciatela ai matematici! :)

Cmq tanto per rispondere alla domanda iniziale :) Se vuoi sapere come fa ad esempio il C++ per generare numeri casuali basta che guardi:

http://it.wikipedia.org/wiki/Numeri_pseudo-casuali
http://it.wikipedia.org/wiki/Generatore_lineare_congruenziale

[gugoXX]

cmq per la dimostrazione che se dato il processo stocastico Sn anche Sn mod N sia stocastico a orecchio mi suona che sia così ma per la dimostrazione magari è meglio aspettare l'intervento di qualche matematico (ZioSilvio?) :)

PS processi stocastici "tempo discreto" naturalmente intendo...

Per la cronaca, tra le ipotesi serve anche che N<<Max(Sn)
Altrimenti ci possono essere irregolarita' nella distribuzione che farebbero preferire alcuni valori (quelli piu' bassi) rispetto ad altri.

[gugoXX]

questa non la sapevo :)

Immagina di avere il range casuale tra 0 e 10000, quindi con distribuzione uniforme dei valori.
E di svilupparla con modulo 9000

Ovviamente i valori 0-1000 capiteranno il doppio piu' frequenti di quello 1000-9000 (relativi ai valori originali compresi tra 9000-10000 che in modulo 9000 torneranno tra 0-1000), e quindi la distribuzione non sara' piu' uniforme e non avremo piu' una successione casuale.

Se invece la si siluppasse per esempio con modulo 11 (valore "a caso" non divisore del massimo del range di cui prima), allora e' pur sempre vero che alcuni valori, sempre i piu' bassi, sarebbero piu' frequenti, ma di una parte su 1000 circa.

Per la dimostrazione rigorosa lascio a fero86, cosi' magari pensando a qualcosa raddrizza le ultime 2 giornate che mi sembrano partite con il piede sbagliato.

[fero86]

http://en.wikipedia.org/wiki/Stochastic_process e allora?


una successione convergente per definizione non arriva a numeri arbitrariamente grande, ma è tale che oltre un certo indice qualsiasi differenza tra due valori della successione è minore di un epsilon piccolo a piacere mi sono perso la parte in cui veniva specificato che la successione é convergente.


n è solo un indice arbitrario per indicare una successione di valori "numerabile"... quindi i valori di Sn possono anche essere n+1?non credo.

[fero86]

Per la dimostrazione rigorosa lascio a fero86, dimostrazione di cosa a questo punto? che il teorema vale solo per i tuoi comodi valori di modulo?

[fero86]

Scusate la deformaziona ingegneristica... a cosa serve la dimostrazione??? Lasciatela ai matematici! :) vogliamo fare un programma funzionante, si o no?

se vuoi sapere cosa succede di fatto quando si usa l'operatore modulo a sproposito leggiti questo interessantissimo articolo:
http://www.hwupgrade.it/forum/showthread.php?t=1196677
paragrafo "Sequenze uniformemente distribuite in un intervallo assegnato".

[fero86]

60 minuti. a parte gli scherzi, allora cosa? hai chiesto la definizione di processo stocastico... quella è... veramente ho chiesto tutt'altro: gugoXX ha proposto un suo teorema in cui un termine ("casuale") non viene chiarito. che qualitá deve avere uno di quei valori per essere casuale? deve non essere predicibile in base a qualche altro fattore? deve essere il risultato di una variabile aleatoria che ha una distribuzione ben precisa? io mica leggo nel pensiero degli altri.


nel problema che stai analizzando non si presentaranno successioni divergenti, i numeri casuali li genererai comunque all'interno di un intervallo chiuso, quindi ci sarà un limite superiore... quale intervallo? vogliamo specificare? altrimenti il povero lettore continuerá per mesi a cercare la "facile" dimostrazione. comunque ormai é giá stato specificato qualche post fa.


anzi, a dire il vero, si possono avere anche successioni divergenti (ad esempio (-1)^n, se la memoria non mi inganna), (-1)^n non é divergente, é indeterminata, ma non divaghiamo


quello che interessa a te è che siano limitate... e in base a cosa mi interessa? :rolleyes:
si richiedono un po' troppe interpretazioni per questo teorema, mi sembra un po' farlocco... tanto vale che affermi empiricamente qualcosa anch'io: direi di non usare sto modulo su di un GUID.


che vuol dire? sono numeri, possono essere tutti i numeri che ti pare... puoi anche definire una successione Sn = n+1... naturalmente diverge... ma non capisco dove vuoi andare a parare... mettiamo n=3 e scegliamo dei valori a caso (visto che sono "casuali" :asd: ) per una nostra S3 (3 scritto a pedice): {1, 2, 3, 4}; la successione {1, 2, 3, 4} contiene n+1=4 valori. va tutto bene?

[gugoXX]

veramente ho chiesto tutt'altro: gugoXX ha proposto un suo teorema in cui un termine ("casuale") non viene chiarito
Ma stai scherzando spero.
Non sono mica io che ha fatto una domanda in questo post.
Se leggi il primo vedrai come qualcun altro ha chiesto:
Come si realizza una funzione che restituisce un numero casuale ?
Quindi chiedi a lui la definizione di casuale o di cosa intende nella sua domanda, NON a me.
Io peraltro l'ho capito anche senza altre spiegazioni.

dimostrazione di cosa a questo punto? che il teorema vale solo per i tuoi comodi valori di modulo?

Comodi cosa? Mi hai visto scrivere un comodo valore?
Ho ben specificato << se riesci a trovarlo in mezzo al resto.
E sempre li' in mezzo alla fuffa troverai come l'algoritmo di costruzione dei GUID si comporta come un generatore pseudo-casuale.

Al posto di tante parole vogliamo scrivere qualcosa?

Presi 1.000.000 di GUID e un modulo di 1104 (valore come detto casuale non per forza divisore del range di partenza, che per i GUID e' una potenza di 2, 2^128)

Mi aspetterei come distribuzione risultato, se rispettata la casualita', parecchie qualita'.
La prima che mi viene in mente e' che il numero di occorrenze per ciascuno dei 1104 valori non si discosti troppo dalla media, che dovrebbe essere fra l'altro il piu' vicino possibile a 1.000.000/1104 = 905.79710144927536231884057971014

La distribuzione delle occorrenze di ciascun valore dovrebbe essere quanto piu' possibile simile a quella di una distribuzione casuale nota che possiamo prendere a riferimento.

Poi mi aspetterei che una qualsiasi sottosequenza di tali valori resti comunque casuale, ovvero che per qualunque di ciascuna di queste sottosequenze sufficientemente lunga le qualita' di prima restino soddisfatte.

PS: Se questo semplice test di casualita' non dovesse soddisfare, sono pronto ad implementarne un altro ragionevolmente non troppo complesso.

Ecco i risultati.

Riferimento da classe Random min:819 avg:905.797101449275 max:992
Riferimento da calcolo GUID min:812 avg:905.797101449275 max:1009
Test su sottosequenze.

Sottosequenza rif. casuale min:62 avg:90.5797101449275 max:120
Calcolo come da GUID, sseq0 min:64 avg:90.5797101449275 max:123
Calcolo come da GUID, sseq1 min:61 avg:90.5797101449275 max:124
Calcolo come da GUID, sseq2 min:65 avg:90.5797101449275 max:125
Calcolo come da GUID, sseq3 min:62 avg:90.5797101449275 max:132
Calcolo come da GUID, sseq4 min:61 avg:90.5797101449275 max:126
Calcolo come da GUID, sseq5 min:54 avg:90.5797101449275 max:123
Calcolo come da GUID, sseq6 min:59 avg:90.5797101449275 max:124
Calcolo come da GUID, sseq7 min:61 avg:90.5797101449275 max:143
Calcolo come da GUID, sseq8 min:64 avg:90.5797101449275 max:129
Calcolo come da GUID, sseq9 min:62 avg:90.5797101449275 max:126
Calcolo come da GUID, sseq10 min:61 avg:90.5797101449275 max:125
Calcolo come da GUID, sseq11 min:58 avg:90.5797101449275 max:124
Calcolo come da GUID, sseq12 min:58 avg:90.5797101449275 max:122
Calcolo come da GUID, sseq13 min:63 avg:90.5797101449275 max:124
Calcolo come da GUID, sseq14 min:61 avg:90.5797101449275 max:128
Calcolo come da GUID, sseq15 min:63 avg:90.5797101449275 max:119
Calcolo come da GUID, sseq16 min:66 avg:90.5797101449275 max:125
Calcolo come da GUID, sseq17 min:65 avg:90.5797101449275 max:121
Calcolo come da GUID, sseq18 min:63 avg:90.5797101449275 max:123
Calcolo come da GUID, sseq19 min:55 avg:90.5797101449275 max:125


E ora un po' di codice.

class Program
{
const int nvals = 1000000;
const uint module = 1104;

static void Main(string[] args)
{
Guid[] str = new Guid[nvals];
for (int t = 0; t < nvals; t++)
{
str[t] = Guid.NewGuid();
}
int[] cnv = str.GetDistrib(module);

int min = cnv.Min();
int max = cnv.Max();
double avg = cnv.Average();

// Test su casuale standard
int[] ccv = Extensor.GetDistrib(nvals, module);
int newmin = ccv.Min();
int newmax = ccv.Max();
double newavg = ccv.Average();

Console.WriteLine("Target media: {0}", (double)nvals / (double)module);
Console.WriteLine("Riferimento da classe Random min:{0} avg:{1} max:{2}", newmin, newavg, newmax);
Console.WriteLine("Riferimento da calcolo GUID min:{0} avg:{1} max:{2}", min, avg, max);

// Test su 20 sottosequenze casuali* di quella originale, lunghe 1/10
// * Casuale standard :)
int nvals2 = nvals / 10;
Guid[] newseq = new Guid[nvals2];

Console.WriteLine("Test su sottosequenze.");
int[] ccvsottos = Extensor.GetDistrib(nvals2, module);
int sottoseqrefmin = ccvsottos.Min();
int sottoseqrefmax = ccvsottos.Max();
double sottoseqrefavg = ccvsottos.Average();
Console.WriteLine();
Console.WriteLine("Sottosequenza rif. casuale min:{0} avg:{1} max:{2}", sottoseqrefmin, sottoseqrefavg, sottoseqrefmax);

Random rnd = new Random();
for (int u = 0; u < 20; u++)
{
for (int t = 0; t < nvals2; t++)
{
int nelem = rnd.Next(nvals);
newseq[t] = str[nelem];
}
int[] dist = newseq.GetDistrib(module);
int tmin = dist.Min();
int tmax = dist.Max();
double tavg = dist.Average();
Console.WriteLine("Calcolo come da GUID, sseq{3} min:{0} avg:{1} max:{2}", tmin, tavg, tmax, u);
}

Console.ReadKey();
}
}

public class Int128
{
public ulong LHi;
public ulong LLo;
public Int128(ulong lhi, ulong llo)
{
LHi = lhi;
LLo = llo;
}

public Int128(byte[] src)
{
string[] vals = src.Select(v => v.ToString("X2")).ToArray();
string HexNum = string.Join("", vals);
string HexNum1 = HexNum.Substring(0, 16);
string HexNum2 = HexNum.Substring(16);
ulong l1 = ulong.Parse(HexNum1, System.Globalization.NumberStyles.HexNumber);
ulong l2 = ulong.Parse(HexNum2, System.Globalization.NumberStyles.HexNumber);

LHi = l1;
LLo = l2;
}

private static ulong lmodule;
private static ulong i64MN;
public static void ModuleArithmInit(uint mod)
{
ulong i32 = ((ulong)1) << 32;
lmodule = (ulong)mod;
ulong i32MN = i32 % lmodule;
i64MN = (i32MN * i32MN) % lmodule;
}

public uint Module()
{
ulong lhim = LHi % lmodule;
ulong llom = LLo % lmodule;

ulong first = (lhim * i64MN) % lmodule;
ulong sec = (first + llom) % lmodule;

uint ret = (uint)sec;
return ret;
}
}

public static class Extensor
{
public static int[] GetDistrib(this Guid[] domain, uint module)
{
Int128.ModuleArithmInit(module);

int[] cnv = new int[module];
int nvals = domain.Length;
for (int u = 0; u < nvals; u++)
{
byte[] barr = domain[u].ToByteArray();
Int128 GD128 = new Int128(barr);

uint val = GD128.Module();
cnv[val]++;
}
return cnv;
}

public static int[] GetDistrib(int howmany, uint module)
{
Random nrnd = new Random();
int[] ccv = new int[module];
for (int t = 0; t < howmany; t++)
{
int val = nrnd.Next((int)module);
ccv[val]++;
}
return ccv;
}
}

vogliamo fare un programma funzionante, si o no?
Adesso vorrei vedere un tuo "Programma" funzionante o un qualsiasi modo a tuo piacere che dimostri come invece una sequenza di GUID modulo M
NON possa essere presa come generatore di valori casuali perche' non sufficientemente casuale
Ah, e mi raccomando rigore, grazie.

Io magari non ne sono capace, ma ai risultati ci arrivo lo stesso.
Tu invece ne sarai capace a questo punto penso.

[Ikon O'Cluster]

:eek: :eek: :eek: ma siete partiti dal GUID avete fatto un giro assurdo... adesso vedo che ci date giù col codice! Cosa ha un LCG che non va???

[PGI-Bis]

:eek: :eek: :eek: ma siete partiti dal GUID avete fatto un giro assurdo... adesso vedo che ci date giù col codice! Cosa ha un LCG che non va???

Ehhh, te se "junior", ancora non puoi capire. La cosa meravigliosa - veramente meravigliosa, è quasi un fenomeno sociologico - delle discussioni nella sezione programmazione è che a volte la più innocente delle domande nasconde le trame più feroci.

I thread li riconosci perchè già a pagina uno c'è qualche schermaglia, a pagina due iniziano le sfide ottocentesche a singolar tenzone ma è da pagina tre in poi che si fa il salto di qualità e lì arriviamo alla vera battaglia campale con trinceramenti, artiglieria e sangue a fiumi.

Sono veramente spettacolari. In un altro thread si discuteva dell'aspetto artistico della programmazione. Ebbene dopo averla negata mi sento ora di aderire a quella tesi: è l'arte della guerra! :D.

[Ikon O'Cluster]

Sono senza parole :eek: :D

[astorcas]

Per la cronaca, tra le ipotesi serve anche che N<<Max(Sn)
Altrimenti ci possono essere irregolarita' nella distribuzione che farebbero preferire alcuni valori (quelli piu' bassi) rispetto ad altri.

In teoria non credi che N dovrebbe "avvicinarsi" il più possibile a un divisore di Max(Sn) perchè i valori siano equamente distribuiti? Cioè credo che non sia necessario che N<<Max(Sn) (se N = Max(Sn) -1 ) la distribuzione continua ad essere "equa".

[gugoXX]

In teoria non credi che N dovrebbe "avvicinarsi" il più possibile a un divisore di Max(Sn) perchè i valori siano equamente distribuiti? Cioè credo che non sia necessario che N<<Max(Sn) (se N = Max(Sn) -1 ) la distribuzione continua ad essere "equa".

Diciamo che e' difficile che ilo modulo sia un divisore di Max(Sn), nel senso che il modulo viene dato poi a posteriori come input per la generazione.
Anzi, diciamo che e' "improbabile" che sia cosi'.

Se non si usa un divisore del massimo del domini originale, i valori piu' bassi sono preferiti rispetto agli altri.
Ma di quanto?

Se Max(Sn) e' il massimo originale e MOD e' il modulo,
allora i Max(sn) % MOD valori piu' bassi
avranno una frequenza di MOD/Max(Sn) occorrenze in piu'.

Ma volevo far notare come Max(Sn) per i GUID e' 2^128
e normalmente il range di uscita e' decisamente piu' basso.
Addirittura nella classe standard in C# puo' essere al piu' 2^32

Quindi per valori comunemente usati direi che si fa "alla peggio" un errore di una parte su
2^96, e possiamo dormire tranquilli.

Per chi avesse bisogno di piu' valori ricordo che l'uscita di un generatore casuale puo' essere preso come uno stream di bit casuali 0-1
Bastera' quindi prendere lo stream e tagliarlo dove serve. A questo punto il dominio di partenza si puo' estendere a piacere a 200, 2000, 1000000 di bit
Che e' come prendere 2 GUID (o semplicemente INT, se e quando come auspicabilmente e' si usa la classe Random standard) insieme oppure 3 GUID insieme oppure N GUID insieme e trattare ogni singolo insieme come valore casuale appartenente al dominio cosi' esteso.