C - rand() - un po' più rand ..

[simo85]

Ciao a tutti,

Stavo scrivendo un piccolo programma in C in grado di generare delle stringhe di caratteri generati pseudocasualmente, con la funzione rand() e lunghezza della stringa a scelta.

Il codice scritto è questo:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <libgen.h>
#include <time.h>

int main(int argc, char *argv[])
{
   if(argc != 2)
   {
      printf("\nusage: %s n\n", basename(argv[0]));
      printf("where \'n\' is the string lenght\n\n");
      exit(1);
   }
   else
   {
      srand(time(NULL));

      int i = 0;
      int N = atoi(argv[1]);

      while(i < N)
      {
         printf("%c", 32 + rand() % (127 - 33) + 1);
         i++;
      }

      putc(10, stdout);
      exit(0);
   }
}


Ho successivamente testato, con la classica generazione del seme del codice precedente, quante volte potrebbe essere ripetuto lo stesso risultato per n esecuzioni, con la seguente stringa di comando:

Codice: Seleziona tutto

$ for i in {0..300}; do echo -n "$i  - "; ./file 30 ; done

La quale esegue il programma compilato con nome file 300 volte.
Il risultato è peggio di quello che mi aspettavo. Le stringhe non sono tutte diverse e viene generata una sequenza diversa ogni 100 esecuzioni circa.

Successivamente ho applicato questa modifica alla generazione del seme:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <libgen.h>
#include <time.h>

int main(int argc, char *argv[])
{
   if(argc != 2)
   {
      printf("\nusage: %s n\n", basename(argv[0]));
      printf("where \'n\' is the string lenght\n\n");
      exit(1);
   }
   else
   {
      int i = 0;
      int N = atoi(argv[1]);
      int *p = NULL;
      unsigned n = (unsigned) &p;

      srand(n);

      while(i < N)
      {
         printf("%c", 32 + rand() % (127 - 33) + 1);
         i++;
      }

      putc(10, stdout);
      return 0;
   }
}


Ho salvato il file come file2.c ed eseguendo n volte con il comando sopra riportato, si può osservare come il risultato ovviamente migliora nettamente.

Non so, magari è qualcosa che gli utenti che masticano il C da anni sapevano già da tempo, però io volevo farlo presente nel caso qualcuno volesse generare delle sequenze di numeri (e non) casuali in un lasso breve di tempo.

Se qualcuno conocesse metodi più casuali sarebbe interessante condividerli.

[DirtyDeeds]

Un generatore di numeri pseudocasuali non dà nessuna garanzia che a ogni esecuzione di un programma venga generata una sequenza diversa, il seme potrebbe essere sempre lo stesso. Se l'utente ha questa necessità deve provvedere a inizializzare il generatore con un seme diverso a ogni esecuzione (ci sono anche casi in cui uno ha bisogno della stessa sequenza a ogni esecuzione).

La funzione rand del C, poi, è nota per non essere un buon generatore di numeri pseudocasuali e ciò è riconosciuto anche nello standard del C:

There are no guarantees as to the quality of the random sequence produced and some implementations
are known to produce sequences with distressingly non-random low-order bits. Applications with
particular requirements should use a generator that is known to be sufficient for their needs.

Meglio, quindi, non usarla per applicazioni serie. Un buon generatore è, per esempio, il Mersenne Twister, ma ce ne sono anche altri.

Il C++11 ha una libreria per la generazione di numeri casuali molto completa, v. qui.

[DirtyDeeds]

Aggiungo un paio di commenti al codice che hai postato.

1) Il codice da te postato non è portabile perché assume che la codifica dei caratteri sia quella ASCII.

2) Occhio che un'espressione come

Codice: Seleziona tutto

33 + rand() % (127 - 33)

non garantisce che i numeri casuali siano distribuiti uniformemente tra 33 e 126. Il motivo è che rand genera un numero casuale tra 0 e RAND_MAX, ma non è detto che RAND_MAX sia divisibile per 127-33 = 94. I codici vicini a 126 hanno quasi sicuramente una minor probabilità di essere estratti rispetto a quelli vicini a 33.

[simo85]

OK facevo meglio a non postare nulla.

Grazie comunque per le osservazioni.

[GuidoB]

Ciao Simone.

Nel tuo primo esempio, come argomento per srand() hai utilizzato la funzione time(NULL), che restituisce i secondi trascorsi dall'epoca (ore 00:00 del 1º gennaio 1970). Questo valore cambia solo una volta al secondo.

Un miglioramento potrebbe essere la chiamata di

Codice: Seleziona tutto

gettimeofday(&tv, NULL);

dove tv.tv_sec sono ancora i secondi trascorsi dall'epoca, e tv.tv_usec sono i microsecondi (da aggiungere al secondo corrente).
Quindi

Codice: Seleziona tutto

(unsigned int)tv.tv_sec * 1000000 + (unsigned int)tv.tv_usec

almeno in teoria, cambia ogni microsecondo.
In realtà non tutte le macchine hanno una risoluzione che si spinge fino al microsecondo, ma comunque il valore cambia molto più spesso di una volta al secondo.

Nel secondo esempio utilizzi un indirizzo di una variabile locale, che presumibilmente cambia a ogni esecuzione (ma non è detto).
Sommargli un altro po' di spazzatura non farebbe male, tipo:

Codice: Seleziona tutto

