Newsgroup: it.comp.lang.c
Titolo: funzioni random

ciao a tutti ragazzi
ho un problema:
per scuola stiamo facendo una versione di mastermind molto ridotta che
prevede l'utilizzo di numeri casuali per la combinazione vincente
la combinazione vincente deve essere compresa tra
1 --> 10
ed è un vettore di 5 elementi.
per fare ciò abbiamo utilizzato la funzione:
rand( );
contenuta in:
stdlib.h
il problema è che questa funzione non prevede la possibilità di inserimento
di limiti (in questo caso numeri compresi tra 1 e 10).
abbiamo provato a utilizzare la funzione
srand( );
che, da quello che diceva il mio prof, dovrebbe porre il limite massimo per
la funzione
rand( );
il punto è che mi segnala errore!
ora, potreste dirmi il nome di qualche funzione di numeri pseudo-casuali con
seme modificabile?
se no, pensate che sia utile creare una funzione per numeri pseudo-casuali?
grazie delle risposte

Per ottenere un numero casuale x tra 1 e 10 è sufficiente scrivere:
x = (rand () % 10) + 1;
La funzione rand restituisce un valore tra 0 e RAND_MAX, definito in
<stdlib.h> (ad es. per il Borland C++ è pari a 0x7FFF). La funzione srand ()
serve solo ad inizializzare il seme ad un valore predefinito. Scrivendo
srand ((unsigned) time (NULL));
potrai inizializzare il seme ad un valore che è imprevedibile a priori (il
tempo del sistema), così da avere una variabile più casuale che
pseudocasuale. Ciao
                                            Marchisio Stefano
P.S.: dì al tuo professore di utilizzare l'help in linea prima di parlare.

 pseudocasuale. Ciao
ok! infatti anche a me srand( ) mi sembrava una funzione per il seme ma...
il prof ha sempre ragione!


 non capisco cosa dovrei inserire qui' !!!
Scrivila e basta ^_^
Serve per casualizzare maggiormente la rand che altrimenti non è così
casuale come ci si aspetterebbe.
Ciao
Claudio

 ha scritto nel messaggio
news:fYFt8.3540$g04....@tornado.fastwebnet.it...

Si tratta semplicemente di un cast: la funzione srand richiede che le si
passi un unsigned int (ovvero un intero senza segno); poichè la funzione
time restituisce un tipo diverso (per la precisione un time_t) è necessario
castarlo al tipo richiesto da srand.
Ciao,
Cecco

Ovviamente il motivo dell'Unsigned te l'ha spiegato Francesco nel mex sotto.
Il motivo del perchè gli passi il risultato ti "time" invece che un numero è
presto detto:
radn è una funzione matematica per la generazione di numeri PSEUDOcasuali
sulla base di un cosiddetto "seme"
tale seme non fa altro che alterare il funzionamento della rand.
Se tu facessi un programma che genera numeri casuali con la rand ma con seme
fisso e lo lanciassi n volte otterresti sempre lo stesso risultato.
Allo scopo di casualizzare i numeri pseudocasuali, c'è la srand: tale
funzione prendendo un numero in ingresso modifica il seme della rand.
Ovviamente per ottenere la casualità maggiore possibile senza tafferugli
cosa si può utilizzare??
L'orologio di sistema :)
Primo è un orologio e per tanto è sempre diverso, secondo ogni pc ne ha uno
diverso, per cui la casualità è assicurata ;)
Ciao
Claudio

x = (rand () % 10) + 1;
Questo dovrebbe avere alcuni problemi, nel senso che la distribuzione
non e' uniforme e su alcune piattaforme meno casuale che su altre. Un
modo per avere risultati migliori e':
<CODE>
    float rndn = (double) rand() / RAND_MAX;
</CODE>
Questo e' piu' casuale dell'altro ed e' una distribuzione uniforme tra
0 e 1.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 0 e 1.
era questo che il prof voleva ottenere! un risultato da 0 a 1  che noi
avremmo poi moltiplicato * 9 e aggiunto 1!
grazie mox

