Algoritmo di casualità?

Ormai gli algoritmi di casualità sono implementati automaticamente in qualunque programma di progettazione informatica. Ma effettivamente, come si fa a creare un algoritmo di casualità? Ce ne sono di diversi tipi, di "migliori" e "peggiori"?

2 risposte

Classificazione
  • 8 anni fa
    Risposta preferita

    Innanzitutto, non si chiama casualità, ma pseudocasualità.

    Un algoritmo che genera numeri pseudocasuali è un algoritmo deterministico per generare numeri che rispettano alcune proprietà statistiche tipiche dei numeri casuali con una certa distribuzione.

    La maggior parte de, se non tutti, i generatori pseudocasuali esistenti genera numeri con distribuzione unforme. Quindi, la proprietà più banale è quella dell'uniformità lineare: se usi il generatore per generare un quantitativo abbondante di numeri in un certo intervallo, alla fine, avrai una distribuzione statisticamente uniforme.

    PS: gli ultimi processori Intel integrano un circuto per generare numeri casuali, senza pseudo-.

    Le parole "abbondante" e "statisticamente uniforme" nascondono due concetti della probabilità e della statistica abbastanza complessi: la legge dei grandi numeri e la verifica statistica delle ipotesi. Ad ogni modo, se verificare la bontà di un generatore è molto difficile, i generatori, di contro, possono essere anche molto facili.

    Il generatore più facile è il moltiplicativo congruenziale:

    const int A = ...;

    const int M = ...;

    static int x = X0;

    int rand()

    {

    return x = (x * A) % M;

    }

    I parametri A e M sono fissati. A partire da un valore iniziale x0, si generano numeri facendo semplicemente una moltiplicazione e calcolando il resto di una divisione.

    Questi generatori non sono un granché, ma si dimostra che, scegliendo opportuni valori di A e M, e se X0 è diverso da 0, si può rispettare la proprietà di uniformità su intervalli 1...M o più piccoli.

    Un generatore più evoluto, che è quello usato da Windows e dalle versioni più vecchie di Linux, è il LCG:

    const int A = ...;

    const int M = ...;

    const int C = ...;

    static int x = X0;

    int rand()

    {

    return x = (x * A + C) % M;

    }

    Con questa piccola modifica, si dimostra che, sempre con opportuni valori di A, M e C, si riesce ad avere un generatore linearmente uniforme sui sottointervalli di 0...M.

    Le versioni attuali di Linux usano un generatore simile al LCG, ma con l'aggiunta di un terzo fattore, che permette di allungare il ciclo del generatore (perché tutti i generatori, a un certo punto, si ripetono).

    Un altro generatore molto usato, ma più complesso, è il Mersenne Twister. Questo generatore, oltre ad avere l'unformità lineare, è uniforme in spazi fino a 623 dimensioni (è uniforme anche se, invece di prendere punti su una linea, prendi punti in un quadrato, in un cubo, ... fino a un ipercubo a 623 dimensioni).

  • 8 anni fa

    Ciao!

    Se hai bisogno di aiuto visita ed iscriviti su http://www.cplobby.it/ . Si tratta di un forum nato da poco riguardante l'informatica, la programmazione e l'elettronica in generale, lì sapranno aiutarti senza dubbio! Basta che ti iscrivi (ovviamente gratuitamente) e in 1 minuto puoi aprire la discussione con il tuo problema! Vedrai che te lo risolveranno subito! E poi puoi aiutare un forum emergente a crescere grazie anche al tuo contributo, magari diventando anche un membro dello staff! http://www.cplobby.it/

Altre domande? Fai una domanda e ottieni le risposte che cerchi.