La settimana scorsa ho saltato ma avevo la scusa: ero in Italia. Comunque mi sembra doveroso fare qualche appunto.

• Il Malpensa Express è un treno regionale che qualche volta fa quattro fermate e qualche volta ne fa mille, in ogni caso percorre 54 km, costa 10 euro ed è operato da TreNord. Durante il mio primo viaggio su codesto treno mi sono beccato il questionario sulla qualità del servizio. Coda di paglia?
• Le Frecce hanno invaso i binari italiani, praticamente gli altri treni non esistono più, se vai sul sito di Trenitalia e vuoi andare da Vicenza a Grisignano di Zocco scopri che fai prima ad andarci a piedi, i pendolari avvertono un ineluttabile senso di sconforto: dev’essere più o meno quello che provavano i Neanderthal quando hanno incontrato il primo Sapiens, e quello non aveva neanche il wifi a bordo… oh, wait.
• Ho dovuto pagare un riscatto di ben £ 86,40 per poter uscire dal parcheggio di lunga permanenza all’aeroporto di Luton che avevo prenotato in anticipo pagando circa 40 sterline. Perché? Perché all’ingresso il sistema di riconoscimento della targa ha letto male la mia e ha ben pensato di farmela pagare cara, facendo pure finta di niente e pensando di essere al parcheggio di breve permanenza. Il giorno dopo mi hanno sentito, mi hanno chiamato “Ms”, e mi hanno restituito i soldi al volo.
• I bambini sotto i 5 anni sono i nuovi corrieri della droga. I tamarroni pieni di piercing invece possono passare facendo suonare il metal detector e non essere nemmeno perquisiti perché l’addetta dall’altra parte li conosceva. E no, non è successo a Malpensa.
• Le hostess di EasyJet ti vedono in difficoltà con le ginocchia e ti fanno sedere nei più larghi posti accanto alle uscite di emergenza, a patto che tu voglia prenderti la responsabilità di aprirle nell’improbabile eventualità di un atterraggio di emergenza. Con Ryanair se vuoi prenderti questa responsabilità devi pagare. I piloti di EasyJet sanno atterrare controvento, quelli di Ryanair non riescono nemmeno ad evitare che l’aereo rimbalzi quando tocca terra.
• Se nel Regno Unito vedi scritto “deviazione” comincia pure a piangere: tu pensi di dover andare da una parte e la deviazione ti porta dalla parte opposta, senza specificare altro.

Comunque sono stati sei bei giorni, ho rivisto gente, ho preso un po’ di sole e l’ho riportato su a scaldare l’algida Albione. Così tanto che in questo momento sto con le finestre aperte mentre due settimane fa in casa mettevo canottiera, maglietta, felpa e maglione.

C’è un’altra cosa di cui avevo accennato e che non ho mai approfondito. Non è che ora… però almeno qualche passo avanti l’ho fatto. Uno dei problemi dei generatori di numeri casuali è che molto spesso sono pseudocasuali, cioè c’è un algoritmo che, a partire da un numero chiamato seme genera una sequenza di numeri con un periodo estremamente lungo, nell’ordine anche di 20 cifre, che sono tante. Purtroppo sono pochissime quando si deve generare quantità vergognosamente grandi di numeri casuali, e quindi la soluzione tipica è ricorrere alle sorgenti fisiche. Gli esempi classici sono piazzare un’antenna, scorrere un po’ di frequenze, e catturare il rumore, oppure sondare le temperature o le oscillazioni di carica nei circuiti integrati… soluzioni di alta qualità ma spesso tragicamente lente, in grado di generare non più di qualche centinaio di migliaio di numeri al secondo. E quando te ne servono alcune centinaia di miliardi, l’attesa può diventare un problema.

Ora, i moderni cellofoni hanno in genere questi giocattolini chiamati accelerometri e magnetometri, al loro interno, che altro non sono che degli integrati che sputano fuori dei numeri. Questi numeri ovviamente non sono casuali, dipendono dall’orientamento del dispositivo, dai campi elettromagnetici da cui è investito, e da alcuni altri fattori più o meno trascurabili. Peggio ancora, tipicamente sono molto lenti. Per fare un esempio, l’accelerometro dell’iPhone è in grado di fornire circa 300 numeri al secondo, avendo tre assi e campionandolo 100 volte al secondo.