(unsigned int)&ui + ui

dove ui è un unsigned int non inizializzato (e quindi leggi la spazzatura che contiene, che comunque potrebbe essere sempre la stessa).
Leggere una variabile non inizializzata ti darà un warning in compilazione... pazienza.

Potresti utilizzare anche i due metodi insieme (semplicemente sommando i due numeri che ottieni).

Per aggiungere altra indeterminazione potresti sommare anche il numero del processo (ottenuto con getpid()). Anche da solo dovrebbe bastare, se sei sicuro che la tua macchina lo cambia ad ogni esecuzione.

La bontà di questi metodi dipende dalla macchina su cui li usi.

Se sei su un sistema a microcontrollore, in molti casi questi metodi non funzioneranno.

In tal caso, se hai qualche periferica che ti restituisce un valore letto dall'esterno (luminosità, temperatura, o l'istante in cui si verifica un evento che non dipende dall'istante di accensione, per esempio la fase della tensione di rete o l'istante della pressione su un pulsante) puoi usare quello.
Spesso però non sono eventi tanto "variabili" e il risultato è mediocre, e/o c'è il problema che devi attendere che l'evento casuale si verifichi, e tu magari ne hai bisogno subito.

Un altro modo di cui avevo parlato tanto tempo fa con TardoFreak è, se hai una EEPROM a disposizione, tenere traccia del numero di volte che il dispositivo è stato acceso. In questo modo il seme di srand cambia ad ogni accensione. Però tutti i dispositivi "gemelli" genereranno le stesse sequenze.

Si può anche memorizzare in EEPROM un valore a cui viene sommato l'istante in cui un certo evento esterno accade per la prima volta da ogni accensione. In questo modo già all'accensione hai a disposizione un numero che dipende dalla storia passata del dispositivo e puoi già usare senza dover aspettare che il tuo evento si verifichi nell'accensione corrente.

Usando questo numero, eventualmente sommato al numero di accensioni (per avere sequenze comunque diverse anche se l'evento qualche volta non si verifica), la sequenza generata sarà ogni volta diversa anche tra dispositivi "gemelli".

Se ancora non basta, si possono generare numeri casuali utilizzando processi fisici, tipo il rumore su un diodo zener.

[DirtyDeeds]

OK facevo meglio a non postare nulla.

Direi che hai fatto bene, invece: la generazione di numeri casuali è sempre un argomento interessante

[TardoFreak]

La generazione di numeri casuali (davvero casuali) è un discreto casino.
Io sfrutto azioni casuali come quella descritta da Guidob (seme catturato all' accensione) o, se ho la fortuna di fare un qualcosa che prevede un qualsiasi tipo di intervento umano come la pressione di un tasto, catturo il valore di un contatore quando il pulsante viene premuto.
Ho avuto bisogno di usare una EEPROM per mettere da parte semi prodotti in questo modo in modo da averli sempre disponibili.

[DirtyDeeds]

La generazione di numeri casuali (davvero casuali) è un discreto casino.

Anche la definizione di che cos'è una sequenza casuale è un discreto casino

Qui si possono trovare un po' di informazioni sui test statistici che possono essere usati per valutare i generatori di numeri pseudocasuali.

I generatori di numeri pseudocasuali hanno particolare importanza per le applicazioni crittografiche (qui alcune informazioni) e per le analisi di tipo Monte Carlo. In quest'ultimo caso, un generatore di scarsa qualità può generare errori significativi nei risultati.

[simo85]

Ciao ragazzi mi fa piacere che abbiate preso parte alla discussione.

Sono al corrente del fatto che la generazione veramente casuale (infatti io con la rand() volevo far riferimento appunto alla generazione pseudocasuale) è un discreto casino.

Questo valore cambia solo una volta al secondo.

Questo è il motivo per cui ho cambiato sistema nella generazione del seme.

Per aggiungere altra indeterminazione potresti sommare anche il numero del processo (ottenuto con getpid()). La bontà di questi metodi dipende dalla macchina su cui li usi.

Ovviamente essendo un pochino fanatico del pinguino ho anche provato questo sistema, richiamando la funzione getpid() generando un sottoprocesso, ed usando anche la funzione getppid().

Tuttavia come dici tu, la bontà dipende appunto dal sistema che si usa ed il PID di processo restituito è sempre stato ma già me lo aspettavo.

[GuidoB]

Tuttavia come dici tu, la bontà dipende appunto dal sistema che si usa ed il PID di processo restituito è sempre stato ma già me lo aspettavo.

Una differenza di 1 è abbastanza. Per i metodi comunemente usati (generatori basati sulle congruenze lineari) per due semi che differiscano anche solo di 1 le sequenze generate saranno comunque molto diverse.

In alcuni generatori i primi numeri pseudo-casuali generati con semi molto vicini potrebbero essere simili (fai qualche prova). Per ovviare all'inconveniente potresti scartare i primi due o tre numeri generati.

Questo documento e quest'altro spiegano velocemente come funzionano questi generatori (attenzione che per un errore del visualizzatore di PDF il segno "=" nel primo documento è raffigurato come "-").

Piuttosto, se reinizializzi il computer spesso, è facile che i process id siano sempre di valore basso, e quindi le sequenze generate saranno sempre le solite. Quindi è meglio sommare al process id i microsecondi trascorsi dall'epoca...