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

[gugoXX]

Si puo' utilizzare un generatore pseudocasuale, come un LCG
http://en.wikipedia.org/wiki/Linear_...tial_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

[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]

Originariamente inviato da gugoXX

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]

Originariamente inviato da fero86

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

[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]

Originariamente inviato da gugoXX

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/Generat..._congruenziale

[gugoXX]

Originariamente inviato da Antonio23

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]

Originariamente inviato da Antonio23

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]

Originariamente inviato da Antonio23

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]

Originariamente inviato da gugoXX

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]

Originariamente inviato da Ikon O'Cluster

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]

Originariamente inviato da Antonio23

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?
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" ) 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?