avremmo poi moltiplicato * 9 e aggiunto 1!
Ho un dubbio pero', il numero va' da 0 a 1, se tu lo moltiplichi per 9
e aggiungi 1 otterrai numeri da 1 a 10... ma non c'e' anche una
probabilita' su RAND_MAX che tu ottenga un 11 (statisticamente prima o
poi rndn varra esattamente 1.0). Non c'e' alcun problema per lo 0.0
invece.
Bisorrebbe ancora controllare questo o migliorando il metodo per
generare i numeri a partire da rndn oppure filtrando il risultato di
quel metodo con un operazione di modulo per il max valore che volevo
ottenere +1 (questo rende di 1/RAND_MAX) piu' probabile il valore
minimo pero'.
((int)(rndn * 9) + 1)%11
Ci sono certamente modi migliori, ma ora come ora non mi vengono in
mente.


Mox, guarda che nel tuo modo non cambia mica tanto. La rand () genera
comunque sempre numeri pseudocasuali, quindi è inutile stare tanto a
dannarsi l'anima. Per ottenere un numero pseudocasuale compreso tra x e y
basta fare:
int value = x + (rand () % (x - y));
ed il gioco è fatto.
                                Marchisio Stefano

Scusate, ma nella mia risposta precedente ho scritto una fesseria e me ne
sono accorto solo adesso. Per ottenere un numero compreso tra x e y occorre
fare:
int value = x + (rand () % (y - x + 1));
Il termine rand () % (y - x + 1) dà numeri compresi tra 0 e (y - x),
sommando il termine x si ottengono numeri compresi tra x e y. Scusate ancora
il lapsus. Ciao
                                                            Marchisio
Stefano

ho capito tutto;
cmq il quesito era generare numeri csuali da 1 a 10!
dovresti fare il professore! ;)

 il lapsus. Ciao
quindi se io volessi numeri da 1 a 10:
rand () % (10 - 1 + 1)
giusto?

 che dicela la stessa cosa):
+++
mynum = rand() % mymax;
Questo potrebbe creare  problemi, visto che in  alcune implementazioni
i bit meno significativi sono "meno random" degli altri. Sarebbe
meglio scrivere:
mynum = (int) ((double)mymax * rand() / RAND_MAX);
+++
Oltre a questo se usi l'operatore di modulo non hai una distribuzione
uniforme, vuoil dire che hai numeri piu' probabili di altri.


grazie millee!!!

 uniforme, vuoil dire che hai numeri piu' probabili di altri.
Vero anche questo; se proprio si deve usare rand() sarebbe meglio adottare la
seconda espressione.
Un vecchio esempio è sempre valido: se rand() generasse numeri da 0 a 10 e tu
volessi ottenerli da 0 a 9 facendo rand()%10 otteresti lo 0 con probabilità
doppia rispetto ai numeri da 1 a 9.
Cristiano

grazieee!!!