Con l’avanzare di crittografie sempre più sofisticate, con chiavi sempre più lunghe, la necessità di avere velocemente numeri (pseudo)casuali di alta qualità è evidente [1]. La soluzione standard è costruire un pool di entropia da cui attingere a piene mani quando servono numeri nuovi. Questi pool vengono riempiti e rinfrescati costantemente dal sistema operativo usando ogni cosa a sua disposizione: i tasti battuti dall’utente, i movimenti del mouse, campionamenti pseudocasuali dalla memoria, letture dai vari sensori di cui il computer dispone…

Qualche tempo fa mi è venuta voglia di scrivere un’applicazione per iOS che, sfruttando proprio l’accelerometro, generasse numeri casuali di alta qualità e in grande quantità. L’idea era di fare una specie di coltellino svizzero della casualità, in grado sia di generare enormi quantità di numeri in poco tempo e metterli a disposizione in tempo ragionevole, sia di generare le classiche scemenze tipo i d20 o le password. Sto ancora lavorando sulle applicazioni, ma prima di tutto volevo assicurarmi che il giochino fosse fattibile. La chiave di tutto è avere un buon generatore con distribuzione uniforme, il che vuol dire che ogni numero compreso in un certo intervallo ha la stessa probabilità di essere estratto rispetto agli altri, un po’ come quando si tira un dado non truccato.

Ci sono innumerevoli funzioni (almeno tre) per generare numeri pseudocasuali. Quella che va più di moda è arc4random() che può essere chiamata in qualsiasi momento, non necessità di essere inizializzata, produce sequenze esageratamente lunghe prima di cominciare a ripetersi, ed è di una lentezza disarmante. Un po’ più veloce è rand() che però deve essere inizializzata, produce sequenze ridicolmente brevi, e chi programma in C da lungo tempo sa bene quanto temere la chiamata “srand(time(NULL))”. Tra le due c’è random() che produce sequenze decenti e sarebbe meglio reinizializzarla ogni tanto.

Così mi sono detto: perché non richiedere una manciata di numeri a random() e poi reinizializzarla usando un seme basato su una sorgente fisica… tipo l’accelerometro? Così il rischio di ripetizioni della sequenza praticamente dovrebbe annullarsi. Detto fatto, il codice è così banale che non ve lo scrivo nemmeno, ho generato una certa quantità di numeri (65536, per i più curiosi) compresi tra 0 e 1, l’ho fatto più volte tanto per avere una quantità di dati da esaminare, e poi li ho importati in Octave per darci un’occhiata.

La linea blu è il dataset che ho generato con l’iPod, la linea rossa è un dataset che ho generato con l’apposita funzione di Octave, tanto per avere un termine di paragone. Il grafico mostra l’istogramma con 50 cestini, che poi vuol dire che ho diviso l’intervallo [0,1] in cinquanta intervallini e per ciascuno di questi ho contato quanti dei numeri generati ci finivano dentro. Idealmente ciascun intervallo dovrebbe contenere la stessa quantità di numeri degli altri. Poi in pratica non è proprio così, ma non siamo mica nell’iperuranio. Due cose comunque si notano:

1. per la maggior parte, la distribuzione è effettivamente uniforme: potrebbe essere meglio ma non fa neanche schifo;
2. a ben guardare, né il dataset generato con l’iPod né quello generato da Octave contengono né 0 né 1.

Questa cosa degli estremi mi ha fatto molto pensare, soprattutto al fatto che potrebbe esserci stato un problema di approssimazione nella divisione in virgola mobile. La verità è che random() genera numeri casuali tra 0 e (2^31)-1 e quindi ciascun numero andava normalizzato per risultare nell’intervallo [0,1] che serviva a me, e questo è un problema classico nel calcolo numerico ad alta precisione. Così ho saltato la divisione e ho analizzato direttamente gli interi. Stesso risultato: degli estremi nessuna traccia.

A questo punto il problema è chiaro: con i numeri casuali non si può mai sapere quello che succede. Potrebbe essere che ci aspettiamo di vedere uscire il numero 4 e in un miliardo di estrazioni non esca mai [2]. Questo però non vuol dire che possiamo assumere che un bel giorno uscirà anche lo zero e andare avanti.

Se a qualcuno venisse qualche idea, io sono in ascolto.

1. A chiunque si intenda un minimo di crittografia :) [↑]
2. A meno che non usiamo Debian, allora è garantito.[↑]