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

[TardoFreak]

... Un buon generatore è, per esempio, il Mersenne Twister, ma ce ne sono anche altri ...

Quali?
Te lo chiedo perché mi sono imbattuto in un problema serio ed ho visto che la rand è ... assi lassativa.

L' algoritmo del link necessita di troppe risorse per implementarlo nei micro che uso io, non tanto per la FLASH che ne ho ancora parecchia quanto per la RAM che è un tantino piccolina.
Non ci sarebbe una via di mezzo, o meglio più vie di mezzo, in modo da poter implementare un discreto compromesso?

Ah, dimenticavo: da scrivere (o già scritta) in C.

[dimaios]

Sarei curioso di vedere se l'algoritmo compilato per un microcontrollore ha qualche possibilità di funzionamento reale.

http://fmg-www.cs.ucla.edu/geoff/mtwist.html#downloading


Comunque un algoritmo molto rapido è lo Xorshift

http://en.wikipedia.org/wiki/Xorshift

Oppure c' è questo :

http://en.wikipedia.org/wiki/Blum-blum-shub

Comunque utilizzo sempre il Mersenne Twist Pseudorandom Number Generator.

[DirtyDeeds]

Prima di tutto, un'osservazione: ogni generatore di numeri casuali ha i suoi problemi, quello ideale non esiste, soprattutto se lo spazio è limitato e alcuni possono avere problemi con determinate inizializzazioni. La rand() del C è in genere un semplice generatore lineare a congruenza.

Qui ci sono alcune implementazioni in C dell'algoritmo WELL che dovrebbe avere ottime caratteristiche e un codice più leggero del MT. Il numero dovrebbe identificare il periodo nella forma 2^n. Tieni conto che un generatore a congruenza ha in genere un periodo dalle parti di 2^35-2^45 o giù di lì, e poi ha anche altri problemi. Io punterei a usare questo, altrimenti se non ti ci sta:

Qui trovi una survey di RNG, dovrebbero esserci anche un po' di implementazioni.

Qui c'è un articolo su un insieme di test per RNGs e al §7 analizza i risultati di alcuni generatori comuni.

Qui trovi la descrizione di un po' di metodi, tra cui alcuni di quelli che ti ha già segnalato dimaios.

[dimaios]

Qui trovi la descrizione di un po' di metodi .....

Bel documento DirtyDeeds, veramente ben fatto.

[TardoFreak]

Ho dato un rapido sguardo, oggi andrò più a fondo.
Ho anche trovato l' implementazione della rand() del C, una vera porcata.

Codice: Seleziona tutto

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

In confronto quella di xor128 è un lusso a confronto, anche solo a livello di codice.

Codice: Seleziona tutto

#include <stdint.h>
uint32_t xor128(void)
{
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;

  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

Oggi la provo per vedere se è meglio (lo sarà sicuramente). In tal caso dovrò implementare anche la funzione corrispondente alla srand() per avere sequenze con diversi semi.
Quello che non riesco a capire è se le inizializzazioni delle 4 variabili sono messe così a capoccia o hanno un significato ben preciso.

[dimaios]

Non sono affatto messe a capocchia e la motivazione teorica e' piuttosto tosta da comprendere.
Comunque le questioni teoriche sono spiegate nei documenti link e link.
A pag. 14 trovi una versione alternativa interessante per i double nell'intervallo [0,1).

Codice: Seleziona tutto

static unsigned int x[8]; /* Generator’s state.*/
/* Initializes state.*/
void initxorshift7 (unsigned int *init) {
int j;
for (j=0; j<8; j++) x[j] = init[j];
}
/* Advances by one step and returns a number in [0,1).*/
double xorshift7 (void) {
static int k = 0;
unsigned int y, t;
t = x[(k+7) & 0x7U]; t = t ^ (t<<13); y = t ^ (t<<9);
t = x[(k+4) & 0x7U]; y^= t ^ (t<<7);
t = x[(k+3) & 0x7U]; y^= t ^ (t>>3);
t = x[(k+1) & 0x7U]; y^= t ^ (t>>10);
t = x[k]; t = t ^ (t>>7); y^= t ^ (t<<24);
x[k] = y; k = (k+1) & 0x7U;
return ((double) y * 2.32830643653869628906e-10 );
}


[DirtyDeeds]

Ho anche trovato l' implementazione della rand() del C, una vera porcata.

Non è detto che sia quella. Lo standard non definisce come quella funzione debba essere implementata. Dice solo che il valore di RAND_MAX debba almeno essere 32767. Su un altro PC ho i sorgenti della libreria C del gcc, quando riesco vado a vedere com'è stata fatta per quella particolare libreria l'implementazione.

Quello che non riesco a capire è se le inizializzazioni delle 4 variabili sono messe così a capoccia o hanno un significato ben preciso.

Tuca niente! I valori delle costanti che vengono messe nei generatori sono studiati in modo da dare buone proprietà statistiche, un certo periodo e devono soddisfare certi criteri. Se uno non conosce in dettaglio la teoria che c'è dietro non può modificare quei valori.

[TardoFreak]

Quindi non c'è modo di scrivere una funzione di inizializzazione basata su un seme.

[DirtyDeeds]

Oops, stavo guardando la versione double

[TardoFreak]

Ok, ora devo andare in ospedale, quando rientrerò cercherò di capire come fare un' inizializzazione per una versione che mi dia un numero intero a 32 bit.