"Cristiano" ha scritto
: > mynum = rand() % mymax;
: >
: > Questo potrebbe creare  problemi, visto che in  alcune implementazioni
: > i bit meno significativi sono "meno random" degli altri. Sarebbe
: > meglio scrivere:
: >
: > mynum = (int) ((double)mymax * rand() / RAND_MAX);
: > +++
:
: Vero. Se mymax fosse 2, usando il primo metodo con alcune implementazioni
di
: rand() potresti ottenere: 0, 1, 0, 1, 0, 1, ...
:
: > Oltre a questo se usi l'operatore di modulo non hai una distribuzione
: > uniforme, vuoil dire che hai numeri piu' probabili di altri.
:
: Vero anche questo; se proprio si deve usare rand() sarebbe meglio adottare
la
: seconda espressione.
: Un vecchio esempio è sempre valido: se rand() generasse numeri da 0 a 10 e
tu
: volessi ottenerli da 0 a 9 facendo rand()%10 otteresti lo 0 con
probabilità
: doppia rispetto ai numeri da 1 a 9.
:
Un nuovo esempio:
Se rand() generasse numeri da 0 a 10 e tu volessi ottenerli da 0 a 9
facendo (int) ((double)9 * rand() / RAND_MAX) otterresti lo 0 con
probabilita` doppia rispetto ai numeri da 1 a 9.
rand()
0      -> [0 * 9 / 10] = [0.0] = 0
1      -> [1 * 9 / 10] = [0.9] = 0
2      -> [2 * 9 / 10] = [1.8] = 1
3      -> [3 * 9 / 10] = [2.7] = 2
4      -> [4 * 9 / 10] = [3.6] = 3
5      -> [5 * 9 / 10] = [4.5] = 4
6      -> [6 * 9 / 10] = [5.4] = 5
7      -> [7 * 9 / 10] = [6.3] = 6
8      -> [8 * 9 / 10] = [7.2] = 7
9      -> [9 * 9 / 10] = [8.1] = 8
10     -> [10* 9 / 10] = [9.0] = 9
ciao
Massimo

probabilita` doppia rispetto ai numeri da 1 a 9.
Uhmm, perche' rand() dovrebbe generare numeri da 0 a 10?
Vuoi dire che se cerco di ottenere numeri molto vicini a RAND_MAX il
metodo a problemi?
Un semplice metodo per sisolverlo sta' nell'interpretare correttamente
quel: (double)rand() / RAND_MAX ignorando il caso rarissimo in cui
esce un 1.0, togli quello e la distribuzione e' "perfettamente"
uniforme (ovviamente stiamo parlando di numeri pseudocasuali, quindi
con questo metodo non potrai mai avere numeri veramente casuali).


 con questo metodo non potrai mai avere numeri veramente casuali).
La distribuzione è uniforme solo se il numero massimo che vuoi ottenere ha una
particolare relazione con RAND_MAX. Per esempio se RAND_MAX = 2^A e tu vuoi
ottenere un numero compreso tra 0 e 2^B (B<A) potresti semplicemente usare lo
scorrimento a destra; in questo caso la distribuzione non ne risentirebbe, ma
negli altri casi sì.
Io consiglierei (per molti validi motivi) di usare rand() sono nei compiti in
classe d'informatica e mai per altre applicazioni, ma considerando che molti si
arrabbiano quando dico male di rand(), preferisco non andare oltre... :-)
Cristiano

