Non ci ho capito niente! Ricominciamo...
La libreria C include alcune funzioni per la generazione di numeri casuali. Va subito precisato che si tratta di una casualità piuttosto... fittizia, in quanto essi sono generati applicando un algoritmo di una certa complessità ad un numero base, detto seed (seme). Dato che l'algoritmo è sempre lo stesso, ad uguale seed corrisponde uguale numero casuale che, quindi, tanto casuale poi non è (infatti si parla, per la precisione, di numeri pseudocasuali). Per ovviare almeno parzialmente al problema, l'algoritmo di generazione del numero casuale modifica il seed, con l'effetto di abbattere la probabilità che venga generato sempre il medesimo numero casuale.
Ciò premesso, come fare ad ottenere un numero "casuale"? Semplice: basta invocare la funzione di libreria
int rand(void);
(prototipo in STDLIB.H), che restituisce un numero pseudocasuale compreso tra 0 e il valore della costante manifesta RAND_MAX (definita in LIMITS.H: in molte implementazioni è pari a 32767), anch'essa definita in STDLIB.H. La funzione rand() applica l'algoritmo sul seed, che viene modificato solo durante il calcolo. Poiché il seed è una variabile statica inzializzata a 1, una serie di chiamate a rand() produce sempre la stessa sequenza di numeri casuali, come il seguente banalissimo programma può facilmente evidenziare se lanciato più volte:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
register int i;
for(i = 0; i < 10; i++)
printf("%d\n",rand());
return(0);
}
Un rimedio può essere rappresentato dalla funzione
void srand(int newseed);
(prototipo in STDLIB.H), che assegna al seed il valore passatole come parametro (trattandosi di un intero, il valore massimo è 32767). E' evidente che successive chiamate a rand() producono identiche sequenze di numeri pseudocasuali, se il seed viene reinizializzato ad uno stesso valore:
....
srand(15);
for(i = 0; i < 10; i++)
printf("%d\n",rand());
srand(15);
for(i = 0; i < 10; i++)
printf("%d\n",rand()); // sequenza identica alla precedente
srand(16);
for(i = 0; i < 10; i++)
printf("%d\n",rand()); // sequenza diversa dalle precedenti
....
Più interessante appare la macro
void randomize(void);
definita (ancora una volta) in STDLIB.H. La randomize() assegna al seed il valore dei 16 bit meno significativi del numero di secondi trascorsi dal 1 gennaio 1970, calcolato mediante una chiamata alla funzione time() [1]:
#include <stdlib.h>
#include <time.h> // per randomize(), oltre a <stdlib.h>
....
randomize();
for(i = 0; i < 10; i++)
printf("%d\n",rand());
randomize();
for(i = 0; i < 10; i++)
printf("%d\n",rand()); // sequenza diversa dalla precedente
....
Come accennato poco sopra, randomize() è una macro e chiama la funzione time(), il cui prototipo si trova in TIME.H: di qui la necessità della direttiva
#include <time.h>
inserita nel precedente frammento di codice. Si noti che solo rand() e srand() sono normalmente disponibili sui sistemi Unix (vedere il capitolo dedicato alla portabilità).
Generare numeri pseudocasuali compresi tra 0 e RAND_MAX è certamente interessante, ma spesso lo è ancora di più controllare l’ampiezza del range: in altre parole, ottenere numeri compresi tra un valore minimo ed uno massimo scelti a piacere. A tale scopo in STDLIB.H è definita la macro
int random(int maxnum);
che genera un numero pseudocasuale compreso tra 0 e maxnum-1. Ad esempio
casuale = random(51);
restituisce un numero compreso tra 0 e 50, estremi inclusi, e lo assegna alla variabile (int) casuale. Se il limite inferiore del range deve essere diverso da 0, è sufficiente sottrarre la differenza (rispetto a 0) a maxnum e addizionarla al risultato:
casuale = random(41)+10;
assegna a casuale un valore compreso tra 10 e 50, estremi inclusi. La sottrazione e l’addizione descritte sono da intendersi in senso algebrico: se il limite inferiore è minore di 0, la differenza tra questo e 0 va sommata al limite superiore e sottratta al valore restituito da random():
casuale = random(61)-10;
assegna a casuale un valore compreso tra -10 e 50, estremi inclusi. Pertanto, una semplice funzione in grado di accettare anche il limite inferiore potrebbe somigliare alla seguente:
#include <stdlib.h>
int random2(int limite_inf, int limite_sup)
{
return(random(limite_sup-limite_inf+1)+limite_inf);
}
La random2() restituisce un numero pseudocasuale compreso tra limite_inf e limite_sup inclusi (si noti la differenza con random(), che esclude maxnum dal range). Va sottolineato che se l’espressione
limite_sup-limite_inf+1
restituisce un valore superiore al massimo ntero (con segno), random() (e, di conseguenza, anche random2()) restituisce sempre detto valore: nelle implementazioni in cui gli interi sono gestiti con 16 bit, pertanto, l’ampiezza massima del range è 32767: dal momento che random() consente di specificare il limite superiore, questo può essere 32767 se il limite inferiore è 0; se quest’ultimo è minore di 0, allora quello superiore, per la formula esaminata poco sopra, è pari, al massimo, a 32767-limite_inf.
Tale limitazione può essere superata con uno stratagemma, consistente nel considerare un qualsiasi numero come una semplice stringa di bit e quindi comporre il numero casuale "concatenando" tante stringhe quante sono necessarie:
/********************
BARNINGA_Z! - 1998
RANDOML.C - genera un numero casuale tra 0 e LONG_MAX-1
long randoml(long upperlim);
COMPILABILE CON TURBO C++ 2.0
bcc -O -d -c -mx randoml.c
dove -mx puo' essere -mt -ms -mc -mm -ml -mh
********************/
#include <stdlib.h>
#include <limits.h>
#define ITERATIONS ( \
((sizeof(long) - sizeof(RAND_MAX)) * CHAR_BIT) / \
(sizeof(RAND_MAX) * CHAR_BIT - 1) \
+ \
( \
( \
((sizeof(long) - sizeof(RAND_MAX)) * CHAR_BIT) % \
(sizeof(RAND_MAX) * CHAR_BIT - 1) \
) ? 1 : 0 \
) \
)
long cdecl randoml(long upperlim)
{
register i;
long randnum;
randnum = (long)rand();
for(i = 1; i <= ITERATIONS; i++)
randnum += (long)rand() << (i * (sizeof(RAND_MAX) * CHAR_BIT - 1));
return((randnum & LONG_MAX) % upperlim);
}
La funzione ha utilizzo analogo a quello di random(), ma accetta come parametro un numero compreso tra 0 e LONG_MAX (costante manifesta definita in LIMITS.H); tuttavia l'algoritmo utilizzato è sensibilmente diverso.
Infatti viene generato un primo numero casuale (mediante la funzione rand()), che occupa parte dei bit (quelli meno significativi) della variabile randnum. Per utilizzare tutti i bit disponibili [2] è necessario generare altri numeri casuali e "affiancarli", mediante operazioni di shift, a quelli già generati: detta operazione è gestita con un ciclo for, che ha lo scopo di rendere la funzione portabile ai sistemi nei quali il tipo long è gestito con un numero di bit diverso dai 32 solitamente utilizzati con i processori Intel per personal computer.
La costante manifesta ITERATIONS esprime il numero di cicli necessari per utilizzare tutti i bit restanti (esclusi, cioè, quelli già impegnati dal primo numero casuale generato). La sua definizione, solo apparentemente complessa [3], esprime il rapporto tra il numero di bit ancora liberi nella variabile di tipo long e il numero di bit occorrenti per memorizzare un numero casuale generato da rand() [4], nell'ipotesi che, in entrambe le grandezze, i sign bit non siano utilizzati. Detto rapporto è incrementato di 1 se la divisione tra le due grandezze fornisce un resto (in pratica il quoziente è arrotondato per eccesso).
Il numero casuale generato ad ogni iterazione è memorizzato nella variabile dopo uno shift a sinistra di un numero di bit pari a quanti ne sono già stati "occupati" dai numeri casuali generati in precedenza: ciò ha l'effetto di concatenare il nuovo numero (cioè la stringa di bit che lo rappresenta) alla sinistra della sequenza di bit già valorizzati nella variabile. L'arrotondamento per eccesso (sopra descritto) del numero di iterazioni può portare la conseguenza che parte dei bit del numero casuale generato nell'ultima iterazione sia perso, in quanto "spinto" dallo shift fuori dallo spazio disponibile nella variabile, senza che ciò abbia comunque conseguenze negative.
I 32 bit così valorizzati sono poi posti in AND con la costante manifesta LONG_MAX: in tal modo il sign bit è sempre uguale a 0. Infine, l'operazione modulo con il parametro passato alla funzione garantisce che randoml() restituisca un valore compreso tra 0 e il parametro stesso, diminuito di 1 (in altre parole, il resto del rapporto tra il numero casuale generato e il parametro), analogamente alla random(). Ne segue che il massimo valore ammissibile in input alla funzione è LONG_MAX.
Si noti che ITERATIONS è una costante, e come tale viene calcolata dal compilatore al momento della compilazione del sorgente: nonostante l'elevato numero di calcoli necessari per ottenerla, essa non può influenzare negativamente le prestazioni del programma che utilizzi randoml(). Vale piuttosto la pena di osservare che, in tal senso, può essere rilevante il numero di iterazioni necessarie per generare un numero casuale: posto RAND_MAX pari a 32767, occorrono 2 cicli se i dati di tipo long sono gestiti con 32 bit; per dati a 64 bit le iterazioni diventano 4.
Vediamo ora un approccio alternativo, consistente nel generare un numero casuale mediante la libreria C e riproporzionarlo successivamente al limite superiore richiesto.
/********************
BARNINGA_Z! - 1998
RANDOMX.C - genera un numero casuale tra 0 e LONG_MAX-1
long randomx(long upperlim);
COMPILABILE CON TURBO C++ 2.0
bcc -O -d -c -mx randomx.c
dove -mx puo' essere -mt -ms -mc -mm -ml -mh
********************/
#include
long randomx(long upperlim)
{
long factor;
if(upperlim < RAND_MAX)
return(rand() % upperlim);
factor = upperlim / RAND_MAX + ((upperlim % RAND_MAX) ? 1 : 0);
return((rand() * factor + randomx(factor)) % upperlim);
}
Se il limite superiore specificato è minore di RAND_MAX, la random() restituisce immediatamente il numero pseudocasuale generato dalla funzione di libreria rand() (l'operazione modulo con upperlim garantisce che il valore restituito sia compreso tra 0 e RAND_MAX-1). In caso contrario viene calcolato un fattore di proporzionalità come rapporto tra il limite superiore richiesto e RAND_MAX, arrotondato per eccesso. A questo punto, generando un numero casuale compreso tra 0 e RAND_MAX-1 (mediante rand()) e moltplicandolo per il fattore sopra calcolato, si ottiene un risultato grossolanamente [5] compreso nel range desiderato: si osservi però che detto risultato è sempre, per definizione, un multiplo di factor; per "tappare i buchi" tra un multiplo ed il successivo si deve sommare al numero generato un secondo numero pseudocasuale compreso tra 0 e factor-1. Ma generare numeri casuali compresi tra 0 e un limite dato è esattamente il compito di randomx(), che quindi può farlo ricorsivamente, cioè chiamando se stessa: ecco perché al prodotto rand()*factor viene sommato il valore restituito da randomx(factor). L'approccio ricorsivo consente inoltre di gestire correttamente, in modo del tutto trasparente, il caso in cui factor risulti maggiore di RAND_MAX-1 (il che si verifica quando upperlim è maggiore o uguale al quadrato di RAND_MAX).
Il massimo valore di upperlim è pari a LONG_MAX-((2*factor)-2) [6]: infatti, essendo factor arrotondato per eccesso, il prodotto rand()*factor può risultare superiore a upperlim di factor-1; inoltre si deve considerare che a detto prodotto è sommato il secondo numero casuale, anch'esso pari, al massimo, a factor-1.
Vale la pena di confrontare rapidamente randoml() e randomx().
Sotto l'aspetto della praticità di utilizzo, risulta senz'altro preferibile la randoml(), in quanto il massimo valore di upperlim è noto e costante, ed è pari a LONG_MAX-1 (il range disponibile è dunque più esteso).
D'altra parte, randomx() è portabile, a differenza di randoml(), la quale, effettuando operazioni di shift a sinistra, assume implicitamente che l'organizzazione interna delle variabili (cioè il significato dei bit che le compongono) sia di tipo backwords e che il sign bit sia sempre quello più significativo, il che non è vero per tutti i processori [7].
Infine, qualche considerazione interessante nasce circa la velocità di calcolo (assumendo, per semplicità, che i dati di tipo long siano gestiti in 32 bit). Il tempo di elaborazione richiesto da randoml() è indipendente dal valore di upperlim: esso è, anzi, costante, in quanto per la generazione di un numero casuale la funzione effettua sempre tre chiamate a rand(). Al contrario, il tempo richiesto da randomx() aumenta al crescere di upperlim; tuttavia non vi è un rapporto di proporzionalità diretta. Infatti, per valori di upperlim inferiori a RAND_MAX viene effettuata una sola chiamata a rand(); per valori di upperlim compresi tra RAND_MAX e il suo quadrato ne vengono effettuate due; infine, rand() è chiamata tre volte per valori uguali o superiori al quadrato di RAND_MAX. Sulla scorta di quanto esposto [8], ci si può aspettare che il tempo di elaborazione di randomx() sia pari a circa un terzo di quello della randoml() per valori di upperlim minori di RAND_MAX, per poi passare a circa due terzi fino al quadrato di questo; i tempi di elaborazione dovrebbero essere assai vicini per valori di upperlim uguali o superiori al quadrato di RAND_MAX.
Una verifica empirica (effettuata cronometrando entrambe le funzioni, eseguite centomila volte con diversi valori di upperlim) conferma quanto ipotizzato per valori di upperlim inferiori a RAND_MAX (randomx() impiega meno della metà di randoml()) [9] e compresi tra RAND_MAX e UINT_MAX (randomx() impiega circa due terzi del tempo richiesto da randoml()). Per valori compresi tra UINT_MAX e il quadrato di RAND_MAX si verifica invece un inatteso e considerevole aumento del tempo di elaborazione di randomx(), che risulta significativamente superiore a quello di randoml(), ma costante in tutto l'intervallo. Per valori superiori al quadrato di RAND_MAX il tempo di elaborazione di randomx() aumenta (come atteso) di una quantità circa pari all'incremento verificatosi tra il primo e il secondo dei range controllati. L'analisi dei sorgenti assembler di randomx(), generati mediante l'opzione -S del compilatore, evidenzia la causa del rallentamento inaspettato: le operazioni aritmetiche coinvolte nell'algoritmo di calcolo (in particolare moltiplicazione, divisione e modulo) vengono effettuate mediante funzioni di libreria non documentate, che ottimizzano il calcolo utilizzando algoritmi semplificati se le word più significative dei dati a 32 bit sono pari a 0: è proprio il caso dei valori compresi tra 0 e UINT_MAX. Attribuendo alla maggiore complessità del calcolo il rallentamento osservato per upperlim compreso tra UINT_MAX e il quadrato di RAND_MAX, il comportamento di randomx() si riconduce a quanto teoricamente previsto. Compilando randomx() con l'opzione -3 del compilatore, che genera codice specifico per processori a 32 bit, una parte dei calcoli sui dati long viene risolta utilizzando direttamente le istruzioni e i registri del processore, senza l'ausilio delle funzioni di libreria, con un considerevole miglioramento della performance. Di conseguenza, il tempo di elaborazione di randomx() diviene circa pari a quello di randoml() per valori di upperlim compresi tra UINT_MAX e il quadrato di RAND_MAX, e risulta superiore solo per valori maggiori di quest'ultimo.
OK, andiamo avanti a leggere il libro...
Non ci ho capito niente! Ricominciamo...