January 26, 2018 · Programmazione

Quando rand() smette di essere rand

Molto spesso quando si inizia a programmare in C/C++ si arriva ad incontrare la fantomatica funzione rand(), una funzione appartenente alla libreria standard ( in C e in C++) che si occupa di generare numeri pseudo-casuali. Ed ecco che nello studente parte subito l'errore iniziale, inconsciamente associa la parola pseudo-casuale a casuale, cosa ben differente e dunque inizia a generarsi numeri casuali usando la seguente espressione:

rand() % var

Ma cosa c'è di sbagliato effettivamente nell'usare la seguente espressione?. Bè l'errore sta nell'usare l'operatore modulo, esso comprometterà automaticamente la nostra generazione di numeri casuali creando un modulo bias.
La funzione rand() non fa altro che scegliere un numero naturale che va da 0 a RAND_MAX(), per chi non lo sapesse RAND_MAX() è una costante definita nella libreria standard.

Dunque per comodità proviamo ad eseguire questo semplice esercizio:

Es. : Generare casualmente numeri da 0 a 2 per 20 volte tramite la funzione rand.

Una volta letto l'esercizio viene naturale pensare di scrivere il seguente codice:

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

int main(void) {
  srand(time(NULL));
  
  int num;
  
  for(int cnt = 0; cnt < 20; cnt++){
    if(cnt % 10 == 0){
      puts(" ");
    }
    num = rand() % 3;
    printf("%d ", num);
  }
  
  return 0;
}

Bè non soprendetevi se ve lo dico ma l'esercizio è sbagliato, il codice appena scritto in verità non ha creato numeri casuali. Sempre per comodità proviamo ad immaginare che la costante integrale massima di RAND_MAX sia 10 e riproviamo a rieseguire il vecchio codice. L'uscita dei numeri 0,1,2 non sarà definita con probabilità uguale e ciò viola il concetto di numero casuale. Questo è dato dal fatto che in caso rand():

restituisce 0,3,6,9 -> rand() % 3 == 0. Ci sarà una probabilità di p(0) = 4/11
restituisce 1,4,7,10 -> rand() % 3 == 1. Ci sarà una probabilità di p(1) = 4/11
restituisce 2,5,8 -> rand() % 3 == 2. Ci sarà una probabilità di p(2) = 3/11

Ciò prova che non ci sarà una generazione di numeri casuali con le stesse probabilità. Applicato tutto ciò a una distribuzione più grande questo potrebbe portare a uno sfondamento della distribuzione arrivando a biasare i numeri più piccoli.

Per far sic he rand() % var resituisca una gamma di numeri da 0 a n-1 con probabilità uguale dobbiamo far si che questa condizioni si verifichi:

RAND_MAX % var == var - 1

Continue . . .

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket
Comments powered by Disqus