arrabbiano quando dico male di rand(), preferisco non andare oltre... :-)
Nessuno deve permettersi di dirlo se prima non ha sottoposto la rand()
al test del CHI QUADRO :)
Comunque per applicazioni reali dovresti trovare altri mezzi per avere
numeri random (ora come ora non so dirti esattamente quali). O se
lavori sotto linux almeno usare il dispositivo dev/random che dovrebbe
comportarsi meglio (sinceramente non so bene come, uno di sti giorni
mi informero' bene).


"Mox" ha scritto
: >Un nuovo esempio:
: >
: >Se rand() generasse numeri da 0 a 10 e tu volessi ottenerli da 0 a 9
: >facendo (int) ((double)9 * rand() / RAND_MAX) otterresti lo 0 con
: >probabilita` doppia rispetto ai numeri da 1 a 9.
:
: Uhmm, perche' rand() dovrebbe generare numeri da 0 a 10?
Io completavo il ragionamento di Cristiano. Mi sembrava che le formule
valessero indipendentemente dal valore di RAND_MAX, purche` >= N.
Per cui, perche` non dieci se N = 10?
(con N indico il numero di valori accettabili)
:
: Vuoi dire che se cerco di ottenere numeri molto vicini a RAND_MAX il
: metodo a problemi?
:
Certo, se N e` dell'ordine di grandezza di RAND_MAX, il problema diventa
evidente. Anche se e` presente ogni volta che RAND_MAX+1 non e` un multiplo
intero di N.
: Un semplice metodo per sisolverlo sta' nell'interpretare correttamente
: quel: (double)rand() / RAND_MAX ignorando il caso rarissimo in cui
: esce un 1.0, togli quello e la distribuzione e' "perfettamente"
: uniforme (ovviamente stiamo parlando di numeri pseudocasuali, quindi
: con questo metodo non potrai mai avere numeri veramente casuali).
:
No, usando modulo o proporzione la distribuzione e` perfettamente uniforme
se RAND_MAX+1 e` un multiplo intero di N. Se vuoi una distribuzione
"perfettamente" uniforme dovresti scartare alcuni valori restituiti da
rand(). Nota che comunque questo e` un problema trascurabile per
N molto piu` piccolo di RAND_MAX.
Comunque la formula "corretta", nel senso del rarissimo caso, e`:
(int)((double) N * rand() / (RAND_MAX + 1.0))
con il piu` uno punto zero.
ciao
Massimo

 mi informero' bene).
Più o meno è quello che ho sempre sostenuto. Ma inspiegabilmente molti
"programmatori" svogliati non l'hanno ancora capito; peggio per loro... :-)
Cristiano

 con il piu` uno punto zero.
Direi che non va bene nemmeno questa perché il problema della distribuzione non
uniforme persiste.
Per ottenere numeri da 0 a n-1 con una distribuzione *identica* a quella che
otterresti con rand() la ottieni in questo modo:
int RND(const int n)
{
 const int S=(RAND_MAX+1)/n,X=S*n;
 int x;
 if(X) { do x=rand(); while(x>=X); }
 else x=rand();
 return x/S; /* Appena più veloce di x%n */
}
Cristiano

"Cristiano" ha scritto
: >
: > Comunque la formula "corretta", nel senso del rarissimo caso, e`:
: >
: > (int)((double) N * rand() / (RAND_MAX + 1.0))
: >
: > con il piu` uno punto zero.
:
: Direi che non va bene nemmeno questa perché il problema della
distribuzione non
: uniforme persiste.
Ho scritto corretta tra virgolette perche` intendevo dire che correggeva
l'errore della versione senza il piu` uno, con la quale N-1 sarebbe uscito
solo nel rarissimo caso in cui rand() restituiva RAND_MAX.
:
: Per ottenere numeri da 0 a n-1 con una distribuzione *identica* a quella
che
: otterresti con rand() la ottieni in questo modo:
:
: int RND(const int n)
: {
:  const int S=(RAND_MAX+1)/n,X=S*n;
Ad occhio, io qui ci vedrei un %, cioe`
  const int S=(RAND_MAX+1)%n, X=S*n;
Infatti, se RAND_MAX fosse 999, per esempio, e n 10
avremmo S=100 e X = 1000 e quindi verrebbe eseguito
il ramo dell'if sbagliato.
:  int x;
:  if(X) { do x=rand(); while(x>=X); }
:  else x=rand();
:  return x/S; /* Appena piů veloce di x%n */
: }
:
: Cristiano
ciao
Massimo

"Massimo Valentini" ha scritto
: :
: : int RND(const int n)
: : {
: :  const int S=(RAND_MAX+1)/n,X=S*n;
:
: Ad occhio, io qui ci vedrei un %, cioe`
:
:   const int S=(RAND_MAX+1)%n, X=S*n;
:
: Infatti, se RAND_MAX fosse 999, per esempio, e n 10
: avremmo S=100 e X = 1000 e quindi verrebbe eseguito
: il ramo dell'if sbagliato.
:
: :  int x;
: :  if(X) { do x=rand(); while(x>=X); }
: :  else x=rand();
: :  return x/S; /* Appena più veloce di x%n */
: : }
: :
Il problema e` un altro. Ho provato a compilare la tua funzione con il gcc
e mi dava un warning in compilazione, mentre se la chiamavo entrava in un
loop infinito. Il punto e` che con la rand() del gcc RAND_MAX e` uguale a
INT_MAX per cui RAND_MAX+1 da un overflow e diventa negativo, e cosi` S e
X, e quindi quando esegue il ciclo do/while la condizione (x >= X) e`
sempre vera.
Per ovviare a cio` potresti usare gli unsigned, tipo:
int RND(const unsigned int n)
{
 const unsigned int S=(((unsigned int)RAND_MAX)+1)/n,X=S*n;
 int x;
 if(X) { do x=rand(); while(x>=X); }
 else x=rand();
 return x/S; /* Appena più veloce di x%n */
}
ciao
Massimo

 }
