backup del Post

Generatore mentale di numeri (pseudo)casuali

Avete mai provato a giocare a carta, forbici e sasso contro un computer? No? Può essere un’esperienza interessante, anche se frustrante. L’anno scorso era apparso sul New York Times un link a un programma contro cui giocare a rock, paper, scissors (il nome inglese del gioco). Il programma era genuino, nel senso che decideva la sua mossa prima di sapere quale fosse la vostra. Eppure se si faceva una trentina di partite era molto probabile che il vincitore complessivo fosse lui. Il trucco però c’era, in un certo senso: il programma valutava la successione dei simboli da voi mostrati in precedenza, e immaginava la struttura, il pattern se volete parlare difficile, che voi avevate inconsciamente seguito nelle vostre scelte; e vi fregava.

Questo esempio dovrebbe avervi fatto capire, se non ci avevate mai pensato, come quello dei numeri casuali è un bel business. I numeri casuali servono ovunque, dalla crittografia alla simulazione numerica; tra l’altro ne servono tanti, quindi occorre anche generarli in qualche modo. Un tempo il sistema più semplice per avere una lista di numeri casuali era mettersi con tanta pazienza a registrare i numeri usciti su una roulette: il metodo Monte Carlo non prende il nome da questa usanza, però fa capire come la roulette sia stata per molto tempo il meccanismo più casuale noto agli uomini. Un altro metodo molto casuale richiede un contatore Geiger e del materiale radioattivo, ma come potete immaginare non è che sia molto usato se non in contesti ben particolari.

Ma oggi ci sono i computer, mi direte. Un qualunque trabiccolo appena più potente della calcolatrice trovata nel fustino di detersivo ha una funzione random(), o rand(), o rnd(), o srand(), o insomma qualcosa che come dice il nome stesso genera numeri casuali. Dov’è il problema, allora? Beh, il piccolo guaio è che un computer è bravo a fare tante cose, ma non esattamente a generare numeri casuali, visto che per definizione i numeri vengono generati secondo una formula che è tutto meno che casuale. In effetti esistono generatori hardware di numeri casuali, ma non li si trova certo sul PC che abbiamo a casa; ci dobbiamo accontentare di generatori di numeri pseudocasuali, tali cioè che se non ne prendiamo troppi non riusciamo a notare la differenza con i numeri casuali: meglio, non ci riesce nemmeno un programma statistico oppure il robot del New York Times.

(Nota a margine: le cifre decimali di pi greco per il momento soddisfano tutti i test di casualità; se non fosse computazionalmente abbastanza scomodo crearle, si potrebbero tranquillamente usare come successione di numeri casuali. Eppure sono tutto meno che casuali, no? Tutto questo per dire che il concetto di “numero casuale” è molto, molto scivoloso. Fine della nota a margine)

Storicamente, i primi algoritmi di generazione di numeri pseudocasuali implementati nei computer sono stati i generatori lineari congruenziali, in inglese Linear Congruential Generator o LGC: si parte da un numero a caso (ehm…, vabbè, in genere si guarda l’ora e si prendono i milionesimi di secondo o quello che si può avere) X₀ e si generano ricorsivamente i numeri successivi con la formula

X_n+1 = (aX_n + c) mod p

dove naturalmente a, c, p sono scelti opportunamente; per esempio è utile anche se non indispensabile che psia un numero primo. Un vantaggio non indifferente di un LCG è che quando si ha bisogno di numeri non casuali, per esempio per debuggare un programma, si può usare sempre lo stesso X₀ (“seme”, o “seed” se siete anglofoni) ed essere sicuri che la successione generata sia la stessa.

Premesso tutto questo, qualche mese fa un pazzoide ha scritto un post che spiegava come avere un LCG abbastanza semplice da poter essere calcolato a mente. Il nostro cervello umano, il wetware come lo chiama Rudy Rucker, naturalmente è ben diverso da un cervello elettronico: a parte la velocità di calcolo infinitesima, noi abbiamo una capacità di memoria piuttosto limitata, e preferiamo lavorare in base 10 piuttosto che in base 2. Tutto ciò si traduce in una scelta completamente diversa dei parametri per il generatore.

Yun William Yu, il pazzoide di cui dicevo, dà alcune possibilità, a seconda della capacità del calcolatore umano di fare i conti a mente. In tutti i casi usa c=0, per ridurre la quantità di informazione da tenere a mente. Il primo suo esempio di LCG è X_n+1 = 6X_n mod 59. Stop! Non scappate! Non è così terribile come sembra! Un minimo di algebra aiuta a semplificarci la vita. Sappiamo che 60 = 1 mod 59; quindi a partire da un numero qualunque, diciamo 42, basta moltiplicare per 6 la cifra delle unità e sommare quella delle decine per ottenere il numero successivo. Da 42 abbiamo dunque 16, 37, 45, 34, 27, 44… A partire da questa successione prendiamo la nostra successione di numeri casuali, usando solo la cifra delle unità: 2, 6, 7, 5, 4, 7, 4, … Questo naturalmente a meno che non ci servano proprio numeri pseudocasuali tra 1 e 58, il che mi pare piuttosto improbabile. Inutile dire che si possono anche ricavare numeri binari (pari=0, dispari=1), ternari per giocare contro il robottino del NYT o altro. Sta a voi scegliere.

Attenzione: non solo i numeri generati in questo modo non sono poi troppo casuali, visto che per definizione al più dopo 58 iterazioni sono stati generati tutti i numeri possibili e la storia, pardon la successione, si ripete; ma proprio perché vengono generati i numeri da 1 a 58 si ha che il 9 e lo 0 appariranno con una frequenza leggermente inferiore alle altre cifre. In compenso c’è un vantaggio: il seme di partenza lo possiamo scegliere semplicemente guardando l’orologio e prendendo il valore dei minuti, o dei secondi se preferite.

Se vi sentite più sicuri delle vostre abilità computatorie, William dà altri due esempi: X_n+1 = 50X_n mod 101 e X_n+1 = 20X_n mod 1999. Nel primo caso, il numero successivo della sequenza è dato da X_n+1 = 101 − X_n/2 se X_n è pari, e X_n+1 = 50 − (X_n−1)/2 se è dispari. Con questo generatore appaiono tutti i numeri da 1 a 100, quindi non c’è la distorsione del primo generatore presentato. Il secondo generatore invece ha un ciclo più lungo (non proprio 1998 ma 999, per ragioni simili a quelle per cui il periodo di 1/13 non è lungo 12 cifre ma solo 6), e soprattutto è molto più difficile da usare: partendo da un numero occorre prendere le ultime due cifre, moltiplicarle per 20 e sommare le altre tenute da parte. Da 314, per esempio, si calcola 14×20 = 280 e si somma 3 per arrivare a 283. Il caustico giudizio è “probabilmente mentre fate questi conti a mente vi sbagliate e finite nell’altro ciclo di 999 elementi, il che fa solo bene alla casualità!”

Qui a sinistra vedete un’immagine, presa sempre dal blog di William, che mostra visualmente la casualità dell’ultima cifra dei numeri ottenuti con quest’ultimo generatore. Se l’ultima cifra del numero è 0, allora è stato usato il nero; se è 9, il bianco; altrimenti sono state usate 8 sfumature di grigio. Il disegno non diventerà certo un bestseller, però direi che è sufficientemente casuale, no?

Bene! Ora potete avere qualche chance a sasso, forbici, carta. Non vi sentite più sollevati?