[C] Utilizzo di rand()

[utente__medio11]

Per ottenere un numero casuale nell'intervallo \( [ 0 \ ; \ n ) \) si utilizza di solito la formula [inline]rand() % n[/inline], ma riflettendo, oltre al fatto che bisognerebbe controllare che \( n \leq RAND_{MAX} + 1 \), mi sono reso conto che solo in alcuni casi la suddetta formula fornisce una distribuzione uniforme, ossia quando \( RAND_{MAX} + 1 = k \cdot n \) con \( k \in N^+ \).

Per esempio ipotizzando \( RAND_{MAX} = 15 \) e \( n = 7 \)

 0 % 7 = 0
 1 % 7 = 1
 2 % 7 = 2
 3 % 7 = 3
 4 % 7 = 4
 5 % 7 = 5
 6 % 7 = 6
 7 % 7 = 0
 8 % 7 = 1
 9 % 7 = 2
10 % 7 = 3
11 % 7 = 4
12 % 7 = 5
13 % 7 = 6
14 % 7 = 0
15 % 7 = 1

avremmo

$p(0) = p(1) = 3/(RAND_(MAX)+1) = 3 / 16$
$p(2) = p(3) = p(4) = p(5) = p(6) = 2 / 16$

Magari poi penso a qualcosa di più raffinato, ma nel frattempo dal momento che non so come funzioni [inline]rand()[/inline] dietro le quinte, mi chiedevo se un approccio rudimentale come il seguente restituisca o meno una distribuzione uniforme:

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

unsigned int my_rand(unsigned int n)
{
    if(n > RAND_MAX + 1)
    {
        return n;
    }
    if(!((RAND_MAX + 1) % n))
    {
        return rand() % n;
    }
    unsigned int r;
    for(unsigned int a = RAND_MAX / n * n; (r = rand()) >= a;);
    return r % n;
}

int main()
{
    srand(time(0));
    printf("%u\n", my_rand(37));
}

[Quinzio]

Direi che va bene, fa quello che deve fare.
In rete trovi tutto su come funzionano quelle funzioni pseudo-causali tipo la rand.
Pero' non so se ne vale la pena, bisogna spenderci del tempo e dipende da cosa devi fare.

[apatriarca]

[tt]rand[/tt] è una pessima funzione per generare numeri casuali e l'espressione [tt]rand() % n[/tt] non genera numeri uniformi come hai già osservato. Se è importante generare "buoni" numeri casuali, è meglio utilizzare altre funzioni (non standard).

[utente__medio11]

"Quinzio":In rete trovi tutto su come funzionano quelle funzioni pseudo-causali tipo la rand.
Pero' non so se ne vale la pena, bisogna spenderci del tempo e dipende da cosa devi fare.

In effetti in rete si trova parecchio materiale sulla generazione di numeri pseudo-causali, oltre al fatto che ho letto che esistono librerie apposite per operazioni di questo tipo.
Alla fine lo scopo del topic era più che altro ragionare su un utilizzo più ponderato della classica [inline]rand()[/inline].

"Quinzio":Direi che va bene, fa quello che deve fare.

In fin dei conti quello che ho implementato è una sorta di estrazione con rimessa ridotta al minimo.

"apatriarca":l'espressione [tt]rand() % n[/tt] non genera numeri uniformi come hai già osservato

Magari poi rifletto anche su un possibile approccio senza "tentativi".

[apatriarca]

L'approccio che scarta i valori è quello più uniforme. La principale ragione è che non c'è alcun modo di suddividere RAND_MAX valori in N blocchi della stessa dimensione se N non divide RAND_MAX. Ci sarà sempre qualche blocco che sarà maggiore o minore degli altri.