Infatti l'avevo scritta per rand() usato in BCB e VC++ in cui RAND_MAX è da 15 o
16 bit (questo è uno dei motivi per cui non bisogna usare rand(): non sai mai
con che aborto di funzione hai a che fare).
La versione qui sotto, invece, l'ho scritta per un generatore che ritorna numeri
da 0 a 2^32-1 (l'ottimo MT19937 è uno di questi):
// Ritorna un numero casuale da 0 ÷ n-1
unsigned long RND(const unsigned long n)
{
 const unsigned long S=4294967296./n,X=S*n;
 unsigned long x;
 if(X) { do x=MT19937(); while(x>=X); }
 else x=MT19937();
 return x/S; // Appena più veloce di x%n
}
Ciao
Cristiano

 avete indizi?
Certo! :-)
Questa è un'implementazione di un lagged Fibonacci prng (ULONG è unsigned long):
/* x[n] = x[n-460] + x[n-607]
   Periodo= 2^(s-1)*(2^607-1) = 1,14061015440555e192
*/
ULONG LAGrnd(void)
{
 static ULONG b[607]; static int i=0,flg=1;
 int j; ULONG rnd;
 if(flg) {
  flg=0;
  for(int j=0;j<607;j++) b[j]=RND();
 }
 if(i>=147) j=i-147; else j=i+460;
 rnd=b[i]=b[j]+b[i];
 if(i>=606) i=0; else i++;
 return rnd;
}
RND() serve per inizializzare il vettore dei numeri.
Non so cosa intendi per "efficiente", in ogni caso è un generatore abbastanza
veloce che occupa non molta memoria.
Tieni presente che i generatori che richiedono un'inizializzazione sono
"rischiosi" nel senso che per molti di essi questa inizializzazione deve essere
fatta rispettando precise regole, altrimenti il generatore rischia di degenerare
in una sequenza avente pessime proprietà statistiche (sarebbe quasi come
utilizzare rand).
Per fare un paragone, l'ottimo MT19937 (o suo valido fratello minore TT800) non
soffrono di questo inconveniente ed hanno caratteristiche superiori ad un lagged
Fibonacci.
Alcuni crittoanalisti hanno proposto la versione shrinking di questo generatore
(FISH) per sostituire i tre generatori a scorrimento (LFSR) usati nell'algoritmo
A5 di codifica del sistema telefonico GSM (ma senza successo... :-) ).
Cristiano

 writes:
  >> avete indizi?
  C> Certo! :-)
  C> Questa è un'implementazione di  un lagged Fibonacci prng (ULONG è
  C> unsigned long):
[...]
Qui  faccio finta  di non  aver letto  :-) cercavo  qual cosa  di piu`
teorico per poi cimentarmi nell'implementazione, e` li` che mi diverto
:-) (se tutto va bene).
  C> RND() serve per inizializzare il vettore dei numeri.  Non so cosa
  C> intendi per "efficiente", in ogni caso è un generatore abbastanza
  C> veloce che occupa non molta memoria.
per efficiente  intendevo un generatore  con una buona  casualita` nel
risultatato. piano piano scopro che i numeri di fibonacci sono come il
prezzemolo nella minestra in ogni cosa e mi incuriosiscono :-)
grazie,


 Cristiano
ps: scusa per le domande un po sempliciotte ma sono un
megasuperstraprincipiante!!!
grazie per la pazienza!

 Mox
txs 1k !!!!!!

ragazzi scusate ancora:
la funzione:
(double) rand() / RAND_MAX
in fase di compilazione mi da un errore:
non riconosce time :((((
uso (purtroppo) VC++
qualcuno che può helpare?

 wrote in message:

lasciate stare! non disturbatevi! non sapevo che c'era da includere la
"time.h"
;P
grazie ancora a tutti!!!
me escluso!

"time.h"
č meglio che la includi cosi <time.h> cosi il compilatore
non la ricerca nemmeno nella directory corrente ma
direttamente nel path :)
--
Lawrence Oluyede
rhy...@myself.com

 direttamente nel path :)
txs!
gia che ci sei ti pongo un altro quesito:
dovrei far rallentare il processo in quanto usando come seme time(NULL) in
un ciclo while:
while(pos<5) {
  srand ((unsigned) time(NULL));
  array[pos] = ((((int) rand() / RAND_MAX) * 9) + 1);
  pos++;
}
di questo tipo (5 sole iterazioni!!!) il risultato è sempre n come numero
generato!
come posso far aspettare la macchina? con un ciclo nel ciclo? mi sembra una
baggianata però!
grazie e ciao!

 direttamente nel path :)
altra domanda:
ma con:
srand ((unsigned) time(NULL));
non passo a srand il valore 0 ?
che significa?
secondo me c'è un errore dato che dopo che chiamo:
((((double) rand() / RAND_MAX) * 9) + 1);
mi da solo ed esclusivamente 7 come output!
help!

  srand ((unsigned) time(NULL));
srand deve stare fuori dal ciclo while, mettilo prima del while.
-- 
Marco Barisione (ICQ 84277092)

che significa?
Dici a srand() di inizializzare il seed perndendo l'output della
funzione time... il NULL lo passi alla time per altri motivi, leggiti
la documentazione della funzione per scoprire a cosa gli serve quella
variabile :)
Srand() comunque la devi usare una sola volta all'inizio, non a ogni
ciclo, se no rischi di ripetere i risultati.


 megasuperstraprincipiante!!!
Non credo nell'esistenza delle domande sempliciotte :-) Non aver paura a
chiedere.
In ogni caso, se dovessimo uscire dal manifesto del ng, è nato da poco
free.it.discussioni.algoritmi in cui potremmo parlare in tutta libertà dei vari
generatori.
Domenico Delle Side, se ci stai leggendo e t'interessa, potremmo spostarci lì
per non rischiare di disturbare.
Ciao
Cristiano

 risultatato. [...]
Quasi tutti i generatori disponibili al pubblico hanno una "buona casualità",
l'unica eccezione è rappresentata dai generatori a congruenza lineare in quanto
non soddisfano parecchi requisiti (un altro difetto di rand() è che nella
maggior parte dei casi viene implementata proprio usando un lcg).
Cristiano

 srand deve stare fuori dal ciclo while, mettilo prima del while.
infatti avevo provato cosě e funzionava!
grazie!
ciao

 variabile :)
eeeh! mox, io uso VC++! non č il max ma per linux nn sono ancora pronto!
con le msdn di M$ non dice molto!
dove posso trovare la documnetazione?

dove posso trovare la documnetazione?
Come no?
Da MSDN:
|time
|Gets the system time.
|
|time_t time( time_t *timer );
|
|[...]
|
|Return Value
|
|time returns the time in elapsed seconds. There is no error return.
|
|Parameter
|
|timer
|
|Storage location for time
|
|Remarks
|
|The time function returns the number of seconds elapsed since midnight 
|(00:00:00), January 1, 1970, coordinated universal time, according to 
|the system clock. The return value is stored in the location given by 
|timer. This parameter may be NULL, in which case the return value is 
|not stored.
|[...]


 [CUT]
opss!!! non l'ho trovata subito!
scusate

 domanda scema: lcg???
Quello che ho scritto più sopra (è una sigla in inglese): generatore a
congruenza lineare.
E` uno del tipo: (i) = y(i-1) * a + b (mod m)
Uno che non lo conosce non può immaginare quanti problemi nasconde un generatore
così semplice. Conviene usarlo solo in particolari casi (a me ha fatto comodo
usarlo soltanto in due casi).
Se riesci a trovare un server con il ng degli algoritmi è meglio continuare là.
Cristiano

 funzione!
In questi casi basta usare google scrivendo: MT19937. Io non mi ricordo dove li
vado a pescare :-)
Cristiano